/*
   This trivial program tests the insertion sort and selection sort
   subroutines.
*/


public class SortTest {

   final static int ARRAY_SIZE = 1000;  // Number of items in arrays to be sorted.
                                        // (This has to be 10 or more.)

   public static void main(String[] args) {
      
      int[] A = new int[ARRAY_SIZE];     // Make an array  ints
      
      for (int i = 0; i < A.length; i++)      // Fill array A with random ints.
         A[i] = (int)(10000*Math.random());
         
      int[] B = (int[])A.clone();   // make B an exact copy of A.
         
      System.out.println("The first 10 items in the array, before sorting:");
      for (int i = 0; i < 10; i++)
         System.out.print(" " + A[i]);
      System.out.println();
      System.out.println();
      
      selectionSort(A);  // Sort A using selctionSort
      
      System.out.println("The first 10 items, after array is sorted by selection sort:");
      for (int i = 0; i < 10; i++)
         System.out.print(" " + A[i]);
      System.out.println();
      System.out.println();
      
      insertionSort(B);  // Sort the copy using insertionSort
      
      System.out.println("The first 10 items, after array is sorted by insertion sort:");
      for (int i = 0; i < 10; i++)
         System.out.print(" " + B[i]);
      System.out.println();
      System.out.println();
      
   }
   
   
   static void selectionSort(int[] A) {
          // sort A into increasing order, using selection sort
      for (int lastPlace = A.length-1; lastPlace > 0; lastPlace--) {
           // Find the largest item among A[0], A[1], ... A[lastPlace],
           // and move it into position lastPlace by swapping it with
           // the number that is currently in position lastPlace
         int maxLoc = 0;  // location of largest item seen so far
         for (int j = 1; j <= lastPlace; j++) {
            if (A[j] > A[maxLoc])
               maxLoc = j;  // Now, location j contains the largest item seen
         }
         int temp = A[maxLoc];   // swap largest item with A[lastPlace]
         A[maxLoc] = A[lastPlace];
         A[lastPlace] = temp;
      }
   }


   static void insertionSort(int[] A) {
            // sort the array A into increasing order
       int itemsSorted;  // number of items that have been sorted so far
       for (itemsSorted = 1; itemsSorted < A.length; itemsSorted++) {
            // assume that items A[0], A[1], ... A[itemsSorted-1] have
            // already been sorted, and insert A[itemsSorted] into the list.
          int temp = A[itemsSorted];  // the item to be inserted
          int loc = itemsSorted - 1;
          while (loc >= 0 && A[loc] > temp) {
             A[loc + 1] = A[loc];
             loc = loc - 1;
          }
          A[loc + 1] = temp;
       }
    }

}