How to Code a Python QuickSort
In this guide, we’re going to talk about what quicksorts are and how they work. We’ll walk through an example of a Python quicksort so you can learn how to implement one.
Without further ado, let’s get started!
What is a QuickSort?
A quicksort is an algorithm that divides an array into subarrays and calls these subarrays recursively to sort each element in the list.
The quicksort algorithm is based on a divide-and-conquer approach. This means that the task of sorting a list is broken down into several subtasks. At the end of the sort, the results of these subtasks come together to return a sorted list.
In a quicksort, the subtask is setting a pivot for each sublist and ordering elements based on their value relative to the pivot.
When Should I Use a QuickSort?
A quicksort is useful when time complexity matters. This is because quicksorts use less memory space than other algorithms, which gives them an efficiency boost.
You should only use a quicksort if you are familiar with recursion. This is because the quicksort algorithm depends on recursive functions.
A quicksort is more efficient than a merge sort on smaller arrays. However, on larger data sets, an insertion sort or a merge sort may be faster.
How Does a QuickSort Work?
First, a quicksort picks an element to serve as a pivot. This can be any element in a list. For this tutorial, we’re going to choose the last item in a list (3).
Next, a quicksort compares the value of pivot to every number when we loop through the items in the list. If an item is greater than the pivot number, it is moved after the pivot; otherwise, it is moved before the pivot:
The value 3 has moved down our list. All the items less than 3 moved to its left; all the values greater than three moved to its right.
Our array is split into two halves: items greater than the pivot and items less than a pivot.
Once this process has started, a new pivot begins on each of the two halves. This pivot begins separately and uses the same algorithm as above. First, we will set a pivot value which is equal to the last value in each list:
|Pivot One||Pivot Two|
Next, we will move all the values greater than a pivot to the right of the pivot. All values less than the pivot will be moved to the left.
|Pivot One||Pivot Two|
This process continues until every item in our list is sorted:
Our final array looks like this:
Python QuickSort Example
The quicksort needs two functions: a pivot function and a quicksort function.
Let’s start with the partition function. This will partition, or prepare, the array based on the value of the pivot element.
Our partition function will:
- Select the pivot element
- Move all items greater than the pivot to the right of the pivot
- Move all items less than the pivot to the left of the pivot
Let’s write a program which implements this algorithm:
def prepare(numbers, low, high): pivot = numbers[high] item = low - 1 for i in range(low, high): if numbers[i] <= pivot: item = item + 1 (numbers[item], numbers[i]) = (numbers[i], numbers[item]) (numbers[item + 1], numbers[high]) = (numbers[high], numbers[item + 1]) return item + 1
First, we select a pivot element. This is equal to the highest number in our list.
Next, we loop through all the items in the list using a for loop. If a number is less than or equal to the pivot, it is moved to the left of the pivot. Otherwise, it goes to the right of the pivot.
Our function returns the new high value, which is equal to item + 1.
Next, we’ve got to run our algorithm. We can do this by writing a separate function:
def quick_sort(numbers, low, high): if low < high: pivot = prepare(numbers, low, high) quick_sort(numbers, low, pivot - 1) quick_sort(numbers, pivot + 1, high)
This function checks to see whether the value of “low” is less than the value of “high”. If it is, our sort can continue. Otherwise, our sort stops because our list has been sorted.
Next, our function calls the
prepare() method. This identifies a pointer for the pivot and moves items to their correct place.
Our function then calls the
quick_sort() method twice. The first time, the quicksort is being run on the elements to the left of the pivot. The second time, the quicksort is run on the elements to the right of the pivot. Hence, our function is recursive because it calls itself.
This continues until every item in the list is sorted.
Let’s write a main program that defines a list to sort:
values = [8, 4, 5, 2, 1, 3] total_values = len(values) quick_sort(values, 0, total_values - 1) print(values)
First, we specify a list of values to sort. We use the len() method to calculate the length of our list of values. Next, we call the
We pass “values” as the numbers that we want to sort, 0 as the low number, and the length of “values” minus 1 as the high value. The high value is the length of values minus 1 because lists are indexed from zero.
Let’s try to run our program: [1, 2, 3, 4, 5, 8].
Our code returns a sorted list! We did it. Give yourself a pat on the back. Quicksorts are not easy to understand or implement.
On average, this algorithm will perform at O(n* log n). This happens when the pivot element is not the greatest or smallest element and when the pivot element is not near the middle element.
The quicksort has a worst case complexity of O(n2). This occurs when the element selected as a pivot is either the greatest or a smallest element. If this is the case, the pivot element will always be at the end of a sorted array. This will create a number of unnecessary subarrays.
The best case complexity for this algorithm is O(n* log n). This happens when the pivot element is either equal to the middle element or near the middle element.
A quicksort is an efficient method of sorting a small list.
Quicksorts use recursion to break down a list into smaller lists which are then sorted. Each list is sorted around a pivot element. Elements greater than the pivot are moved to its right; smaller elements are moved to the left of the pivot.
Now you’re ready to start implementing a quicksort algorithm in Python like an expert!