3 Implementation of Sorting Algorithms in Python

jagesh maharjan
Aug 14, 2020 · 4 min read
Image for post
Image for post

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.

Image for post
Image for post

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 node
def 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 True
def 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)
Image for post
Image for post

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
Image for post
Image for post

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
Image for post
Image for post

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.

www.delvify.ai

Image for post
Image for post

References:

  1. Introduction to Algorithms 3rd ed [Smith, Judith J, and Dunn, Barbara K]
  2. The Algorithm Design Manual [Skiena, Steven S.]
  3. Algorithms Specialization Offered By Stanford University [Tim Roughgarden]
  4. https://youtu.be/PRKfZSNHyHE
  5. https://youtu.be/PFCXiopbT8Q
  6. https://youtu.be/lh9ypfgKpW4

delvify

Delve into AI at scale with Delvify and drive business growth using the latest advances in AI

jagesh maharjan

Written by

delvify

delvify

Transform your business with our AI powered solutions. We help global brands turn consideration into conversion with intelligent insight-driven Programmatic AI with visual AI solutions for eCommerce.

jagesh maharjan

Written by

delvify

delvify

Transform your business with our AI powered solutions. We help global brands turn consideration into conversion with intelligent insight-driven Programmatic AI with visual AI solutions for eCommerce.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store