How to write a Quicksort Algorithm in Python

While there are libraries available for all programming languages that offer abilities to sort list, arrays and collections, it is important to know how this is achieved.

Learning how to write a quicksort algorithm yourself gives the ability to better understand the programming language of your choice and how to optimise code where possible.

Today we will explore writing a quicksort algorithm in the Python programming language.

Let’s start by defining a list of integers that are clearly not in order:

unordered = [97, 200, 100, 101, 211, 107]
Code language: Python (python)

Next, we need to create a function, which we will call quicksort that will house our algorithm. We will give it our unsorted list and it will return a sorted list once done.

# Create a function with 3 arguments # `list` = an unsorted list # `start` = index where to start sorting # `end` = index where to end sorting def quicksort(list, start=0, end=None): if end is None: end = len(list) - 1 # an internal recursion function to do all the work def _quicksort(list, start, end): if start >= end: return pivot = partition(list, start, end) _quicksort(list, start, pivot-1) _quicksort(list, pivot+1, end) return list # call our internal function and return return _quicksort(list, start, end)
Code language: Python (python)

We’re not done quite yet, we still need to write our partition function that will return a new pivot point on each run.

# Create another function with 3 arguments # `list` = a list # `start` = starting index # `end` = ending index def partition(list, start, end): # start by setting our pivot point at the start pivot = start for i in range(start+1, end+1): if list[i] <= list[start]: pivot += 1 # swap loop index and pivot around list[i], list[pivot] = list[pivot], list[i] # swap pivot and start values around list[pivot], list[start] = list[start], list[pivot] # return our new pivot return pivot
Code language: Python (python)

Now let’s put it all together and try it out!

# Create a function with 3 arguments # `list` = an unsorted list # `start` = index where to start sorting # `end` = index where to end sorting def quicksort(list, start=0, end=None): if end is None: end = len(list) - 1 # an internal recursion function to do all the work def _quicksort(list, start, end): if start >= end: return pivot = partition(list, start, end) _quicksort(list, start, pivot-1) _quicksort(list, pivot+1, end) return list # call our internal function and return return _quicksort(list, start, end) # Create another function with 3 arguments # `list` = a list # `start` = starting index # `end` = ending index def partition(list, start, end): # start by setting our pivot point at the start pivot = start for i in range(start+1, end+1): if list[i] <= list[start]: pivot += 1 # swap loop index and pivot around list[i], list[pivot] = list[pivot], list[i] # swap pivot and start values around list[pivot], list[start] = list[start], list[pivot] # return our new pivot return pivot
Code language: Python (python)

What do we get when we call it with our unsorted list from before?

unsorted = [97, 200, 100, 101, 211, 107] print(quicksort(unsorted)) # [97, 100, 101, 107, 200, 211]
Code language: Python (python)

Ah, lovely, we now have a sorted list of integers compliments of our quicksort python function!

Subscribe
Notify of
guest
1 Comment
Newest
Oldest Most Voted
Inline Feedbacks
View all comments
trackback

[…] Learn how to write a Quicksort Algorithm in Python so that you can ace programming interviews at all the best tech companies! Read more […]