Quick Sort
How to efficiently order elements in an array
To get started in data structures and algorithms, it’s good to know the basic searching and sorting methods.
Here we will discuss the sorting algorithm known as quick sort, how it works, and finally how to code it. Let’s begin!
We start off with an unsorted list of numbers, and we want to put them in increasing order as quickly as possible. We can use a recursive approach, as follows.
The base case will be when the list consists of just one or zero elements. In that case the list is already sorted, so we can return the list itself.
The recursive step will be to pick one element (in our case we will pick the first in the list), and do just enough work to put it in the right place. Then we can recursively sort the remaining unsorted portions of the list.
The one element which we want to put in its correct position will be called the pivot. It will be put in its correct place, with all the other elements arranged on either its left or its right depending on whether they are less than or greater than it respectively.
We will need three pointers. One corresponds to the pivot element that we wish to place in its correct spot. A second will be used to store the elements which will ultimately reside to the left of the pivot since their value is less. Finally a third pointer will serve as the index to loop through all elements to the right of the pivot.
Let’s now describe how the procedure will work, and then finally show it in code so that you can see and run it yourself. We check which elements have a value less than the pivot. For each one that does, we move it to the left, since we know it should eventually be placed to the left of the pivot’s ultimate position.
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = 0
store = pivot + 1
for idx in range(store,len(arr)):
if arr[idx] < arr[pivot]:
arr[idx], arr[store] = arr[store], arr[idx]
store += 1
new_pivot = store - 1
arr[pivot], arr[new_pivot] = arr[new_pivot], arr[pivot]
left_portion = quicksort(arr[:new_pivot])
right_portion = quicksort(arr[new_pivot + 1:])
return left_portion + [arr[new_pivot]] + right_portionarr = [21, 21, 21, 93, 99, 20, 25, 16, 21, 14]
quicksort(arr)
>>> [14, 16, 20, 21, 21, 21, 21, 25, 93, 99]
I hope this helps you understand how the quick sort algorithm works, and how you can implement using Python!
