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.
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)
In [5]:
print(functional_quicksort([5, 1, 2, 10, 3, 2, 5, 3]))
In [6]:
print(quicksort([5, 1, 2, 10, 3, 2, 5, 3]))
In [7]:
xs = np.random.randint(100, size=20)
print(functional_quicksort(xs))
print(quicksort(xs))
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))))