hw # 17

// Name                 :       Kyle Blanchard
// Due                  :       12/5/2014
// Class                :       CSCI-401
// Assignment           :   Improve quick sort
// Contact              :   Kwblanchard@student.stcc.edu


//package csci401;

public class medianQuickSort {

      public static void quickSort(int[] list) {
        quickSort(list, 0, list.length - 1);
      }

      private static void quickSort(int[] list, int first, int last) {
        if (last > first) {
          int pivotIndex = partition(list, first, last);
          quickSort(list, first, pivotIndex - 1);
          quickSort(list, pivotIndex + 1, last);
        }
      }

      /** Partition the array list[first..last] */
      private static int partition(int[] list, int first, int last) {
        int pivot = findMedian(list, first, last);
        int low = first + 1; // Index for forward search
        int high = last; // Index for backward search

        while (high > low) {
          // Search forward from left
          while (low <= high && list[low] <= pivot)
            low++;

          // Search backward from right
          while (low <= high && list[high] > pivot)
            high--;

          // Swap two elements in the list
          if (high > low) {
            int temp = list[high];
            list[high] = list[low];
            list[low] = temp;
          }
        }

        while (high > first && list[high] >= pivot)
          high--;

        // Swap pivot with list[high]
        if (pivot > list[high]) {
          list[first] = list[high];
          list[high] = pivot;
          return high;
        }
        else {
          return first;
        }
      }

      // New improved median based quick sort
      public static int findMedian(int[]list, int first, int last){
          // finds the middle number
          int middle = (first+last)/2;
          // if the first element is bigger than the last switch the elements
           if (list[first]>list[last])
                  switchElements(list, first, last);
          // if the first element is bigger than the middle switch the elements
          if (list[first]>list[middle])
                  switchElements(list, first, middle);
          // if the middle element is bigger than the last switch the elements
          if (list[middle]>list[last])
                  switchElements(list, middle, last);
          // the three elements should now be organized from greatest to least

          // this puts the pivot as the first element and returns it
          switchElements(list, middle, first);
          return list[first];
      }
      // Switches the elements
      public static void switchElements(int[] list, int x, int y) {
          int temp = list[x];
          list[x] = list[y];
          list[y] = temp;
    }


      /** A test method */
      public static void main(String[] args) {
        int[] list = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
        quickSort(list);
        for (int i = 0; i < list.length; i++)
          System.out.print(list[i] + " ");
      }
    }