Quicksort uses a divide and conquer approach to sorting an array, and leverages recursion.
Essentially, you pick a pivot number from the array to be sorted, it can be any number:
[4, 6, 2, 1, 5]
Let’s pick 2.
Now partition the array into two sub-arrays, the numbers less than or equal to the pivot are added to the first sub-array (less), those greater are added to the second sub-array (greater):
pivot = 2 less = [1] greater = [4, 6, 5]
Note: Remember to skip the number you chose as a pivot when building your sub-arrays.
The last step is to recursively call quicksort on the two sub-arrays, joining the results to the pivot:
quicksort(less) + [2] + quicksort(greater)
Here’s the implementation, notice how we picked the first number in the array as our pivot, this makes it easy to skip.
def quicksort(array):
if len(array) < 2:
return array
# pick the first number in the array
pivot = array[0]
less = []
greater = []
# skip our pivot number, start from the second
for i in array[1:]:
if i <= pivot:
less.append(i)
else:
greater.append(i)
return quicksort(less) + [pivot] + quicksort(greater)
print(quicksort([7, 11, 5, 2, 44, 21, 3, 18, 1]))
# outputs:
[1, 2, 3, 5, 7, 11, 18, 21, 44]
The same, more concisely:
def quicksort(array):
if len(array) < 2:
return array
pivot = array[0]
less = [x for x in array[1:] if x <= pivot]
greater = [x for x in array[1:] if x > pivot]
return quicksort(less) + [pivot] + quicksort(greater)