Day 15 - Quicksort


Definition(s)

Quicksort is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order.

Quicksort is a comparison sort, meaning that it can sort items of any type for which a "less-than" relation (formally, a total order) is defined. In efficient implementations it is not a stable sort, meaning that the relative order of equal sort items is not preserved. Quicksort can operate in-place on an array, requiring small additional amounts of memory to perform the sorting.

Algorithm(s)


In [1]:
import numpy as np
import random

In [2]:
def functional_quicksort(a):
    if len(a) <= 1:
        return a
    else:
        pivot = a[0]
        return functional_quicksort([x for x in a if x < pivot]) + \
               [x for x in a if x == pivot] + \
               functional_quicksort([x for x in a if x > pivot])

In [3]:
def partition(a, l, r, pivot):
    i, j = l, r
    
    while True:
        while a[i] < pivot:
            i += 1
            
        while a[j] > pivot:
            j -= 1
            
        if i <= j:
            a[i], a[j] = a[j], a[i]
            i += 1
            j -= 1
        
        if i > j:
            break

    return i, j
    

# median of three
def choose_pivot(a, l, r):
    return (a[random.randint(l, r)] + a[random.randint(l, r)] + a[random.randint(l, r)]) // 3

In [4]:
def impl_quicksort(a, l, r):
    if l < r:
        pivot = choose_pivot(a, l, r)
        i, j = partition(a, l, r, pivot)
        impl_quicksort(a, i, r)
        impl_quicksort(a, l, j)
        
def quicksort(a):
    impl_quicksort(a, 0, len(a) - 1)
    return list(a)

Run(s)


In [5]:
print(functional_quicksort([5, 1, 2, 10, 3, 2, 5, 3]))


[1, 2, 2, 3, 3, 5, 5, 10]

In [6]:
print(quicksort([5, 1, 2, 10, 3, 2, 5, 3]))


[1, 2, 2, 3, 3, 5, 5, 10]

In [7]:
xs = np.random.randint(100, size=20)

print(functional_quicksort(xs))
print(quicksort(xs))


[2, 3, 20, 34, 36, 36, 37, 43, 47, 47, 49, 53, 54, 57, 63, 65, 74, 76, 89, 93]
[2, 3, 20, 34, 36, 36, 37, 43, 47, 47, 49, 53, 54, 57, 63, 65, 74, 76, 89, 93]

In [8]:
num_tests = 20
for t in range(num_tests):
    xs = np.random.randint(10000, size=random.randint(50, 500))
    ys = xs[:]
    print("Test: {} -> {}".format(t, quicksort(xs) == list(sorted(ys))))


Test: 0 -> True
Test: 1 -> True
Test: 2 -> True
Test: 3 -> True
Test: 4 -> True
Test: 5 -> True
Test: 6 -> True
Test: 7 -> True
Test: 8 -> True
Test: 9 -> True
Test: 10 -> True
Test: 11 -> True
Test: 12 -> True
Test: 13 -> True
Test: 14 -> True
Test: 15 -> True
Test: 16 -> True
Test: 17 -> True
Test: 18 -> True
Test: 19 -> True