3 Implementation of Sorting Algorithms in Python
The three most popular yet underrated algorithms in computer science are Heap Sort, Merge Sort, and QuickSort. It seems quite contradictory, how could something be popular yet underrated? That’s exactly what will be explained. Almost all CS students have studied and learned these three algorithms with Sudo code but only few implement them. This is probably because we take care of algorithms and the running time of these sorting algorithms in comparison to implementation.
There are a mass number of materials and references to get into the details of Sudo code and runtime. The implementation part will be more focused on in comparison to the algorithm in this article and Python will be used for the implementation.
Let’s implement Heap Sort algorithm in Python. Note* heap can be min-heap or max-heap. Here, we shall focus on min-heap but this works for both except you need to change operator ‘<’ to ‘>’ or vice-versa where necessary.
import math
# You cannot add any items to the heap after you start deleting the nodedef check_min_index(nodelst, child_index_1, child_index_2):
if nodelst[child_index_1] >= nodelst[child_index_2]:
return child_index_2
if nodelst[child_index_1] < nodelst[child_index_2]:
return child_index_1# Recursive way
def check_bubble_up(nodelst, index):
if index == 0:
return True
parent = math.floor(index/2)
if nodelst[parent] > nodelst[index]:
tmp = nodelst[index]
nodelst[index] = nodelst[parent]
nodelst[parent] = tmp
check_bubble_up(nodelst, parent)
return True
# iterative way
# def check_bubble_up(nodelst, index):
# while index != 0:
# parent = math.floor(index/2)
# if nodelst[parent] > nodelst[index]:
# tmp = nodelst[index]
# nodelst[index] = nodelst[parent]
# nodelst[parent] = tmp
# index = parent
# return Truedef check_bubble_down(nodelst, cur_idx, last_idx):
if last_idx == cur_idx:
return True
child_index_1 = 2 * cur_idx + 1
child_index_2 = 2 * cur_idx + 2
if (child_index_1 >= last_idx) and (child_index_1 > last_idx):
return True
if (child_index_1 <= last_idx) and (child_index_1 >= last_idx):
min_idx = child_index_1
if nodelst[cur_idx] > nodelst[min_idx]:
tmp = nodelst[cur_idx]
nodelst[cur_idx] = nodelst[min_idx]
nodelst[min_idx] = tmp
check_bubble_down(nodelst, min_idx, last_idx)
else:
min_idx = check_min_index(nodelst, child_index_1, child_index_2)
if nodelst[cur_idx] > nodelst[min_idx]:
tmp = nodelst[cur_idx]
nodelst[cur_idx] = nodelst[min_idx]
nodelst[min_idx] = tmp
check_bubble_down(nodelst, min_idx, last_idx)class Heap:
def __init__(self):
self.nodelst = []
self.last_pos = -1
def add_node(self, node):
self.nodelst.append(node)
self.last_pos += 1
check_bubble_up(self.nodelst, len(self.nodelst)-1)
def delete_node(self):
heap_size = len(self.nodelst)
if heap_size != 0:
tmp = self.nodelst[0]
self.nodelst[0] = self.nodelst[self.last_pos]
self.nodelst[self.last_pos] = tmp
self.last_pos -= 1
check_bubble_down(self.nodelst, 0, self.last_pos)
Video Tutorial:
Merge Sort is implemented below:
def mergesort(array, i, l):
if array == []:
return False
if len(array) == 2:
if array[0] > array[1]:
tmp = array[0]
array[0] = array[1]
array[1] = tmp
return array
else:
return array
if len(array) == 1:
return array
else:
mid = (i + len(array))//2
return merge(mergesort(array[i:mid], i, mid), mergesort(array[mid:l], i, mid+1))
def merge(arr1, arr2):
if (arr1 != None) or (arr2 != None):
new_arr = []
i = 0
j = 0
while ((i < len(arr1)) and (j < len(arr2))):
if (arr1[i] > arr2[j]):
new_arr.append(arr2[j])
j += 1
if j >= len(arr2):
while(i < len(arr1)):
new_arr.append(arr1[i])
i += 1
elif arr1[i] <= arr2[j]:
new_arr.append(arr1[i])
i += 1
if i >= len(arr1):
while (j < len(arr2)):
new_arr.append(arr2[j])
j += 1
return new_arr
Video tutorial:
And the last one is QuickSort:
def quick_sort(given, min, max):
if given == None or len(given) == 0:
return False
if min > max:
return False
mid = min + (max-min)//2
pivot = given[mid]
i = min
j= max
while (i < j):
while (given[i] < pivot):
i += 1
while (given[j] > pivot):
j -= 1
if (i <= j):
tmp = given[j]
given[j] = given[i]
given[i] = tmp
i += 1
j -= 1
if (min < j):
quick_sort(given, min, j)
if max > i:
quick_sort(given, i, max)
return given
Video tutorial:
The video tutorials will give you a step-by-step overview of how to implement the three algorithms. As shown, they are very powerful and bear several qualities of computation algorithms. They pose the divide and conquer strategies as well as the greedy method. The theoretical concepts behind these algorithms are cited below to get a detailed explanation of the runtime complexity of the algorithms.
Ready To Know More?
Get in touch with our team of experts to find out how we can help you build predictive AI solutions for your business.
References:
- Introduction to Algorithms 3rd ed [Smith, Judith J, and Dunn, Barbara K]
- The Algorithm Design Manual [Skiena, Steven S.]
- Algorithms Specialization Offered By Stanford University [Tim Roughgarden]
- https://youtu.be/PRKfZSNHyHE
- https://youtu.be/PFCXiopbT8Q
- https://youtu.be/lh9ypfgKpW4