How to Code a Python QuickSort

A Python QuickSort selects a pivot element and splits the elements of an array into two new arrays. Numbers higher than the pivot go into one array; numbers lower than the pivot go into another. Each array is sorted and then all the arrays are merged into one.

How to Code a Python QuickSort

There are plenty of sorting algorithms you can use to sort a list in programming. There’s Python insertion sorts, bubble sorts, and more. QuickSort are one of the most common types of sorts.

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 Python QuickSort?

A Python QuickSort algorithm divides an array into sub arrays. This algorithm calls these sub arrays recursively to sort each element in the list. The contents of a sub array are determined by a pivot element that is not moved into a new sub array.

The QuickSort algorithm divides-and-conquers. 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 sub list and ordering elements based on their value relative to the pivot.

When Should I Use a Python QuickSort?

A QuickSort is useful when time complexity matters. This is because QuickSort use less memory space than other algorithms, which gives them an efficiency boost.

You should only use a QuickSort if you are familiar with Python 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?

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).

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, we move the number after the pivot; otherwise, we move the number 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 Python 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:

Next, we will move all the values greater than a pivot to the right of the pivot. We move all values less than the pivot to the left.

This process continues until we sort our list:

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:

1. Select the pivot element
2. Move all items greater than the pivot to the right of the pivot
3. Move all items less than the pivot to the left of the pivot

QuickSort Python Program

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 Python 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 Python function returns the new high value. The new high value 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. If our sort stops, it means we have sorted the list.

"Career Karma entered my life when I needed it most and quickly helped me match with a bootcamp. Two months after graduating, I found my dream job that aligned with my values and goals in life!"

Venus, Software Engineer at Rockbot

Find Your Bootcamp Match

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, we run the QuickSort on the elements to the left of the pivot. The second time, we run the QuickSort 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.

Writing a Main Method

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 Python len() method to calculate the length of our list of values. Next, we call the quick_sort() method.

We pass “values” as the numbers that we want to sort. We then pass 0 as the low number. The length of “values” minus 1 is the high value we specify. The high value is the length of values minus 1 because the first item in a list has the index number 0.

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. QuickSort are not easy to understand or implement.

Complexity Overview

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 the worst case complexity of O(n2). This occurs when the element selected as a pivot is either the greatest or 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 sub arrays.

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.

To learn more about algorithm complexity, check out our guide to Big O Notation.

Conclusion

Python 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.

For guidance on top Python learning resources, online courses, and books, read our comprehensive How to Learn Python guide.