// Chapter 9, pp 412 - 413

#include <stdlib.h> // included for rand in main

#include <iostream.h>

const int MAX_SIZE = 12;

typedef int dataType;
typedef dataType arrayType[MAX_SIZE];

void InsertionSort(dataType A[], int N)
// ---------------------------------------------------
// Sorts the items in an array into ascending order.
// Precondition: A is an array of N items.
// Postcondition: The array A is sorted into ascending
// order; N is unchanged.
// ---------------------------------------------------
{
	// Unsorted = the first index of the unsorted region,
	// Loc = the index of insertion in the sorted region,
	// NextItem = the next item in the unsorted region

	// initially, sorted region is A[0] and
   //            unsorted region is A[1..N-1].
	// in general, sorted region is A[0..Unsorted-1] and
   //             unsorted region is A[Unsorted..N-1].

   for (int Unsorted = 1; Unsorted < N; ++Unsorted)
   {  // Invariant: A[0..Unsorted-1] is sorted

      // find the right position (Loc) in A[0..Unsorted]
      // for A[Unsorted], which is the first item in
      // the unsorted region -- shift, if necessary,
      // to make room
      dataType NextItem = A[Unsorted];
      int Loc = Unsorted;

      for (; (Loc > 0) && (A[Loc-1] > NextItem); --Loc)
			// shift A[Loc-1] to the right
			A[Loc] = A[Loc-1];
		// Assertion: A[Loc] is where NextItem belongs

      // insert NextItem into Sorted region
      A[Loc] = NextItem;
   }  // end for
}  // end InsertionSort

// ******SAMPLE MAIN PROGRAM******
main()
{  arrayType A;
   int N, Size;

   // create an array of random integers
   Size = MAX_SIZE; // size of array
   for (N = 0; N < Size; ++N)
      A[N] = rand();

   cout << "The array before sorting is:\n ";
   for (N = 0; N < Size; ++N)
      cout << A[N] << " ";
   cout << "\n";

   // sort the array
   InsertionSort(A, Size);

   cout << "The array after sorting is:\n ";
   for (N = 0; N < Size; ++N)
      cout << A[N] << " ";
   cout << "\n";
   return 0;
}  // end main