Breder.org

Quicksort

Quicksort is a sorting algorithm which has a worst case time complexity of O(n^2) for an input sequence of n elements, but, for most practical applications, it has an average complexity of O(n log n) and is generally efficient in modern hardware. Another good property is that the sorting can also be performed in-place with small additional memory needed.

Conceptual decription

For a given sequence A with n elements, we proceed as follows:

1. Base case: If the sequence has a single element or is empty, the array is sorted and we're done.

2. Select an element from the sequence as the pivot. (for example the first element)

3. Divide step: Collect all elements other than the pivot which are less than its value (in no particular order), and name this subsequence as L. Likewise, collect all elements other than the pivot which are greater or equal to its value (also in no particular order), and call this subsequence M.

4. Recursive step: Apply Quicksort to the L and M subsequences. They will now each be sorted.

5. Conquer step: Return the sequence by concatenating L, the pivot, and M. This will return the sorted sequence.

Speed considerations

If the sequence is already “near-sorted”, selecting the pivot as the first or as the last element often leads to poor performance, as the recursion tree will be very imbalanced. A better approach, considering this case to be common, is to select the pivot at random as any element of the sequence. This leads to more balanced recursion trees in the average case.

For even greater performance by taking advantage of actual hardware behavior, an hybrid approach may be taken. When sorting small sequences (let's say 12~16 elements, depending on particular cache sizes), the algorithm might switch to insertion sort which, despite being O(n^2) asymptotically, requires no function call overhead and can be performed efficiently in cache for small and contiguous sections of memory.

Functional implementation

def quicksort_recursive(arr):
    if len(arr) <= 1: return arr
    pivot, others = arr[0], arr[1:]
    less = [e for e in others if e < pivot]
    more = [e for e in others if e >= pivot]
    return quicksort_recursive(less) \
        + [pivot] \
        + quicksort_recursive(more)

In-place implementation

# note: "low" and "high" are inclusive ranges
# the "arr" array is sorted in-place
def quicksort_inplace(arr, low=0, high=-1):
    # "-1" is the sentinel value for the last element of "arr"
    if high == -1: high = len(arr) - 1

    # the subarray has one or no elements
    if low >= high: return

    p = quicksort_partition(arr, low, high)
    quicksort_inplace(arr, low, p - 1)
    quicksort_inplace(arr, p + 1, high)

def quicksort_partition(arr, low, high):
    # the last element is selected as the pivot
    pivot = arr[high]

    # elements located at [low; i) will constitute
    # a subarray of elements less than the pivot
    i = low
    for j in range(low, high):
        if arr[j] < pivot:
            # swap the current element into the subarray
            arr[i], arr[j] = arr[j], arr[i]
            i += 1

    # swap the pivot into its correct position,
    # after the last element of the subarray)
    arr[i], arr[high] = arr[high], arr[i]
    return i

Source