Sorting is a common problem in computer science. Not only is a sorted list useful in itself, but sorted lists often enable other algorithms, such as binary search, to work.
This brings up the question: How do you sort a list? Perhaps the most intuitive way is to find the minimum value in the list, and then move that to the first index. Then, find the next smallest value and move it to the second index. Then, keep finding the next smallest value and moving it to the next index until the list is sorted.
This is called Selection Sort.
Many of you probably have used selection sort before in some way or another. Here’s an example implementation of this.
def selection_sort(lst):
for i in range(len(lst)):
min_value = lst[i]
min_val_idx = i
# find the new minimum value and its idx
for x in range(i, len(lst)):
if lst[x] < min_value:
min_value = lst[x]
min_val_idx = x
# swap the minimum value with the value at the current idx
lst[i], lst[min_val_idx] = min_value, lst[i]
return lst
test1 = [3, 12, 7, 2, 0, 3]
test1 = selection_sort(test1)
print(test1) # [0, 2, 3, 3, 7, 12]
test2 = [-23, 0, 72, -33, 11, 6, 2, -5, -9, 10, -1]
test2 = selection_sort(test2)
print(test2) # [-33, -23, -9, -5, -1, 0, 2, 6, 10, 11, 72]
test3 = [i for i in range(1000, -1, -1)]
test3 = selection_sort(test3) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
print(test3)
View code on GitHub.
Although Selection Sort is definitely intuitive, it’s also not that efficient. Its runtime is O(n^2) since you have to traverse the array one time for each iteration. So, let’s talk about some less intuitive but faster methods to sort a list
Quick sort is a very famous sorting algorithm, namely for its speed. Especially in smaller lists, quicksort is sometimes twice or three times as fast as other sorting algorithms like bubble sort or heap sort. Quick sort is a “divide and conquer” algorithm, so it is easiest to implement with recursion. Let’s put ourselves in the shoes of someone trying to develop a really fast sorting algorithm and “discover” quick sort.
Let’s start with the following list:
my_list = [43, 192, 234, 12, 3, 89, 78]
Let’s just take the last number in the list, 78, and put all of the elements smaller than 78 to the left, and all of the numbers larger than 78 to the right. We don’t care about whether the numbers to the left and right are ordered, just put it to the left or right side. If we do that, then our new list would look something like this:
my_list = [43, 3, 12, 78, 234, 192, 89]
green - numbers SMALLER than 78
purple- numbers LARGER than 78
In this case, we have 3 numbers to the left of 78 and 3 numbers to the right. The list is obviously not sorted yet, because the areas in green and purple are not sorted. However, notice that the position of 78 doesn’t change even if the two regions WERE sorted.
my_list = [43, 3, 12, 78, 234, 192, 89]
sorted_list = [3, 12, 43, 78, 89, 192, 234]
78 is in the same place because the number of elements to the left and right don’t change even if they are sorted. Thus, you could say 78 is sorted, or we know it’s position if the entire list WAS sorted.
Let’s call this process of putting elements smaller than 78 to the left and elements larger than 78 to the right partitioning. And let’s call 78 the pivot, the element that we use as a reference to move other elements to the left or right side. Note that the pivot doesn’t need to have the left and right regions be the same size. We could have picked any other element to be the pivot. As an example, we can also pivot around 89, shown below.
my_list = [43, 3, 78, 12, 89, 234, 192]
Before implementing quick sort, let’s just create a function that takes in a list and an index, and partitions the list with the pivot as the element with the index provided. There are many ways of doing this, but below is one approach.
def partition(arr, pi):
"""
partition takes some pivot index (pi), and puts all of the items
smaller than pivot to the left, and all of the items larger than
pivot to the right,
in doing so we put pivot in the same spot as if the entire list was
sorted
note: this is only one way of doing it
"""
# moves pivot to the end of the list so it doesn't get in the way
arr[-1], arr[pi] = arr[pi], arr[-1]
i = 0 # i is initialized to be the left side of our list
for j in range(len(arr)):
# if j is smaller than the pivot, arr[j] is smaller than the pivot,
# so we want to move it to the left
if arr[j] < arr[-1]:
# swaps arr[j] and arr[i], so arr[j] is at the left side of the list
arr[i], arr[j] = arr[j], arr[i]
i += 1
# move the pivot from the end to the correct location
arr[i], arr[-1] = arr[-1], arr[i]
Now that we have a partition function implemented, we can really easily create quick sort.