![Partition Scheme
The choice of pivot and partitioning steps could
greatly affects the algorithm¡¯s performance.
Below are the two scheme:
Lomuto Partition Scheme pseudocode
algorithm paritition(A, lo, hi) is
pivot := A[hi]
i := lo
for j := lo to hi do
if A[j] < pivot then
swap A[i] with A[j]
i := I + 1
swap A[i] with A[hi]
return i
Hoare Partition Scheme
algorithm partition(A, lo, hi) is
pivot := A[(hi + lo) / 2]
i := lo ¨C 1
j := hi + 1
loop forever
do
i := i + 1
while A[i] < pivot
do
j := j - 1
while A[j] > pivot
if i >= j then
return j
swap A[i] with A[j]](https://image.slidesharecdn.com/quicksort-200510184935/85/Quicksort-4-320.jpg)
![Algorithm:
algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p)
quicksort(A, p + 1, hi)
Example: Quicksort using Hoare Partition Scheme
Value 12 5 29 0 22 5 7
Index 0 1 2 3 4 5 6
Let sort this array from index 1 to index 5
Value 5 29 0 22 5
Index 0 1 2 3 4
lo = 0, hi = 4, pivot = 0, swap(A[0], A[2])
Value 0 29 5 22 5
Index 0 1 2 3 4
Recursively call:
+ quicksort(A, 0, 0)
+ quicksort(A, 1, 4)
Value 0 5 5 22 29
Index 0 1 2 3 4
lo = 1, hi = 4, pivot = 5, swap(A[1], A[4])
Recursively call:
+ quicksort(A, 1, 1)
+ quicksort(A, 2, 2)
+ quicksort(A, 3, 4)
lo = 1, hi = 2, pivot = 5, swap(A[1], A[2])
Recursively call:
+ quicksort(A, 1, 2)
lo = 3, hi = 4, pivot = 22
Recursively call:
+ quicksort(A, 3, 3)
+ quicksort(A, 4, 4)
Value 0 5 5 22 29
Index 0 1 2 3 4
Result:](https://image.slidesharecdn.com/quicksort-200510184935/85/Quicksort-5-320.jpg)
Quicksort
- 2. Quicksort or partition-exchange sort is an efficient sorting algorithm developed by Tony Hoare in 1959 while in the Soviet Union, as a visiting student at Moscow State University. At that time, he worked on a project on machine translation for the National Physical Laboratory. (Wikipedia)
- 3. Quicksort Variants 1. Multi-pivot Quicksort : Instead of partition array into two subarrays, it partitions into some s number of subarrays using s ¨C 1 pivot. In mid-1970s, the dual-pivot case was considered by Sedgewick and others, but the resulting algorithm is not faster than the ¡°classical¡± quicksort in practice. However, it can be more efficient by making uses of processor caches. It is more related to cache performance. 2. External Quicksort : Everything is the same as a regular quick sort except the pivot is replaced by a buffer. It is a kind of three-way quicksort in which the middle partition (buffer) represents a sorted subarray of elements that are approximately equal to the pivot. 3. Three-way radix Quicksort : A combination of radix sort and quicksort. 4. Quick radix sort : A combination of radix sort and quicksort but left/right partition decision is made on successive bits of the key. 5. BlockQuicksort : Rearranges the computations of quicksort to convert unpredictable branches to data dependencies. 6. Partial and incremental Quicksort : Several variants of quicksort that separate the k smallest or largest elements from the rest of the input.
- 4. Partition Scheme The choice of pivot and partitioning steps could greatly affects the algorithm¡¯s performance. Below are the two scheme: Lomuto Partition Scheme pseudocode algorithm paritition(A, lo, hi) is pivot := A[hi] i := lo for j := lo to hi do if A[j] < pivot then swap A[i] with A[j] i := I + 1 swap A[i] with A[hi] return i Hoare Partition Scheme algorithm partition(A, lo, hi) is pivot := A[(hi + lo) / 2] i := lo ¨C 1 j := hi + 1 loop forever do i := i + 1 while A[i] < pivot do j := j - 1 while A[j] > pivot if i >= j then return j swap A[i] with A[j]
- 5. Algorithm: algorithm quicksort(A, lo, hi) is if lo < hi then p := partition(A, lo, hi) quicksort(A, lo, p) quicksort(A, p + 1, hi) Example: Quicksort using Hoare Partition Scheme Value 12 5 29 0 22 5 7 Index 0 1 2 3 4 5 6 Let sort this array from index 1 to index 5 Value 5 29 0 22 5 Index 0 1 2 3 4 lo = 0, hi = 4, pivot = 0, swap(A[0], A[2]) Value 0 29 5 22 5 Index 0 1 2 3 4 Recursively call: + quicksort(A, 0, 0) + quicksort(A, 1, 4) Value 0 5 5 22 29 Index 0 1 2 3 4 lo = 1, hi = 4, pivot = 5, swap(A[1], A[4]) Recursively call: + quicksort(A, 1, 1) + quicksort(A, 2, 2) + quicksort(A, 3, 4) lo = 1, hi = 2, pivot = 5, swap(A[1], A[2]) Recursively call: + quicksort(A, 1, 2) lo = 3, hi = 4, pivot = 22 Recursively call: + quicksort(A, 3, 3) + quicksort(A, 4, 4) Value 0 5 5 22 29 Index 0 1 2 3 4 Result: