Understanding quicksort

Question

I'm having a hard time understanding quicksort, most of the demonstrations and explanations leave out what actually happens (http://me.dt.in.th/page/Quicksort/ for example).

Wikipedia says:

Pick an element, called a pivot, from the array. Partitioning: reorder the array 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 apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

How would that work with an array of 9,1,7,8,8 for example with 7 as the pivot? The 9 needs to move to the right of the pivot, all quicksort implementations are in place operations it seems so we can't add it after the 8,8, so the only option is to swap the 9 with the 7.

Now the array is 7,1,9,8,8. The idea behind quicksort is that now we have to recursively sort the parts to the left and right of the pivot. The pivot is now at position 0 of the array, meaning there's no left part, so we can only sort the right part. This is of no use as 7>1 so the pivot ended up in the wrong place.

In this image 4 is the pivot, then why is 5 going almost all the way to the left? It's bigger than 4! After a lot of swapping it ends up being sorted but I don't understand how that happened.

Answer 1

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(n²)
• 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:

• http://www.cs.bilkent.edu.tr/~atat/473/lecture05.pdf
• http://codefap.com/2012/08/the-quick-sort-algorithm/
• http://visualgo.net/sorting
• https://en.wikipedia.org/wiki/Quicksort