COP 3337
  Section U05
  Spring 2017


                         THE QUICK SORT METHOD
                         =====================



  I. The driver, the method, and the printArray:
  ----------------------------------------------


  public class QuickSort 
  {

      // driver for quicksort
      // test merge sort
      public static void main(String[] args) 
      {
          System.out.println("Test Quick Sort");
          System.out.println("===============");
        
          // the array to be sorted
          int[] table = { 78, 45, 89, 23, -26, -10, 37, 38, 47, 58, 69, -45, 4};
          printArray("The array before quick sort:",table);
          sort(table);
          System.out.println("We quick sort the array");
          printArray("The sorted array:", table);
      }
    

      // sort the array a
      public static void sort(int[] a)
      {
          if (a != null )
              quickSort(a, 0,a.length -1);
      }
  
      // sort the slice a[low:high]
      public static void quickSort(int a[], int low, int high)
      {

          // handle the cases when the slice has <= 3 items
          if (high - low <= 0)
             return;
          if ( high - low == 1)
          {
              // sort 2
              if (a[low] > a[high])
                  swap(a,low,high);
              return;
          }
          if (high - low == 2)
          {
              // sort 3
              if (a[low] > a[low +1])
                  swap(a,low,low +1);
              if (a[low+1] > a[low +2])
                  swap(a,low + 1,low + 2);
              if (a[low] > a[low + 1])
                  swap(a,low,low +1);
              return;
          }
        
          // sort when a.length >= 4
          // sort a[low],a[mid], a[high]
          int mid = (low+high) / 2;
          if (a[mid] < a[low])
              swap(a,mid,low);
          if (a[high] < a[mid])
              swap(a, high,mid);
          if (a[mid] <  a[low])
              swap(a, mid, low);
          // move the pivot at position high -1
          swap(a, mid,high -1);
          int pivot = a[high - 1];

          // begin partitioning
          int i,j;
          for (i = low, j=high -1;;)
          {
              while (a[++i] < pivot); // advance i
              while (a[--j] > pivot); // decrease j

              if (i >= j)
                  break;
              swap(a,i,j);
          }


          // restore pivot
          swap(a,i,high-1);

          // recurse
          quickSort(a,low,i-1);
          quickSort(a,i+1,high);
      }

      // swap the contents of a[i] and a[j]
      public static void swap(int[] a, int i, int j)
      {
          int temp = a[i];
          a[i] = a[j];
          a[j] = temp;
      }

    
      // print an array of integers, one per line
      // message is the header
      private static void printArray(String message, int[] arr)
      {
          // print the header and underline it
          System.out.println(message);
          for (int i = 0; i < message.length() ; i++)
              System.out.print('-');
          System.out.println();
        
          // check for null or emmpy array
          if (arr == null)
              System.out.println("Null array");
          else if (arr.length == 0)
              System.out.println("Empty array");
          else
          {
              for (int curr : arr)
                  System.out.println(curr);
          }    
      } // end printArray    
    
  }

  II. The output:
  ---------------

  run:
  Test Quick Sort
  ===============
  The array before quick sort:
  ----------------------------
  78
  45
  89
  23
 -26
 -10
  37
  38
  47
  58
  69
  -45
  4
  We quick sort the array
  The sorted array:
  -----------------
  -45
  -26
  -10
  4
  23
  37
  38
  45
  47
  58
  69
  78
  89
  BUILD SUCCESSFUL (total time: 0 seconds)