Quicksort

Quicksort and merge sort are both in-place and divide-and-conquer recursive algorithms.

Quicksort Sorting A[p ... r]

• Divide:: A[p ... r] into A[p ... q] and A[q+1 ... r] all have q determined as a part of the divide.

• Conquer:: A[p ... q] and A[q+1 ... r] are sorted recursively

• Combine:: None as all this leaves sorted array in place

Quicksort ( A, p, r )

1. if p < r

2.        then q ¬ Paritition ( A, p, r )

3.             Quicksort ( A, p, q )

4.             Quicksort ( A, q+1, r )

To sort an entire array A, the initial call is Quicksort ( A, 1, length[A] )

Partitioning the array

The key to the algorithm is the Partition procedure which rearranges the sub array A[p ...r] in place.

Partition ( A, p, r )

1. x ¬ A[p]

2. i ¬ p -1

3. j ¬ r + 1

4. while True

5.        do repeat j ¬ j - 1

6.            until A[j] £ x

7.        repeat i ¬ i + 1

8.            until A[i] ³ x

9.        If i < j

10.            then exchange A[i] « A[j]

11.        else return j

The cost of the Partition algorithm is Q (n)