# 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 :

import numpy as np
import random

``````
``````

In :

def functional_quicksort(a):
if len(a) <= 1:
return a
else:
pivot = a
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 :

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 :

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 :

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

``````
``````

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

``````
``````

In :

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

``````
``````

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

``````
``````

In :

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 :

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

``````