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 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)

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.

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