/********************************************  LANCE SIMMS, LLNL 2011
*NAME: SortArray
*
*PURPOSE:
*  To sort an array and return the indices of the sorted array.  The 
*  algorithm used is the simple insertion algorith.  It should take 
*  about O(N^2) operations.
*
*INPUTS:
*  Array: *INTU16
*    The array that needs to be sorted
*  Indices: *INTU16
*    The array that will be filled with the sorted indices
*
*RETURNS:
*  Success: INT32S
*    0 - Successful
*    1 - Failure
*
*********************************************************************/
#include <stdio.h>
#include <stdlib.h>

#define PRINT_ARRAY
#define PRINT_INDICES

void InsertSort(int *Array, int *SortInd, int LowerBound, int UpperBound){

  //Declare a variable to hold the current value (t) and index (s)
  int Temp, TempInd;
  int i,j,k;

  //The index of the 0th element is 0
  for (i=LowerBound; i<UpperBound+1; i++) SortInd[i]=i; 

#ifdef PRINT_ARRAY
    printf("Array to be sorted ------------------------------\n\r");
    for(k=LowerBound;k<UpperBound+1;k++) printf("%d ", Array[k]);
    printf("\n\r");
#endif
#ifdef PRINT_INDICES
    for(k=LowerBound;k<UpperBound+1;k++) printf("%d ", SortInd[k]);
    printf("\n\r");
#endif

  //Sort the array Array[LowerBound:UpperBound]
  for (i=LowerBound+1; i<=UpperBound; i++){
 
    //Take out the ith element of the array (card deck)
    Temp    = Array[i];
    TempInd = i;

    //Shift elements down until insertion point found
    for (j=i-1; (j>=LowerBound && (Array[j] > Temp)); j--){
      Array[j+1]   = Array[j];
      SortInd[j+1] = SortInd[j];
    }

    //Insert the element
    Array[j+1]   = Temp;
    SortInd[j+1] = TempInd;

#ifdef PRINT_ARRAY     
    printf("\n\r");
    for(k=LowerBound;k<UpperBound+1;k++) printf("%d ", Array[k]); 
#endif
#ifdef PRINT_INDICES
    printf("\n\r");
    for(k=LowerBound;k<UpperBound+1;k++) printf("%d ", SortInd[k]); 
    printf("\n\r");
#endif

   }
}

int main(int argc, char *argv[]){

  int ArrayToSort[20] = {3,4,8,1,0,2,4,5,9,-1,-5,20,7,-10,3,8,9,12,1,2};
  int SortedIndices[20];
  int lb = 0;
  int ub = 19;

  InsertSort(ArrayToSort, SortedIndices, lb, ub);

}