Quicksort
The Quicksort steps are:
- Pick an element, called a pivot, from the list.
- Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
- Recursively sort the sub-list of lesser elements and the sub-list of greater elements.
The base case of the recursion are lists of size zero or one, which never need to be sorted.
Lomuto partition scheme
- This scheme chooses a pivot which is typically the last element in
the array.
- The algorithm maintains the index to put the pivot in variable i and each time it finds an element less than or equal to pivot, this
index is incremented and that element would be placed before the
pivot.
- As this scheme is more compact and easy to understand, it is frequently used in introductory material.
- Is less efficient than Hoare's original scheme.
Partition algorithm (using Lomuto partition scheme)
algorithm partition(A, lo, hi) is
pivot := A[hi]
i := lo // place for swapping
for j := lo to hi – 1 do
if A[j] ≤ pivot then
swap A[i] with A[j]
i := i + 1
swap A[i] with A[hi]
return i
Quicksort algorithm (using Lomuto partition scheme)
algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p – 1)
quicksort(A, p + 1, hi)
Hoare partition scheme
Uses two indices that start at the ends of the array being
partitioned, then move toward each other, until they detect an
inversion: a pair of elements, one greater than the pivot, one
smaller, that are in the wrong order relative to each other. The
inverted elements are then swapped.
There are many variants of this algorithm, for example, selecting pivot from A[hi] instead of A[lo]
partition algorithm (using Hoare partition scheme)
algorithm partition(A, lo, hi) is
pivot := A[lo]
i := lo – 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]
quicksort algorithm(using Hoare partition scheme)
algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p)
quicksort(A, p + 1, hi)
Hoare partition scheme vs Lomuto partition scheme
The pivot selection
The execution speed of the algorithm depends largely on how this mechanism is implemented, poor implementation can assume that the algorithm is run at a slow speed.
The choice of pivot determines partitions the data list, therefore, this is the most critical part of the implementation of the Quicksort algorithm. It is important to try that selecting the pivot left and right partitions have an identical size as much as possible.
Best and worst case
Worst case
The most unbalanced partition occurs when the pivot divides the list into two sublists of sizes _0 and n ? 1. This may occur if the pivot happens to be the smallest or largest element in the list, or in some implementations when all the elements are equal.
Best Case
In the most balanced case, each time we perform a partition we divide the list into two nearly equal pieces. This means each recursive call processes a list of half the size.
Formal analysis
- Worst-case analysis = O(n2)
- Best-case analysis = O(n) factor
- Average-case analysis = O(n log n)
Examples source
Using additional memory
def quicksort(array):
less = []
equal = []
greater = []
if len(array) > 1:
pivot = array[0]
for x in array:
if x < pivot:
less.append(x)
if x == pivot:
equal.append(x)
if x > pivot:
greater.append(x)
return sort(less)+equal+sort(greater)
else:
return array
Usage:
quicksort([12,4,5,6,7,3,1,15])
Without additional memory
def partition(array, begin, end):
pivot = begin
for i in xrange(begin+1, end+1):
if array[i] <= array[begin]:
pivot += 1
array[i], array[pivot] = array[pivot], array[i]
array[pivot], array[begin] = array[begin], array[pivot]
return pivot
def quicksort(array, begin=0, end=None):
if end is None:
end = len(array) - 1
if begin >= end:
return
pivot = partition(array, begin, end)
quicksort(array, begin, pivot-1)
quicksort(array, pivot+1, end)
Usage:
quicksort([97, 200, 100, 101, 211, 107])
In your example
Debug Lomuto partition
References:
