(java)

Suppose that the implementation of sorting by quick sort given below (see below) were changed as follows: Procedure partition is retained, but quickSort is eliminated, so that its work is done directly in sort. Is this change a good idea? What purpose does quickSort have? Discuss.

---------------------------------------------------------------------------------------------------------------

/** OVERVIEWS: ... */

public class Arrays {

/** MODIFIES: a

EFFECTS: Sorts a[0], ..., a[a.length 1]

into ascending order. */

public static void sort (int[] a) {

if (a == null) return;

quicksort(a, a.length - 1);

}

/** REQUIRES: a is not null and 0 <= low &

high < a.length

MODIFIES: a

EFFECT: Sorts a[low], a[low + 1], ..., a[high]

into ascending order. */

private static void quicksort(int[] a, int low,

int high) {

if (low >= high) return;

int mid = partition(a, low, high);

quickSort(a, low, mid);

quickSort(a, mid + 1, high);

}

/** REQUIRES: a is not null and 0 <= i < j < a.length

MODIFIES: a

EFFECTS: Reorders the elements in a into two

contiguous groups, a[i], ..., a[res] and

a[res + 1], ..., a[j], such that each element

in the second group is at least as large as

each element of the first group. Returns res. */

private static int partition(int[] a, int i, int j) {

int x = a[i];

while (true) {

while (a[j] > x) j--;

while (a[i] < x) i++;

if (i < j) { // need to swap

int temp = a[i]; a[i] = a[j]; a[j] = temp;

j--; i++;

} else return j;

}

}

}