Quick sort without additional memory (in place)

Usage:

array = [97, 200, 100, 101, 211, 107]
quicksort(array)
print(array)
# array -> [97, 100, 101, 107, 200, 211]

def partition(array, begin, end):
    pivot = begin
    for i in range(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
    def _quicksort(array, begin, end):
        if begin >= end:
            return
        pivot = partition(array, begin, end)
        _quicksort(array, begin, pivot-1)
        _quicksort(array, pivot+1, end)
    return _quicksort(array, begin, end)

There is another concise and beautiful version

def qsort(arr):
    if len(arr) <= 1:
        return arr
    else:
        return qsort([x for x in arr[1:] if x < arr[0]])
        + [arr[0]]
        + qsort([x for x in arr[1:] if x >= arr[0]])

Let me explain the above codes for details

1. pick the first element of array arr[0] as pivot

   [arr[0]]

2. qsort those elements of array which are less than pivot with List Comprehension

   qsort([x for x in arr[1:] if x < arr[0]])

3. qsort those elements of array which are larger than pivot with List Comprehension

   qsort([x for x in arr[1:] if x >= arr[0]])

This answer is an in-place QuickSort for Python 2.x. My answer is an interpretation of the in-place solution from Rosetta Code which works for Python 3 too:

import random

def qsort(xs, fst, lst):
    '''
    Sort the range xs[fst, lst] in-place with vanilla QuickSort

    :param xs:  the list of numbers to sort
    :param fst: the first index from xs to begin sorting from,
                must be in the range [0, len(xs))
    :param lst: the last index from xs to stop sorting at
                must be in the range [fst, len(xs))
    :return:    nothing, the side effect is that xs[fst, lst] is sorted
    '''
    if fst >= lst:
        return

    i, j = fst, lst
    pivot = xs[random.randint(fst, lst)]

    while i <= j:
        while xs[i] < pivot:
            i += 1
        while xs[j] > pivot:
            j -= 1

        if i <= j:
            xs[i], xs[j] = xs[j], xs[i]
            i, j = i + 1, j - 1
    qsort(xs, fst, j)
    qsort(xs, i, lst)

And if you are willing to forgo the in-place property, below is yet another version which better illustrates the basic ideas behind quicksort. Apart from readability, its other advantage is that it is stable (equal elements appear in the sorted list in the same order that they used to have in the unsorted list). This stability property does not hold with the less memory-hungry in-place implementation presented above.

def qsort(xs):
    if not xs: return xs # empty sequence case
    pivot = xs[random.choice(range(0, len(xs)))]

    head = qsort([x for x in xs if x < pivot])
    tail = qsort([x for x in xs if x > pivot])
    return head + [x for x in xs if x == pivot] + tail

Quicksort with Python

In real life, we should always use the builtin sort provided by Python. However, understanding the quicksort algorithm is instructive.

My goal here is to break down the subject such that it is easily understood and replicable by the reader without having to return to reference materials.

The quicksort algorithm is essentially the following:

1. Select a pivot data point.
2. Move all data points less than (below) the pivot to a position below the pivot - move those greater than or equal to (above) the pivot to a position above it.
3. Apply the algorithm to the areas above and below the pivot

If the data are randomly distributed, selecting the first data point as the pivot is equivalent to a random selection.

Readable example:

First, let's look at a readable example that uses comments and variable names to point to intermediate values:

def quicksort(xs):
    """Given indexable and slicable iterable, return a sorted list"""
    if xs: # if given list (or tuple) with one ordered item or more: 
        pivot = xs[0]
        # below will be less than:
        below = [i for i in xs[1:] if i < pivot] 
        # above will be greater than or equal to:
        above = [i for i in xs[1:] if i >= pivot]
        return quicksort(below) + [pivot] + quicksort(above)
    else: 
        return xs # empty list

To restate the algorithm and code demonstrated here - we move values above the pivot to the right, and values below the pivot to the left, and then pass those partitions to same function to be further sorted.