 In Progress
Lesson 19 of 43
In Progress

# 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].