Sorting Algorithms

sorting.py

import time
import os
import random


def main():
    LENGTH = 185
    MAX = 50
    arr = [random.randint(1,MAX) for i in range(LENGTH)]
    HeapSort.sort(arr)
    arr = [random.randint(1,MAX) for i in range(LENGTH)]
    MergeSort.sort(arr)
    arr = [random.randint(1,MAX) for i in range(LENGTH)]
    QuickSort.sort(arr)


class HeapSort:
    
    @staticmethod
    def _heapify_max(arr: [], root_index, length):
        ArrayPrinter.print_arr(arr)
        max_index = root_index
        left_index = root_index * 2 + 1
        right_index = root_index * 2 + 2

        if left_index < length and arr[left_index] > arr[max_index]: max_index = left_index
        if right_index < length and arr[right_index] > arr[max_index]: max_index = right_index

        if max_index != root_index:
            swap(arr, root_index, max_index)
            HeapSort._heapify_max(arr, max_index, length)

    @staticmethod
    def sort(arr: []):
        length = len(arr)
        for i in range(length // 2 - 1, -1, -1):
            HeapSort._heapify_max(arr, i, length)


        for i in range(length-1, 0, -1):
            swap(arr, 0, i)
            HeapSort._heapify_max(arr, 0, i)


class MergeSort:
    
    @staticmethod
    def _merge(arr, arr_l, arr_r) -> None:
        i = j = k = 0
        while i < len(arr_l) and j < len(arr_r):
            if arr_l[i] < arr_r[j]:
                arr[k] = arr_l[i]
                ArrayPrinter.print_arr(arr)
                i+=1
                k+=1
            else:
                arr[k] = arr_r[j]
                ArrayPrinter.print_arr(arr)
                j+=1
                k+=1
        
        while i < len(arr_l):
            arr[k] = arr_l[i]
            ArrayPrinter.print_arr(arr)
            i+=1
            k+=1
            
        while j < len(arr_r):
            arr[k] = arr_r[j]
            ArrayPrinter.print_arr(arr)
            j+=1
            k+=1

    @staticmethod
    def sort(arr: []) -> list[int]:
        if len(arr) > 1:
            mid = len((arr)) // 2
            arr_l = arr[:mid]
            arr_r = arr[mid:]
            MergeSort.sort(arr_l)
            MergeSort.sort(arr_r)
            MergeSort._merge(arr, arr_l, arr_r)


class QuickSort:

    @staticmethod
    def _partition(arr, low, high):
        pivot = arr[high]
        i = low-1
        for j in range(low, high):
            if arr[j] <= pivot:
               i += 1
               swap(arr, j, i)
        i += 1
        swap(arr, i, high)
        return i
    
    @staticmethod
    def sort(arr, low=0, high=None):
        if high is None: high = len(arr) - 1
        if low < high:
            pivot_index = QuickSort._partition(arr, low, high)
            QuickSort.sort(arr, low, pivot_index-1)
            QuickSort.sort(arr, pivot_index+1, high)

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]
    ArrayPrinter.print_arr(arr)
            
class ArrayPrinter:

    @staticmethod
    def print_arr(arr:[], delay_seconds=0.03):
        os.system('cls' if os.name == 'nt' else 'clear')
        high = max(arr)
        low = min(arr)
        width = len(arr)
        lines = []
        for y in range(high, low-2, -1):
            line = ''
            for x in range(width):
                if y < arr[x]: line+='❚'
                else: line+=' '
            lines.append(line)
        print('\n'.join(lines))
        time.sleep(delay_seconds)


if __name__ == '__main__': main()