

In [ ]:

    
%%HTML
<style>
.container { width:100% } 
</style>

An Array-Based Implementation of Quick-Sort

The function $\texttt{sort}(L)$ sorts the list $L$ in place.



In [ ]:

    
def sort(L):
    quickSort(0, len(L) - 1, L)

The function $\texttt{quickSort}(a, b, L)$ sorts the sublist $L[a:b+1]$ in place.



In [ ]:

    
def quickSort(a, b, L):
    if b <= a:
        return  # at most one element, nothing to do
    m = partition(a, b, L)  # m is the split index
    quickSort(a, m - 1, L)
    quickSort(m + 1, b, L)

The function $\texttt{partition}(\texttt{start}, \texttt{end}, L)$ returns an index $m$ into the list $L$ and regroups the elements of $L$ such that after the function returns the following holds:

$\forall i \in \{\texttt{start}, \cdots, m-1\} : L[i] \leq L[m]$,
$\forall i \in \{ m+1, \cdots, \texttt{end} \} : L[m] < L[i]$,
$L[m] = \texttt{pivot}$.

Here, $\texttt{pivot}$ is the element that is at the index $\texttt{end}$ at the time of the invocation of the function, i.e. we have

$L[\texttt{end}] = \texttt{pivot}$

at invocation time.

The for-loop of partition maintains the following invariants:

$\forall i \in \{\texttt{start}, \cdots, \texttt{left} \} : L[i] \leq \texttt{pivot}$,
$\forall i \in \{\texttt{left}+1, \cdots, \texttt{idx}-1\} : \texttt{pivot} < L[i]$,
$L[\texttt{end}] = \texttt{pivot}$.

This algorithm has been suggested by Nico Lomuto. It is not the most efficient implementation of partition, but it is easier to understand than the algorithms that use two separate loops.



In [ ]:

    
def partition(start, end, L):
    pivot = L[end]
    left  = start - 1
    for idx in range(start, end):
        if L[idx] <= pivot:
            left += 1
            swap(left, idx, L)
    swap(left + 1, end, L)
    return left + 1

The function $\texttt{swap}(x, y, L)$ swaps the elements at index $x$ and $y$ in $L$.



In [ ]:

    
def swap(x, y, L):
    L[x], L[y] = L[y], L[x]

Testing



In [ ]:

    
import random as rnd



In [ ]:

    
def demo():
    L = [ rnd.randrange(1, 200) for n in range(1, 16) ]
    print("L = ", L)
    sort(L)
    print("L = ", L)



In [ ]:

    
demo()



In [ ]:

    
def isOrdered(L):
    for i in range(len(L) - 1):
        assert L[i] <= L[i+1]



In [ ]:

    
from collections import Counter



In [ ]:

    
def sameElements(L, S):
    assert Counter(L) == Counter(S)

The function $\texttt{testSort}(n, k)$ generates $n$ random lists of length $k$, sorts them, and checks whether the output is sorted and contains the same elements as the input.



In [ ]:

    
def testSort(n, k):
    for i in range(n):
        L = [ rnd.randrange(2*k) for x in range(k) ]
        oldL = L[:]
        sort(L)
        isOrdered(L)
        sameElements(oldL, L)
        assert len(L) == len(oldL)
        print('.', end='')
    print()
    print("All tests successful!")



In [ ]:

    
%%time
testSort(100, 20000)

Next, we sort a million random integers.



In [ ]:

    
k = 1000000
L = [ rnd.randrange(1000 * k) for x in range(k) ]



In [ ]:

    
%%time
sort(L)

Again, we sort a million integers. This time, many of the integers have the same value.



In [ ]:

    
L = [ rnd.randrange(1000) for x in range(k) ]



In [ ]:

    
%%time
sort(L)

Next, we test the worst case and sort 5000 integers that are sorted ascendingly. Since quicksort is recursive, we have to increment the recursion limit of Python, because otherwise we would get an error that we exceed the maximum recursion depth.



In [ ]:

    
import sys



In [ ]:

    
sys.setrecursionlimit(10000)



In [ ]:

    
L = list(range(5000))



In [ ]:

    
%%time
sort(L)

If we shuffle the list to be sorted before sorting, the worst case behaviour disappears.



In [ ]:

    
rnd.shuffle(L)



In [ ]:

    
%%time
sort(L)



In [ ]: