Sorting
Contents
Sorting#
Sorting1 is an operation that you need to perform frequently. There are multiple sorting algorithms, such as bubble sort, insertion sort, merge sort, quick sort, etc. Each algorithm has a different time complexity, this means the amount of time need to sort an array.
Of course, Python offers built-in functions for sorting, e.g. list.sort().
But it is good to understand the basic principles of various sorting algorithms.
Bubble Sort#
The first algorithm that will be discussed is bubble sort.
The basic idea of bubble sort is to move the largest element to the end of a list, array, etc.
We will use a list of elements for which the comparison operator > is defined.
Suppose we have to sort the list [4, 3, 5, 2, 1].
In the first step the element 5 bubbles to the end of the list, giving [4, 3, 2, 1, 5].
In the second step the element 4 bubbles to the end of the list, but will not pass the element 5, giving [3, 2, 1, 4, 5].
In the third step the element 3 bubbles to the end of the list, but will not pass the element 4, giving [2, 1, 3, 4, 5].
In the fourth step the element 2 bubbles to the end of the list, but will not pass the element 3, giving [1, 2, 3, 4, 5].
The first version of bubble sort is a recursive version.
from typing import List
def bubble_to_end(lst : List[any]) -> List[any]:
""" moves the largest element to the end of the list"""
if len(lst) <= 1: # Stop condition for moving
return lst
else:
if lst[0] > lst[1]:
# Swap the first and second elements in the row
lst[0], lst[1] = lst[1], lst[0]
first : any = lst[0]
return [first] + bubble_to_end(lst[1:])
def bubble_sort_r(unsorted : List[any]) -> List[any]:
""" sorts a list in a recursive way
>>> bubble_sort([3, 4, 7, -1, 2, 5])
[-1, 2, 3, 4, 5, 7]
>>> bubble_sort([])
[]
>>> bubble_sort([5, 4, 3, 2, 1])
[1, 2, 3, 4, 5]
"""
if len(unsorted) <= 1: # Stop condition for sorting
return unsorted
else:
unsorted = bubble_to_end(unsorted) #move (bubble) largest element to the end
print(unsorted)
last : any = unsorted.pop() #remove last element and remember it
sortedList = bubble_sort_r(unsorted)
print(sortedList)
return sortedList + [last] #sort the rest and concatenate last element
print(bubble_sort_r([4,3,5,2,1]))
[3, 4, 2, 1, 5]
[3, 2, 1, 4]
[2, 1, 3]
[1, 2]
[1]
[1, 2]
[1, 2, 3]
[1, 2, 3, 4]
[1, 2, 3, 4, 5]
import doctest
doctest.testmod(verbose=True) # with details
Trying:
bubble_sort([3, 4, 7, -1, 2, 5])
Expecting:
[-1, 2, 3, 4, 5, 7]
**********************************************************************
File "__main__", line 17, in __main__.bubble_sort_r
Failed example:
bubble_sort([3, 4, 7, -1, 2, 5])
Exception raised:
Traceback (most recent call last):
File "/opt/hostedtoolcache/Python/3.8.15/x64/lib/python3.8/doctest.py", line 1336, in __run
exec(compile(example.source, filename, "single",
File "<doctest __main__.bubble_sort_r[0]>", line 1, in <module>
bubble_sort([3, 4, 7, -1, 2, 5])
NameError: name 'bubble_sort' is not defined
Trying:
bubble_sort([])
Expecting:
[]
**********************************************************************
File "__main__", line 19, in __main__.bubble_sort_r
Failed example:
bubble_sort([])
Exception raised:
Traceback (most recent call last):
File "/opt/hostedtoolcache/Python/3.8.15/x64/lib/python3.8/doctest.py", line 1336, in __run
exec(compile(example.source, filename, "single",
File "<doctest __main__.bubble_sort_r[1]>", line 1, in <module>
bubble_sort([])
NameError: name 'bubble_sort' is not defined
Trying:
bubble_sort([5, 4, 3, 2, 1])
Expecting:
[1, 2, 3, 4, 5]
**********************************************************************
File "__main__", line 21, in __main__.bubble_sort_r
Failed example:
bubble_sort([5, 4, 3, 2, 1])
Exception raised:
Traceback (most recent call last):
File "/opt/hostedtoolcache/Python/3.8.15/x64/lib/python3.8/doctest.py", line 1336, in __run
exec(compile(example.source, filename, "single",
File "<doctest __main__.bubble_sort_r[2]>", line 1, in <module>
bubble_sort([5, 4, 3, 2, 1])
NameError: name 'bubble_sort' is not defined
2 items had no tests:
__main__
__main__.bubble_to_end
**********************************************************************
1 items had failures:
3 of 3 in __main__.bubble_sort_r
3 tests in 3 items.
0 passed and 3 failed.
***Test Failed*** 3 failures.
TestResults(failed=3, attempted=3)
The time complexity of the bubble sort algorithm is \(n^2\) worst case.
The next cell shows the iterative version of bubble sort, it has the same time complexity.
from typing import List
def bubble_sort(unsorted : List[any]) -> List[any]:
"""sorts a list in a non-recursive way
>>> bubble_sort([3, 4, 7, -1, 2, 9, 5])
[-1, 2, 3, 4, 5, 7, 9]
>>> bubble_sort([])
[]
>>> bubble_sort([6, 5, 4, 3, 2, 1])
[1, 2, 3, 4, 5, 6]
"""
offset : int = 1
swapped : bool = True
while swapped: #Non-terminating loop
swapped = False
#move the biggest element to the end of the list
for i in range(len(unsorted)-offset):
if unsorted[i] > unsorted[i+1]:
unsorted[i], unsorted[i+1] = unsorted[i+1], unsorted[i] #swap
swapped = True
# you can ignore the last element(s) because they are sorted
offset += 1
#print(unsorted)
#print(offset)
return unsorted
print(bubble_sort([4,3,5,2,1]))
[1, 2, 3, 4, 5]
doctest.testmod(verbose=True) # with details
Trying:
bubble_sort([3, 4, 7, -1, 2, 9, 5])
Expecting:
[-1, 2, 3, 4, 5, 7, 9]
ok
Trying:
bubble_sort([])
Expecting:
[]
ok
Trying:
bubble_sort([6, 5, 4, 3, 2, 1])
Expecting:
[1, 2, 3, 4, 5, 6]
ok
Trying:
bubble_sort([3, 4, 7, -1, 2, 5])
Expecting:
[-1, 2, 3, 4, 5, 7]
ok
Trying:
bubble_sort([])
Expecting:
[]
ok
Trying:
bubble_sort([5, 4, 3, 2, 1])
Expecting:
[1, 2, 3, 4, 5]
ok
2 items had no tests:
__main__
__main__.bubble_to_end
2 items passed all tests:
3 tests in __main__.bubble_sort
3 tests in __main__.bubble_sort_r
6 tests in 4 items.
6 passed and 0 failed.
Test passed.
TestResults(failed=0, attempted=6)
import random
from typing import List
i : int = 0
rdlst : List[int] = []
while i < 10000:
rdnr : int = random.randint(0,1000000)
if rdnr not in rdlst:
rdlst = rdlst + [rdnr]
i += 1
#print(rdlst)
Again some timing measurements.
import time
org_lst = rdlst.copy()
t1 = time.perf_counter()
lst2 : List[int] = bubble_sort(rdlst)
t2 = time.perf_counter()
print("The binary search code took {:.2f}ms".format((t2 - t1) * 1000))
The binary search code took 12264.34ms
Insertion Sort#
The second algorithm that will be discussed is insertion sort.
The basic idea of insertion sort is to move the smaller elements in front of bigger elements.
We will use a list of elements for which the comparison operator > is defined.
Suppose we have to sort the list [4, 3, 5, 2, 1].
In the first step the element 3 will be inserted before the 4 in the list, giving [3, 4, 5, 2, 1]. This is done by storing the value 3 and copying the 4 to the place of the 3, the intermediate result is: [4, 4, 5, 2, 1]. Now the original 4 is replaced by 3, giving [3, 4, 5, 2, 1].
In the second step the first 3 elements 3, 4, 5 are sorted and next element 2 must be inserted before the 3. This is done by storing the value 2 and copying the first 3 elements one position to the right, the intermediate result is: [3, 3, 4, 5, 1].Now the original 3 is replaced by 3, giving [2, 3, 4, 5, 1].
In the third and final step the first 4 elements 2, 3, 4, 5 are sorted and next element 1 must be inserted before the 2. This is done by storing the value 1 and copying the first 4 elements one position to the right, the intermediate result is: [2, 2, 3, 4, 5].Now the original 2 is replaced by 1, giving [1, 2, 3, 4, 5].
The next cell shows a version of insertion sort.
from typing import List
def insertion_sort(unsorted: List[any]) -> List[any]:
"""sorts the list by inserting the at the right position in the list
>>> insertion_sort([3, 4, 7, -1, 2, 9, 5])
[-1, 2, 3, 4, 5, 7, 9]
>>> insertion_sort([])
[]
>>> insertion_sort([6, 5, 4, 3, 2, 1])
[1, 2, 3, 4, 5, 6]
"""
for index in range(1, len(unsorted)):
currentvalue : any = unsorted[index]
position : int = index
# print(unsorted)
# shift elements that are greater than the "current value" to the right and
# create an "open" slot in the list to insert the "current value".
while position > 0 and unsorted[position-1] > currentvalue:
unsorted[position] = unsorted[position-1]
position -= 1
#print(unsorted)
unsorted[position] = currentvalue
return unsorted
alist = [54,26,93,17,77,31,44,55,20]
sortedList = insertion_sort(alist)
print(sortedList)
[17, 20, 26, 31, 44, 54, 55, 77, 93]
import doctest
doctest.testmod(verbose=True) # with details
Trying:
bubble_sort([3, 4, 7, -1, 2, 9, 5])
Expecting:
[-1, 2, 3, 4, 5, 7, 9]
ok
Trying:
bubble_sort([])
Expecting:
[]
ok
Trying:
bubble_sort([6, 5, 4, 3, 2, 1])
Expecting:
[1, 2, 3, 4, 5, 6]
ok
Trying:
bubble_sort([3, 4, 7, -1, 2, 5])
Expecting:
[-1, 2, 3, 4, 5, 7]
ok
Trying:
bubble_sort([])
Expecting:
[]
ok
Trying:
bubble_sort([5, 4, 3, 2, 1])
Expecting:
[1, 2, 3, 4, 5]
ok
Trying:
insertion_sort([3, 4, 7, -1, 2, 9, 5])
Expecting:
[-1, 2, 3, 4, 5, 7, 9]
ok
Trying:
insertion_sort([])
Expecting:
[]
ok
Trying:
insertion_sort([6, 5, 4, 3, 2, 1])
Expecting:
[1, 2, 3, 4, 5, 6]
ok
2 items had no tests:
__main__
__main__.bubble_to_end
3 items passed all tests:
3 tests in __main__.bubble_sort
3 tests in __main__.bubble_sort_r
3 tests in __main__.insertion_sort
9 tests in 5 items.
9 passed and 0 failed.
Test passed.
TestResults(failed=0, attempted=9)
import time
rdlst = org_lst.copy()
t1 = time.perf_counter()
lst1 : List[int] = bubble_sort(rdlst)
t2 = time.perf_counter()
print("The binary search code took {:.2f}ms".format((t2 - t1) * 1000))
rdlst = org_lst.copy()
t1 = time.perf_counter()
lst2 : List[int] = insertion_sort(rdlst)
t2 = time.perf_counter()
print("The insertion search code took {:.2f}ms".format((t2 - t1) * 1000))
if lst1 == lst2:
print("lst1 == lst2")
The binary search code took 12385.99ms
The insertion search code took 7040.20ms
lst1 == lst2
Merge Sort#
The third algorithm that will be discussed is merge sort. This algorithm and the next are based on the same idea as the binary_search algorithm. Splitting the list recursively in 2 parts and sort each part and then merge.
The basic idea of merge sort is to split the list in two halves and sort each halves and merge the both into one list again.
We will use again a list of elements for which the comparison operator > is defined.
Suppose we have to sort the list [4, 3, 5, 2, 1].
In the first step the list is splitted into [4, 3] and [5, 2, 1]
In the second step the list [4, 3] is splitted into [4] and [3], and
the resulting two ‘sorted lists’ are merged into [3, 4].
In the third step the list [5, 2, 1] is splitted into [5] and [2, 1].
In the fourth step the list [2, 1] is splitted into [2] and [1], and
the resulting two ‘sorted lists’ are merged into [1, 2].
The list [1, 2] can now be merged with the sorted list [5], resulting in [1, 2, 5].
The list [1, 2, 5] can now be merged with the sorted list [3, 4], resulting in the sorted list [1, 2, 3, 4, 5].
The version of merge sort is a recursive version.
from typing import List
def merging(leftSorted : List[any], rightSorted : List[any]) -> List[any]:
"""both lists into a merged list
"""
sortedList : List[any] = []
i : int = 0
j : int = 0
while i < len(leftSorted) and j < len(rightSorted):
if leftSorted[i] < rightSorted[j]:
sortedList.append(leftSorted[i])
i += 1
else:
sortedList.append(rightSorted[j])
j += 1
if i < len(leftSorted):
sortedList += leftSorted[i:]
if j < len(rightSorted):
sortedList += rightSorted[j:]
# print("Merging ", sortedList)
return sortedList
def merge_sort(unsorted : List[any]) -> List[any]:
"""sorts a list by means of divide and conquer
>>> merge_sort([3, 4, 7, -1, 2, 9, 5])
[-1, 2, 3, 4, 5, 7, 9]
>>> merge_sort([])
[]
>>> merge_sort([6, 5, 4, 3, 2, 1])
[1, 2, 3, 4, 5, 6]
"""
if len(unsorted) > 1:
middle = len(unsorted) // 2
leftUnsorted = unsorted[:middle]
rightUnsorted = unsorted[middle:]
leftSorted = merge_sort(leftUnsorted)
rightSorted = merge_sort(rightUnsorted)
return merging(leftSorted, rightSorted)
else:
return unsorted
alist = [54,26,93,17,77,31,44,55,20]
#alist = [4, 3, 5, 2, 1]
print(alist)
sList = merge_sort(alist)
print(sList)
[54, 26, 93, 17, 77, 31, 44, 55, 20]
[17, 20, 26, 31, 44, 54, 55, 77, 93]
import doctest
doctest.testmod(verbose=True) # with details
Trying:
bubble_sort([3, 4, 7, -1, 2, 9, 5])
Expecting:
[-1, 2, 3, 4, 5, 7, 9]
ok
Trying:
bubble_sort([])
Expecting:
[]
ok
Trying:
bubble_sort([6, 5, 4, 3, 2, 1])
Expecting:
[1, 2, 3, 4, 5, 6]
ok
Trying:
bubble_sort([3, 4, 7, -1, 2, 5])
Expecting:
[-1, 2, 3, 4, 5, 7]
ok
Trying:
bubble_sort([])
Expecting:
[]
ok
Trying:
bubble_sort([5, 4, 3, 2, 1])
Expecting:
[1, 2, 3, 4, 5]
ok
Trying:
insertion_sort([3, 4, 7, -1, 2, 9, 5])
Expecting:
[-1, 2, 3, 4, 5, 7, 9]
ok
Trying:
insertion_sort([])
Expecting:
[]
ok
Trying:
insertion_sort([6, 5, 4, 3, 2, 1])
Expecting:
[1, 2, 3, 4, 5, 6]
ok
Trying:
merge_sort([3, 4, 7, -1, 2, 9, 5])
Expecting:
[-1, 2, 3, 4, 5, 7, 9]
ok
Trying:
merge_sort([])
Expecting:
[]
ok
Trying:
merge_sort([6, 5, 4, 3, 2, 1])
Expecting:
[1, 2, 3, 4, 5, 6]
ok
3 items had no tests:
__main__
__main__.bubble_to_end
__main__.merging
4 items passed all tests:
3 tests in __main__.bubble_sort
3 tests in __main__.bubble_sort_r
3 tests in __main__.insertion_sort
3 tests in __main__.merge_sort
12 tests in 7 items.
12 passed and 0 failed.
Test passed.
TestResults(failed=0, attempted=12)
merge sort is more efficient than bubble sort because of the divide-and-conquer strategy, however the creation of intermediate lists may be problematic.
import time
rdlst = org_lst.copy()
t1 = time.perf_counter()
lst1 : List[int] = bubble_sort(rdlst)
t2 = time.perf_counter()
print("The bubble sort took {:.2f}ms".format((t2 - t1) * 1000))
rdlst = org_lst.copy()
t1 = time.perf_counter()
lst2 : List[int] = insertion_sort(rdlst)
t2 = time.perf_counter()
print("The insertion sort took {:.2f}ms".format((t2 - t1) * 1000))
rdlst = org_lst.copy()
t1 = time.perf_counter()
lst3 : List[int] = merge_sort(rdlst)
t2 = time.perf_counter()
print("The merge sort took {:.2f}ms".format((t2 - t1) * 1000))
if lst1 == lst2:
print("lst1 == lst2")
if lst1 == lst3:
print("lst1 == lst3")
The bubble sort took 12355.43ms
The insertion sort took 7047.48ms
The merge sort took 54.30ms
lst1 == lst2
lst1 == lst3
Quicksort#
Quicksort is an algorithm presented by Tony Hoare in 1962. It is like merge sort a recursive algorithm, where the list to be sorted is recursively “split” into 2 parts, sorted and combined again. In contrast to merge sort, where the split is done based on the length of the list, each half is sorted and the results are merged. In case of quicksort the splitting results two parts that can be concatenated. This is possible because a pivot is chosen and the elements of the list are reshuffled in relation to the pivot. Elements smaller than the pivot are moved to left of the pivot, elements greater than the pivot are moved to the right of the pivot.
The challenge is to find the right pivot. The better the pivot the faster the algorithm, because the sublist (left and right of the pivot) will be more or less of the same length.
def partition(arr : List[any], low : int, high : int) -> int:
""" Reshuffles the elements of the list according to a pivot.
The arbitrary chosen pivot is the last element of the list.
The pivot is moved to the "middle" of the list.
>>> L = [1]
>>> partition(L, 0, 0)
0
>>> L = [5, 4, 2, 1, 3]
>>> partition(L, 0, 4)
2
>>> L = [5, 4, 3, 2, 1]
>>> partition(L, 0, 4)
0
"""
i : int = low-1 # index of smaller element
pivot : any = arr[high] # choose a pivot
for j in range(low , high):
# If current element is smaller than or equal to pivot
if arr[j] <= pivot:
# increment index of smaller element and swap elements
i += 1
arr[i],arr[j] = arr[j],arr[i]
# move the pivot to the right position
arr[i+1],arr[high] = arr[high],arr[i+1]
return i+1
# The main function that implements QuickSort
# arr[] --> Array to be sorted,
# low --> Starting index,
# high --> Ending index
# Function to do Quick sort
def quick_sort(arr : List[any], low : int, high : int) -> None:
""" the list is sorted by partition the list in two parts,
a part with elements smaller than a pivot and elements greater
than the pivot.
The partitioned parts are recursively sorted.
>>> L = [3, 4, 7, -1, 2, 5]
>>> quick_sort(L, 0, 5)
>>> L
[-1, 2, 3, 4, 5, 7]
"""
if low < high:
# pi is partitioning index, arr[p] is now
# at right place
pi : int = partition(arr, low, high)
# Separately sort elements before
# partition and after partition
quick_sort(arr, low, pi-1)
quick_sort(arr, pi+1, high)
alist = [54,26,93,17,77,31,44,55,20]
#alist = [4, 3, 5, 2, 1]
print(alist)
quick_sort(alist, 0, len(alist)-1)
print(alist)
[54, 26, 93, 17, 77, 31, 44, 55, 20]
[17, 20, 26, 31, 44, 54, 55, 77, 93]
import doctest
doctest.testmod(verbose=True) # with details
Trying:
bubble_sort([3, 4, 7, -1, 2, 9, 5])
Expecting:
[-1, 2, 3, 4, 5, 7, 9]
ok
Trying:
bubble_sort([])
Expecting:
[]
ok
Trying:
bubble_sort([6, 5, 4, 3, 2, 1])
Expecting:
[1, 2, 3, 4, 5, 6]
ok
Trying:
bubble_sort([3, 4, 7, -1, 2, 5])
Expecting:
[-1, 2, 3, 4, 5, 7]
ok
Trying:
bubble_sort([])
Expecting:
[]
ok
Trying:
bubble_sort([5, 4, 3, 2, 1])
Expecting:
[1, 2, 3, 4, 5]
ok
Trying:
insertion_sort([3, 4, 7, -1, 2, 9, 5])
Expecting:
[-1, 2, 3, 4, 5, 7, 9]
ok
Trying:
insertion_sort([])
Expecting:
[]
ok
Trying:
insertion_sort([6, 5, 4, 3, 2, 1])
Expecting:
[1, 2, 3, 4, 5, 6]
ok
Trying:
merge_sort([3, 4, 7, -1, 2, 9, 5])
Expecting:
[-1, 2, 3, 4, 5, 7, 9]
ok
Trying:
merge_sort([])
Expecting:
[]
ok
Trying:
merge_sort([6, 5, 4, 3, 2, 1])
Expecting:
[1, 2, 3, 4, 5, 6]
ok
Trying:
L = [1]
Expecting nothing
ok
Trying:
partition(L, 0, 0)
Expecting:
0
ok
Trying:
L = [5, 4, 2, 1, 3]
Expecting nothing
ok
Trying:
partition(L, 0, 4)
Expecting:
2
ok
Trying:
L = [5, 4, 3, 2, 1]
Expecting nothing
ok
Trying:
partition(L, 0, 4)
Expecting:
0
ok
Trying:
L = [3, 4, 7, -1, 2, 5]
Expecting nothing
ok
Trying:
quick_sort(L, 0, 5)
Expecting nothing
ok
Trying:
L
Expecting:
[-1, 2, 3, 4, 5, 7]
ok
3 items had no tests:
__main__
__main__.bubble_to_end
__main__.merging
6 items passed all tests:
3 tests in __main__.bubble_sort
3 tests in __main__.bubble_sort_r
3 tests in __main__.insertion_sort
3 tests in __main__.merge_sort
6 tests in __main__.partition
3 tests in __main__.quick_sort
21 tests in 9 items.
21 passed and 0 failed.
Test passed.
TestResults(failed=0, attempted=21)
import time
rdlst = org_lst.copy()
t1 = time.perf_counter()
lst1 : List[int] = bubble_sort(rdlst)
t2 = time.perf_counter()
print("The bubble sort took {:.2f}ms".format((t2 - t1) * 1000))
rdlst = org_lst.copy()
t1 = time.perf_counter()
lst2 : List[int] = insertion_sort(rdlst)
t2 = time.perf_counter()
print("The insertion sort took {:.2f}ms".format((t2 - t1) * 1000))
rdlst = org_lst.copy()
t1 = time.perf_counter()
lst3 : List[int] = merge_sort(rdlst)
t2 = time.perf_counter()
print("The merge sort took {:.2f}ms".format((t2 - t1) * 1000))
rdlst1 = org_lst.copy()
t1 = time.perf_counter()
quick_sort(rdlst1, 0, len(rdlst1)-1)
t2 = time.perf_counter()
print("The quick sort took {:.2f}ms".format((t2 - t1) * 1000))
rdlst2 = org_lst.copy()
t1 = time.perf_counter()
rdlst2.sort()
t2 = time.perf_counter()
print("The python sort took {:.2f}ms".format((t2 - t1) * 1000))
if lst1 == lst2:
print("lst1 == lst2")
if lst1 == lst3:
print("lst1 == lst3")
if lst1 == rdlst1:
print("lst1 == rdlst1")
if lst1 == rdlst2:
print("lst1 == rdlst2")
The bubble sort took 12381.21ms
The insertion sort took 7031.47ms
The merge sort took 55.37ms
The quick sort took 32.63ms
The python sort took 1.64ms
lst1 == lst2
lst1 == lst3
lst1 == rdlst1
lst1 == rdlst2
Do It Yourself!
Use the four functions to sort an array of integers and profile each one of them. Create a copy of the list otherwise you will end up sorting the same list. What is the difference among each algorithm?
lst = [54, 26, 93, 17, 77, 31, 44, 55, 20]
# Remove this line and add your code here
Advice: when writing code always make sure that the code is correct (via testing for instance) before starting optimizing.
- 1
This Jupyter Notebook is based on external content related to algorithms (e.g. searching and sorting).