quick sort
β’ 153 words β’ 1 min
First element is the pivot:
python
def quick_sort(a):
if len(a) < 2: ## [0, 1]
return a
pivot = a[0]
left = [x for x in a[1:] if x < pivot]
right = [x for x in a[1:] if x >= pivot]
left = quick_sort(left)
right = quick_sort(right)
return left + [pivot] + right
a = list(range(10))[::-1]
# it's usually easier to do it with a copy
assert quick_sort(a) == list(range(10))With a random pivot:
import random
def quick_sort(a):
if len(a) < 2: ## [0, 1]
return a
pivot = random.choice(a)
a_nopivot = [x for x in a if x != pivot]
left = [x for x in a_nopivot if x < pivot]
right = [x for x in a_nopivot if x >= pivot]
left = quick_sort(left)
right = quick_sort(right)
return left + [pivot] + right
a = list(range(10))[::-1]
# it's usually easier to do it with a copy
assert quick_sort(a) == list(range(10))