Question

Trace the execution of quicksort on the following array, assuming that the first item in each subarray is the pivot value. Show the values of first and last for each recursive call and the array elements after returning from each call. Also, show the value of pivot during each call and the value returned through pivIndex. How many times is sort called, and how many times is partition called? 55 50 10 40 80 90 60 100 70 80 20 50 22

The following code is provided in the textbook:

/** Implements the quicksort algorithm. */

public class QuickSort {

/** Sort the table using the quicksort algorithm. @pre table contains Comparable objects. @post table is sorted. @param table The array to be sorted */

public static > void sort(T[] table) { // Sort the whole table. quickSort(table, 0, table.length - 1); }

/** Sort a part of the table using the quicksort algorithm.

@post The part of table from first through last is sorted.

@param table The array to be sorted

@param first The index of the low bound
@param last The index of the high bound

*/

private static > void quickSort(T[] table, int first, int last) {

if (first < last) { // There is data to be sorted.

// Partition the table.

int pivIndex = partition(table, first, last);

// Sort the left half.

quickSort(table, first, pivIndex - 1);

// Sort the right half. quickSort(table, pivIndex + 1, last);

}

}

/** Partition the table so that values from first to pivIndex are less than or equal to the pivot value, and values from pivIndex to last are greater than the pivot value.

@param table The table to be partitioned

@param first The index of the low bound

@param last The index of the high bound

@return The location of the pivot value

*/

private static > int partition(T[] table, int first, int last) {

// Select the first item as the pivot value.

T pivot = table[first]; int up = first; int down = last;

do {

/* Invariant: All items in table[first . . . up - 1] <= pivot All items in table[down + 1 . . . last] > pivot */

while ((up < last) && (pivot.compareTo(table[up]) >= 0)) { up++;

}

// assert: up equals last or table[up] > pivot.

while (pivot.compareTo(table[down]) < 0) {

down--; }

// assert: down equals first or table[down] <= pivot.

if (up < down) {

// if up is to the left of down. //

Exchange table[up] and table[down].

swap(table, up, down);

}

}

while (up < down);

// Repeat while up is left of down. //

Exchange table[first] and table[down] thus putting the // pivot value where it belongs.

swap(table, first, down);

// Return the index of the pivot value. return down;

}

Answer 1

QUICK SORT

Assumption of language convention:

i = first

j = last

p = pivIndex

i = up

j = down

page 1

page 2

page 3

page 4

page 5