basic sorting algorithms

sorting.py

from numbers import Number


def selection_sort(arr: list[Number]) -> list[Number]:
    n = len(arr)
    swap_index = 0
    for start_idx, start_num in enumerate(arr):
        min_num = float('inf')
        for idx in range(start_idx, n):
            num = arr[idx]
            if num < min_num:
                swap_index = idx
                min_num = num
        arr[swap_index], arr[start_idx] = start_num, min_num
    return arr


def swap(arr: list, index1: int, index2: int) -> None:
    arr[index1], arr[index2] = arr[index2], arr[index1]


def bubble_sort(arr: list[Number]) -> list[Number]:
    n = len(arr)
    for idx in range(n):
        # print(f"iteration{idx}")
        for j in range(1, n - idx):
            # print(f"comparing {A[j-1]} and {A[j]}", A[j - 1] > A[j])
            if arr[j - 1] > arr[j]:
                # print(f"swapping {A[j-1]} and {A[j]}")
                swap(arr, j - 1, j)
        # print(A)
    return arr


def insertion_sort(arr: list[Number]) -> list[Number]:
    n = len(arr)
    last_idx = 0
    temp_num = 0
    for idx in range(n):
        temp_num = arr[idx]
        # print(f"at index {idx} with value {temp_num}")
        for pre_idx in range(idx - 1, -1, -1):
            last_idx = pre_idx
            # print(f"at index: {pre_idx}",)
            if arr[pre_idx] > temp_num:
                arr[pre_idx + 1] = arr[pre_idx]  # shift right
            else:
                arr[pre_idx + 1] = temp_num  # insert temp num at the last position
                # print(f"last_idx = {last_idx}")
                break
        else:
            # print(f"else last_idx = {last_idx}")
            arr[last_idx] = temp_num  # insert temp num at the last position
        # print(f"final array", arr)
    # if last_idx < 0:
    #     # print(f"final array when last_idx < 0", last_idx)
    #     arr[last_idx + 1] = temp_num
    return arr


def merge_sort(arr, lo, hi):
    if lo < hi:
        mid = (hi - lo) // 2 + lo
        # print(f"indices: lo={lo}, mid={mid}, hi={hi}")
        left = merge_sort(arr, lo, mid)
        right = merge_sort(arr, mid + 1, hi)
        # print(f"merging", left, right)
        return merge(left, right)
    else:
        return [arr[lo]]


def merge(left: list[Number], right: list[Number]) -> list[Number]:
    len_left = len(left)
    len_right = len(right)
    total_len = len_left + len_right
    left_idx = 0
    right_idx = 0
    arr = []
    # print(f"indices: len_left={len_left}, len_right={len_right}, total_len={total_len}")
    for idx in range(total_len):
        # print(f"when left_idx={left_idx}, right_idx={right_idx}")
        if left_idx < len_left and right_idx < len_right:
            if left[left_idx] <= right[right_idx]:
                arr += [left[left_idx]]
                left_idx += 1
            else:
                arr += [right[right_idx]]
                right_idx += 1
        elif left_idx < len_left:
            arr += [left[left_idx]]
            left_idx += 1
        else:
            arr += [right[right_idx]]
            right_idx += 1
    return arr


import random


def quick_sort(arr):
    """
    Args:
     arr(list_int32)
    Returns:
     list_int32
    """
    size = len(arr)
    quicksort(arr, 0, size - 1)
    return arr


def quicksort(arr: list, lo, hi):
    # recurse base case
    if lo >= hi:
        return

    # recursive case
    # select random pivot between indices
    pivot = random.choice(arr[lo:hi + 1])
    for pivot_idx in range(lo, hi+1):
        if arr[pivot_idx] == pivot:
            break

    # print(f"starting lo={lo}, hi={hi} pivot_idx={pivot_idx}")
    # swap with first index
    swap(arr, lo, pivot_idx)
    pivot_idx = lo
    pivot = arr[pivot_idx]

    # apply hoare's partioning
    lesser = lo + 1
    bigger = hi
    # print(f"lo={lo}, hi={hi}")
    # print(f"pivot is {pivot} at {pivot_idx}\nlesser idx:{lesser}, bigger idx: {bigger}", arr)
    while lesser <= bigger:
        if arr[lesser] <= pivot:
            lesser += 1
        elif arr[bigger] > pivot:
            bigger -= 1
        else:
            swap(arr, lesser, bigger)
            lesser += 1
            bigger -= 1
        # print(f"lesser idx:{lesser}, bigger idx: {bigger}")
        # print(f"post while", arr)

    if not bigger > pivot_idx:
        quicksort(arr, lo, bigger)
    else:
        swap(arr, pivot_idx, bigger)
        # print(f"after swapping", arr)
        # recurse
        quicksort(arr, lo, bigger - 1)
    quicksort(arr, bigger + 1, hi)


