// Practicing with sorting and searching

#include <iostream.h>
#include <iomanip.h>

void sort (int A[],const int n);			            // Performs insertion sort
void display_array (int A[], int n);	            // Displays the array
void input_numbers(int A[],int &n);		            // Gets numbers from nums.dat


void main ()
{
	int numbers[100];	// Array of integers
	int n;				// Number of integers actually entered into numbers array


	input_numbers(numbers, n);  	// Get array elements from nums.dat
	sort(numbers, n);             // Sort array elements

// This code fragment will be added after the sorting algorithm is explored
//
//	int num;
//	cout << "What number would you like to search for? ";
//	cin >> num;
//
//	int pos = search(numbers,n,num);
//	if (pos < 0)
//		cout << "Your number could not be found" << endl;
//	else
//		cout << "Your number was found in position " << pos << endl;


	display_array(numbers, n);   //Display array in sorted order
}



//This function reads numbers from the file nums.dat and places them
//into the array until end of file is encountered.  The function returns
//the array and the number of elements entered.

void input_numbers(int A[],int &n)
{

}


//Display the array 10 elements per line.

void display_array (int A[], int n)
{
	int i;

	cout << endl;
	for (i = 0; i < n; ++i)
	{
		if ((i % 10) == 0)
			cout << endl;
		cout << setw(6) << A[i];
	}
	cout << endl;
}


//Sort array using the insertion sort algorithm.  It will insert
//each array element in its proper place starting with the second
//(i.e. index=1).

void sort (int A[], int n)
{
	int i;

	for (i = 1; i < n; ++i) 	// Process each element starting with the 2nd
	{
		if (A[i] < A[i-1])      // Is element with index i out of place?
		{
			int temp = A[i];           // If element is out of place shift
			int j = i;                 // down the elements to the right
			do                         // until we find the correct spot for
			{                          // the element with index i
				A[j] = A[j-1];
				--j;
			} while ((j>0) && (A[j-1] > temp));
			A[j] = temp;               //Put element with index i in correct position
		}
	}
}



// The following function sequentially searches for the array item.  It
// returns the index of the item if found or the value -1 if not found.