sort_algs.py

"""
Good site for sorting algorithm visualization
- https://visualgo.net/en/sorting
"""


__all__ = [
    'bubble_sort', 'insertion_sort', 'selection_sort',
    'quick_sort', 'merge_sort',
]


def bubble_sort(arr: list) -> list:
    """
    Time complexity: O(n^2)
    """
    arr = arr.copy()
    length = len(arr)
    for pivot_idx in range(length-1):
        swapped = False
        for i in range(length-1-pivot_idx):
            if arr[i] > arr[i+1]:
                arr[i], arr[i+1] = arr[i+1], arr[i]
                swapped = True
        if not swapped:
            break
    return arr
      

def insertion_sort(arr: list) -> list:
    """
    Time complexity: O(n^2)
    """
    arr = arr.copy()
    length = len(arr)
    for start_idx in range(1, length):
        for i in range(start_idx, 1-1, -1):
            if arr[i] < arr[i-1]:
                arr[i], arr[i-1] = arr[i-1], arr[i]
            else:
                break
    return arr


def selection_sort(arr: list) -> list:
    """
    Time complexity: O(n^2)
    """
    arr = arr.copy()
    length = len(arr)
    for pivot_idx in range(length-1):
        lowest_idx = pivot_idx
        for idx in range(pivot_idx+1, length):
            if arr[lowest_idx] > arr[idx]:
                lowest_idx = idx
        arr[pivot_idx], arr[lowest_idx] = arr[lowest_idx], arr[pivot_idx]
    return arr


def quick_sort(arr: list) -> list:
    """
    Time complexity
        - Mean:  O(nlogn)
        - Worst: O(n^2)
    """
    if len(arr) <= 1:
        return arr
    
    pivot = arr[0]
    left, right = [], []
    for n in arr[1:]:
        if n < pivot:
            left.append(n)
        else:
            right.append(n)
    
    return quick_sort(left) + [pivot] + quick_sort(right)


def merge_sort(arr: list[int]) -> list[int]:
    if len(arr) <= 1:
        return arr

    pivot_idx = len(arr) // 2
    left = merge_sort(arr[:pivot_idx])
    right = merge_sort(arr[pivot_idx:])
    return _merge(left, right)


def _merge(left: list[int], right: list[int]) -> list[int]:
    merged = []
    l, r = 0, 0
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            merged.append(left[l])
            l += 1
        else:
            merged.append(right[r])
            r += 1

    if len(left) > l:
        merged.extend(left[l:])
    else:
        merged.extend(right[r:])
    return merged


if __name__ == '__main__':
    import random
    
    
    # Create random list has length 10
    tmp_list = random.sample(range(100), 10)
    print(f'* Created random list: {tmp_list.copy()}')

    bubble_sort_result = bubble_sort(tmp_list.copy())
    print(f'- bubble_sort_result: {bubble_sort_result}')
    
    insertion_sort_result = insertion_sort(tmp_list.copy())
    print(f'- insertion_sort_result: {insertion_sort_result}')

    selection_sort_result = selection_sort(tmp_list.copy())
    print(f'- selection_sort_result: {selection_sort_result}')

    quick_sort_result = quick_sort(tmp_list.copy())
    print(f'- quick_sort_result: {quick_sort_result}')

    merge_sort_result = merge_sort(tmp_list.copy())
    print(f'- merge_sort_result: {merge_sort_result}')