# =============== #
from functools import partial

def heap_sort(arr):
    heap_limit = len(arr)
    partial_swap_call = partial(swap, arr)
    partial_heapify_call = partial(heapify, arr)
    for idx in range(heap_limit - 1, 0, -1):
        partial_heapify_call(parent_key(idx), heap_limit, partial_swap_call)
    
    for idx in range(heap_limit-1, 0, -1):
        partial_swap_call( 0, idx)
        heap_limit -= 1
        partial_heapify_call(0, heap_limit, partial_swap_call)
    return arr


def parent_key(idx):
        return idx // 2 if idx > 0 else 0


def heapify(arr, idx, heap_limit: int, swap_call):
    # swap max child value with value @ idx 
    # and swap child key if needed to trickle down smallest value.
    child_key = -1
    while True:
        left_key = 2 * idx + 1
        right_key = 2 * idx + 2
        child_key = idx
        
        if right_key < heap_limit and arr[right_key] > arr[child_key]:
            child_key = right_key
        if left_key < heap_limit and arr[left_key] > arr[child_key]:
            child_key = left_key
                
        if child_key != idx:
            swap_call(child_key, idx)
            idx = child_key
        else:
            break;
# =============== #


# print(selection_sort([1, 2, 3, 4, 59, 10, 6, 7, 8, -100]))
# print(selection_sort([1, -100]))
# print(selection_sort([-100]))

# print(bubble_sort([1, 2, 3, 4, 59, 10, 6, 7, 8, -100]))
# print(bubble_sort([1, -100]))
# print(bubble_sort([-100]))
#
# print(insertion_sort([1, 2, 3, 4, 59, 10, 6, 7, 8, -100]))
# print(insertion_sort([5, 8, 3, 9, 4, 1, 7]))
# print(insertion_sort([1, -100]))
# print(insertion_sort([-100]))
#
# print(merge_sort([1, 2, 3, 4, 59, 10, 6, 7, 8, -100], 0, 9))
assert insertion_sort([5, 8, 3, 9, 4, 1, 7]) == sorted([5, 8, 3, 9, 4, 1, 7])
assert insertion_sort([1, -100]) == sorted([1, -100])
assert insertion_sort([-100]) == sorted([-100])

assert quick_sort([5, 8, 3, 9, 4, 1, 7]) == sorted([5, 8, 3, 9, 4, 1, 7])
assert quick_sort([1, -100]) == sorted([1, -100])
assert quick_sort([-100]) == sorted([-100])

# import functools

def get_digit_place(radix_system, num_place, num):
    return (num // num_place) % radix_system
    
    
def counting_sort(arr, num_place, radix_system = 10):
    get_digit_partial = functools.partial(get_digit_place, radix_system)
    n = len(arr)
    aux_arr = [0 for _ in range(radix_system)]
    result = [0] * n
    
    for each_num in arr:
        num = get_digit_partial(num_place, each_num)
        aux_arr[num] += 1

    
    for idx in range(1, len(aux_arr)):
        aux_arr[idx] += aux_arr[idx-1]
    
    for each_num in reversed(arr):
        num = get_digit_partial(num_place, each_num)
        result[aux_arr[num] - 1] = each_num
        aux_arr[num] -= 1
    
    return result
        
    
def radix_sort(arr):
    min_num = 0
    max_num = max(arr)
    is_neg = False
    
    if min_num < 0:
        min_num = min(arr)
        is_neg = True
    
    if is_neg:
        for idx, num in enumerate(arr):
            arr[idx] = num - min_num
    
    place = 1
    while max_num//place > 0:
        arr = counting_sort(arr, place)
        place *= 10
    
    for idx, num in enumerate(arr):
        arr[idx] = num + min_num
    
    return arr
    
    
    
res = radix_sort([91374, 3241, 99999, 124315, 0, 0, 99999])
assert res == [0, 0, 3241, 91374, 99999, 99999, 124315]