/*
1.  for each array element starting with the second one.
       2.  for each element in the sorted part starting with the last one
              3. if this element is larger than the one being inserted
                    shift it to the right.
       4.  Place the element being inserted at the position of the
           last element that was shiffted.
*/




#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;

void insertSort(int[], int);

int main()
{
   const int SIZE = 100;
   int scores[SIZE];
   for (int i = 0; i < SIZE; i++)
     scores[i] = int(random() / 1000);

   insertSort(scores, SIZE);

   for (int i = 0; i < SIZE; i++)
      cout << scores[i] << ", ";
   cout << endl;
   return 0;
}


void insertSort(int x[], int size) {
  int j, next;
 /*
 for each array element starting with the second one.
       2.  for each element in the sorted part starting with the last one
              3. if this element is larger than the one being inserted
                     shift it to the right.

       4.  insert next at the position of 
            the last element that was shifted.                                
 */
 for (int nextIndex = 1; nextIndex < size; nextIndex++)
 {
    next = x[nextIndex];
    j = nextIndex - 1;
    while (j >= 0 && x[j] > next)
    {
       x[j+1] = x[j];
       j--;
    }

    x[j+1] = next;
 }
}