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]
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)
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
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
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]
Ah, lovely, we now have a sorted list of integers compliments of our quicksort python function!
