Chapter 23 Exercise 4, Introduction to Java Programming, Tenth Edition Y. Daniel LiangY.

23.4 (Improve quick sort) The quick sort algorithm presented in the book selects the first element in the list as the pivot. Revise it by selecting the median among the first, middle, and last elements in the list.

public class Exercise04 {
 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 = (list[first] + list[last] + list[(last + first) / 2]) / 3; // Choose the first element as the pivot
  int low = first; // 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--;

  if (pivot > list[high]) {
   return high;
  } else {
   return first;
  }
 }

 /** 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] + " ");
 }
}