#include <iostream.h>

// print integer list 
void printList (int lst[], int len) {
   for (int cnt = 0;cnt < len; cnt++) {
      cout << "|" << lst[cnt] << "|";
     }
   return;
 }

// sort integer list from large to small
void InsertSort (int list[], int num) {
   for (int cnt = 1; cnt < num; cnt++){
      // find proper spot for list[cnt]
      //   looking (only) at earlier positions in the array
      cout << endl << "   find proper spot for " << list[cnt]; 
      if (list[cnt] > list[cnt - 1]){
         // current element is larger than the one before
         //   hence some shifting is necessary
         cout << endl << "      " << list[cnt] 
              << " needs to move earlier in list";
         int curr = list[cnt];      // keep copy of current element
         int toMove = cnt;          // mark available spot
         // shift until correct
         do { 
            // shift element to later in the list
            cout << endl << "            " << list[toMove-1] << " shifting"
                << " right from position " << toMove-1 << " to " << toMove;
            list[toMove] = list[toMove - 1];
            // prepare to check next earlier spot
            toMove--;
            // keep looking until get to front of list or curr element fits
          } while ((toMove > 0) && (list[toMove - 1] < curr));
          // found place to put current element
          list[toMove] = curr;
       } // end if
      cout << endl << "After iteration: "; 
      printList(list,num);
     } // end for
  } // end InsertSort

int main() {
   int list[10] = { 13, 23, 5, 17, 19, 12 };
   cout << endl << "Starting List: ";
   printList(list,6);
   InsertSort(list,6);
   cout << endl << "Ending List: ";
   printList(list,6);
   cout << endl;
   return 0;
 }