# 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 waydef 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            self.nodelst = 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 > array:            tmp = array            array = array            array = 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.

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

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

#### 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. 