## Sunday, 22 January 2017

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