Faster Sorting Methods - Data Structures and Abstractions with Java - page 224

Question 2 Modify the merge sort algorithm given in Segment 9.3 so that it skips any
unnecessary merges, as just described.

Quick Sort

9.10

We now look at another divide and conquer strategy for sorting an array. The quick sort divides an array
into two pieces, but unlike merge sort, these pieces are not necessarily halves of the array. Instead, quick
sort chooses one entry in the array—called the pivot —and rearranges the array entries so that

•

The pivot is in the position that it will occupy in the final sorted array

• Entries in positions before the pivot are less than or equal to the pivot

•

Entries in positions after the pivot are greater than or equal to the pivot

This arrangement is called a partition of the array.

Creating the partition divides the array into two pieces, which we will call Smaller and Larger ,
separated by the pivot, as Figure 9-5 illustrates. Since the entries in Smaller are less than or equal to
the pivot, and the entries in Larger are greater than or equal to the pivot, the pivot is in its correct
and final position within the sorted array. If we now sort the two subarrays Smaller and Larger —by
using quick sort, of course—the original array will be sorted. The following algorithm describes
our sorting strategy:
Algorithm quickSort(a, first, last)
// Sorts the array entries a[first] through a[last] recursively.

VideoNote

Quick sort

if (first < last)
{

Choose a pivot
Partition the array about the pivot
pivotIndex = index of pivot
quickSort(a, first, pivotIndex - 1) // sort Smaller
quickSort(a, pivotIndex + 1, last) // sort Larger

}

FIGURE 9-5

A partition of an array during a quick sort

pivot pivot

pivot

Smaller Larger

The Efficiency of Quick Sort
9.11

Notice that creating the partition—which accounts for most of quickSort 's work—occurs before
the recursive calls to quickSort . Contrast this with merge sort, where most of the work occurs dur-
ing the merge phase after the recursive calls to mergeSort . Partitioning will require no more than n
comparisons, and so, like merging, it will be an O( n ) task. Thus, we can assess the efficiency of
quick sort, even though we have not yet developed a partitioning strategy.
The ideal situation occurs when the pivot moves to the center of the array, so the two subarrays
that the partition forms are the same size. If every recursive call to quickSort forms a partition
with equal-sized subarrays, the quick sort will be like merge sort in that the recursive calls halve the
array. Thus, quick sort would be O( n log n ), and this would be its best case.