Quick Sort

The divide-and-conquer approach can be used to arrive at an efficient sorting method different from merge sort.In merge sort,the file a[1 :n] was divided at its midpoint into sub arrays which were independently sorted and later merged. In quicksort, the division into two sub arrays is made so that the sorted sub arrays do not need to be merged later. This is accomplished by rearranging the elements in a[l:n] such that a[i] < a[j] for all i between 1 and m and all j between m + 1 and n for some m, 1< m < n. Thus, the elements in a[l:m] and a[rn + 1:n] can be independently sorted. No merge is needed.The rearrangement of the elements is accomplished by picking some element of a[],say t = a[s],and then reordering the other elements so that all elements appearing before t in a[1:n] are less than or equal to t and all elements appearing after t are greater than or equal to t. This rearranging is referred to as partitioning.

Function Partition of Algorithm 8(due to C.A.R. Hoare)accomplishes an in place partitioning of the elements of a[m:p – 1].It is assumed that a[p] >a[m] and that a[m] is the partitioning element. If m = 1 and p-1 = n, then a[n + 1]must be defined and must be greater than or equal to all elements in a[1:n]. The assumption that a[m] is the partition element is merely for convenience; other choices for the partitioning element than the first item in the set are better in practice. The function Interchange(a,i,j) exchanges a[i] with a[j].

Using Hoare’s clever method of partitioning a set of elements about a chosen element,we can directly devise a divide-and-conquer method for completely sorting n elements. Following a call to the function Partition, two sets S1 and S2 are produced. All elements in S1 are less than or equal to the elements in S2. Hence S1 and S2 can be sorted independently. Each set is sorted by reusing the function Partition. Algorithm 9 describes the complete process.

Performance Measurement

Quick Sort and Merge Sort were evaluated on a SUN work station 10/30.In both cases the recursive versions were used.For Quick Sort the Partition function was altered to carry out the median of three rule (i.e.the partitioning element was the median of a[m],a[[(m+p – 1)/2]]and a[p 1]).Each data set consisted of random integers in the range (0, 1000). Tables 1 and 2 record the actual computing times in milliseconds. Table 1 displays the average computing times.For each n, 50 random data sets were used. Table 2 shows the worst-case computing times for the 50 datasets. Scanning the tables,we immediately see that Quick Sort is faster than Merge Sort for all values. Even though both algorithms require 0(n logn) time on the average, Quick Sort usually performs well in practice.