Sorting algorithm in Python
Selection sort
The selection sort algorithm sorts array by repeatedly finding the minimum element from the unsorted subarray and moving it to the sorted subarray.
For ascending order, we can implement the algorithm as below.
def selection_sort(my_list):
for i in range(len(my_list) - 1):
min_idx = i
for j in range(i + 1, len(my_list)):
if my_list[j] < my_list[min_idx]:
min_idx = j
# swap the minimum element with the current element
temp = my_list[i]
my_list[i] = my_list[min_idx]
my_list[min_idx] = temp
test_list_1 = [4, 3, 2, 10, 12, 1, 5, 6]
selection_sort(test_list_1)
print(test_list_1)
# Time complexity: O(n^2)
# Space complexity: O(1)
The following steps elaborate how it works. The left arrow indicates the current element position and the right arrow indicates the minimum element position in the unsorted sublist.
i=0: [1, 3, 2, 10, 12, 4, 5, 6]
^ ^
i=1: [1, 2, 3, 10, 12, 4, 5, 6]
^ ^
i=2: [1, 2, 3, 10, 12, 4, 5, 6]
^^
i=3: [1, 2, 3, 4, 12, 10, 5, 6]
^ ^
i=4: [1, 2, 3, 4, 5, 10, 12, 6]
^ ^
i=5: [1, 2, 3, 4, 5, 6, 12, 10]
^ ^
i=6: [1, 2, 3, 4, 5, 6, 10, 12]
^ ^
Insertion sort
Just like playing a card game, to re-organize the cards, we pick an element from the unsorted sublist(on the right side), search a spot backwards from the sorted sublist(on the left side), and insert the element by shifting greater elements to the right.
def insert_sort(my_list):
# pick an element from the unsorted sublist [i:n-1]
for i in range(1, len(my_list)):
current = my_list[i]
# search a spot in the sorted sublist [0:i-1]
j = i - 1
while j >= 0:
if my_list[j] > current:
my_list[j + 1] = my_list[j]
j -= 1
else:
break
# insert the current element to the spot
my_list[j + 1] = current
test_list_2 = [4, 3, 2, 10, 12, 1, 5, 6]
insert_sort(test_list_2)
print(test_list_2)
# Time complexity: O(n^2)
# Space complexity: O(1)
The following steps elaborate how it works. The left arrow indicates where to insert and the right arrow indicates the current picked unsorted element.
i=1: [3, 4, 2, 10, 12, 1, 5, 6]
^ ^
i=2: [2, 3, 4, 10, 12, 1, 5, 6]
^ ^
i=3: [2, 3, 4, 10, 12, 1, 5, 6]
^^
i=4: [2, 3, 4, 10, 12, 1, 5, 6]
^^
i=5: [1, 2, 3, 4, 10, 12, 5, 6]
^ ^
i=6: [1, 2, 3, 4, 5, 10, 12, 6]
^ ^
i=7: [1, 2, 3, 4, 5, 6, 10, 12]
^ ^
Bubble sort
Bubble sort repeatedly swapping the adjacent elements if they are in wrong order.
def bubble_sort(my_list):
n = len(my_list)
# bubble up the maximum element for each round, totally (n-1) rounds
for i in range(n - 1):
swapped = False
# walk through the unsorted sublist [0:n-i-2]
for j in range(n - i - 1):
# bubble up if the current item is greater
if my_list[j] > my_list[j + 1]:
temp = my_list[j]
my_list[j] = my_list[j + 1]
my_list[j + 1] = temp
swapped = True
# already sorted
if not swapped:
break
test_list_3 = [4, 3, 2, 10, 12, 1, 5, 6]
bubble_sort(test_list_3)
print(test_list_3)
# Time complexity: O(n^2)
# Space complexity: O(1)
The following steps elaborate how it works.
i=0: [3, 4, 2, 10, 12, 1, 5, 6]
[3, 2, 4, 10, 12, 1, 5, 6]
[3, 2, 4, 10, 12, 1, 5, 6]
[3, 2, 4, 10, 12, 1, 5, 6]
[3, 2, 4, 10, 1, 12, 5, 6]
[3, 2, 4, 10, 1, 5, 12, 6]
[3, 2, 4, 10, 1, 5, 6, 12]
^
i=1: [2, 3, 4, 10, 1, 5, 6, 12]
[2, 3, 4, 10, 1, 5, 6, 12]
[2, 3, 4, 10, 1, 5, 6, 12]
[2, 3, 4, 1, 10, 5, 6, 12]
[2, 3, 4, 1, 5, 10, 6, 12]
[2, 3, 4, 1, 5, 6, 10, 12]
^
i=2: [2, 3, 4, 1, 5, 6, 10, 12]
[2, 3, 4, 1, 5, 6, 10, 12]
[2, 3, 1, 4, 5, 6, 10, 12]
[2, 3, 1, 4, 5, 6, 10, 12]
[2, 3, 1, 4, 5, 6, 10, 12]
^
i=3: [2, 3, 1, 4, 5, 6, 10, 12]
[2, 3, 1, 4, 5, 6, 10, 12]
[2, 1, 3, 4, 5, 6, 10, 12]
[2, 1, 3, 4, 5, 6, 10, 12]
^
i=4: [2, 1, 3, 4, 5, 6, 10, 12]
[1, 2, 3, 4, 5, 6, 10, 12]
[1, 2, 3, 4, 5, 6, 10, 12]
^
i=5: [1, 2, 3, 4, 5, 6, 10, 12]
[1, 2, 3, 4, 5, 6, 10, 12]
^
For loop ends early since there is no swap in this round!
Merge sort
Merge sort is Divide-and-Conquer algorithm. It divides list into two halves, recursively calls itself, and then merges the two sorted halves. The merge function is the key process for the merging two halves.
def merge_sort(my_list, low, high):
if low < high:
mid = int((low + high) / 2)
# sort each half of list
merge_sort(my_list, low, mid)
merge_sort(my_list, mid + 1, high)
# merge the sorted two halves
merge(my_list, low, mid, high)
def merge(my_list, low, mid, high):
n1 = mid - low + 1
n2 = high - mid
# temporary list to store each half of list
my_list1 = [None] * n1
my_list2 = [None] * n2
for i in range(n1):
my_list1[i] = my_list[low + i]
for i in range(n2):
my_list2[i] = my_list[mid + 1 + i]
# merge the two halves using running pointers on each half
i = j = 0
k = low
while i < n1 and j < n2:
if my_list1[i] < my_list2[j]:
my_list[k] = my_list1[i]
i += 1
else:
my_list[k] = my_list2[j]
j += 1
k += 1
# merge the remaining items from each sorted list
while i < n1:
my_list[k] = my_list1[i]
i += 1
k += 1
while j < n2:
my_list[k] = my_list2[j]
j += 1
k += 1
test_list_4 = [4, 3, 2, 10, 12, 1, 5, 6]
merge_sort(test_list_4, 0, len(test_list_4) - 1)
print(test_list_4)
The following process simulates how it works.
1. [4, 3, 2, 10, 12, 1, 5, 6]
2. [4,3,2,10] [12,1,15,6]
3. [4,3] [2,10] [12,1] [15,6]
4. [4] [3] [2] [10] [12] [1] [15] [6]
5. [3,4] [2,10] [1,12] [6,15]
6. [2,3,4,10] [1,6,12,15]
7. [1,2,3,4,6,10,12,15]
# Time complexity: O(n*logn)
# Space complexity: O(n)
Quick sort
Like merge sort, quick sort is also a Divide-and-Conquer algorithm. It picks an element as pivot and partitions the list around the pivot. The pivot can be picked in different ways(first, last, random, or median position). The partition function is the key process. Its target is to put the pivot in the correct position, put all smaller elements to the left, and put all greater elements to the right of it.
def partition(my_list, low, high):
pivot = my_list[high]
curr = low - 1
# move smaller items to the very left
for i in range(low, high):
if my_list[i] < pivot:
curr += 1
temp = my_list[curr]
my_list[curr] = my_list[i]
my_list[i] = temp
# move pivot to the final place
temp = my_list[curr + 1]
my_list[curr + 1] = pivot
my_list[high] = temp
# return pivot index
return curr + 1
def quick_sort(my_list, low, high):
if low < high:
pivot = partition(my_list, low, high)
quick_sort(my_list, low, pivot - 1)
quick_sort(my_list, pivot + 1, high)
test_list_5 = [4, 3, 2, 10, 12, 1, 5, 6]
quick_sort(test_list_5, 0, len(test_list_5) - 1)
print(test_list_5)
# Time complexity: O(n*logn)
# Space complexity: O(n)
The following process simulates how it works.
1. [4, 3, 2, 1, 5] 6 [12, 10]
^
2. [4, 3, 2, 1] 5 6 [12, 10]
^
3. 1 [3, 2, 4] 5 6 [12, 10]
^
4. 1 [3, 2] 4 5 6 [12, 10]
^
5. 1 2 [3] 4 5 6 [12, 10]
^
6. 1 2 [3] 4 5 6 10 [12]
^
Heap sort
Heap sort is a comparison based sorting algorithm based on binary heap. It follows the below idea:
- build a max heap with the given list
- repeat the following steps until the heap contains only one item:
2.1 swap the root of heap with last item in the heap
2.2 remove the last item of the heap which is already sorted to expected position
2.3 heapify the remaining items in the heap
def heapify(my_List, n, i):
largest = i
# get left and right child
l = 2 * i + 1
r = 2 * i + 2
# check if left child exists and greater than parent
if l < n and my_List[largest] < my_List[l]:
largest = l
# check if right child exist and greater than parent
if r < n and my_List[largest] < my_List[r]:
largest = r
# change parent if needed
if largest != i:
# swap parent with largest child
my_List[i], my_List[largest] = my_List[largest], my_List[i]
# heapify the subtree of largest child
heapify(my_List, n, largest)
def heap_sort(my_list):
n = len(my_list)
# 1. build max heap
for i in range(n // 2 - 1, -1, -1):
heapify(my_list, n, i)
# extract one by one
for i in range(n - 1, 0, -1):
# 2.1 swap the root of heap with the last item in the heap
my_list[0], my_list[i] = my_list[i], my_list[0]
# 2.3 heapify the remaining items
heapify(my_list, i, 0)
test_list_6 = [4, 3, 2, 10, 12, 1, 5, 6]
heap_sort(test_list_6)
print(test_list_6)
# Time complexity: O(n*logn)
# Space complexity: O(1)