//*****************************************************************************
//
//   Insertion Sort.cpp
//   Input:  list length n, and array list.
//   Output: list in increasing order.
//
//*****************************************************************************

#include<iostream>
using namespace std;

#define MAX_LIST_LEN  100

int main(){

   int    n,                    // list length
          j,                    // loop control
          i;                    // index of maximum element in unsorted section
                                // index of rightmost element in unsorted section
   double max,                  // maximum value in unsorted section
          temp,                 // temporary storage
          list[MAX_LIST_LEN];   // array to be sorted

   // Get values for n and list.
   cout << "Enter list length (must be less than or equal to "
        << MAX_LIST_LEN << "): ";
   cin  >> n;
   cout << "Enter " << n << " numbers:" << endl;
   for(j=0; j<n; j++){
      cin >> list[j];
   }

   // perform InsertionSort algorithm //


      for (i = 1; i < n; i++) {
            j = i;
            while (j > 0 && list[j - 1] > list[j]) {
                  temp = list[j];
                  list[j] = list[j - 1];
                  list[j - 1] = temp;
                  j--;
            }
      }

// Print out sorted list.
   for(j=0; j<n; j++){
      cout << list[j] << " ";
   }
   cout << endl;

   return(0);
}