Sorting Algorithms

counting-sort.py

# Total possible values in array
# Array can only be sorted if it's in range [0, K)
K = 10


def counting_sort(arr):
    counter = [0 for _ in range(K)]
    for a in arr:
        counter[a] += 1

    sorted_arr = []
    for a, count in enumerate(counter):
        sorted_arr += [a] * count

    return sorted_arr


if __name__ == '__main__':
    print(counting_sort([3, 2, 7, 5, 1, 8, 4, 7, 3]))

merge-sort.py

def merge_sort(arr):
    if len(arr) < 2:
        return arr

    mid = len(arr) // 2
    left, right = arr[:mid], arr[mid:]
    sorted_left = merge_sort(left)
    sorted_right = merge_sort(right)

    return merge(sorted_left, sorted_right)


def merge(left, right):
    merged = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1

    while i < len(left):
        merged.append(left[i])
        i += 1
    while j < len(right):
        merged.append(right[j])
        j += 1

    return merged


if __name__ == '__main__':
    print(merge_sort([3, 2, 7, 5, 1, 8, 4, 7, 3]))

quick-select.py

import random

def quick_select(arr, k):  # kth index (0-indexed)
    if len(arr) == 1:
        return arr[0]
    
    left, middle, right = [], [], []
    pivot = random.choice(arr)  # use random element as pivot
    for a in arr:
        if a < pivot:
            left.append(a)
        elif a > pivot:
            right.append(a)
        else:
            middle.append(a)

    if k < len(left):
        return quick_select(left, k)
    elif k < len(left) + len(middle):
        return pivot
    else:
        return quick_select(right, k - len(left) - len(middle))

if __name__ == '__main__':
    nth_smallest = 1
    print(quick_select([3, 2, 7, 5, 1, 8, 4, 7, 3], k=nth_smallest-1))

quick-sort.py

def quick_sort(arr):
    if not arr: return []

    left, middle, right = partition(arr)
    return quick_sort(left) + middle + quick_sort(right)


def partition(arr):
    left, middle, right = [], [], []
    pivot = arr[len(arr) // 2]  # use middle element as pivot
    for a in arr:
        if a < pivot:
            left.append(a)
        elif a > pivot:
            right.append(a)
        else:
            middle.append(a)

    return left, middle, right


if __name__ == '__main__':
    print(quick_sort([3, 2, 7, 5, 1, 8, 4, 7, 3]))

radix-sort.py

def radix_sort(arr):
    # get length of the longest number
    max_len = len(str(max(arr)))
    i = 1
    while i <= max_len:
        buckets = list_to_buckets(arr, i)
        arr = buckets_to_list(buckets)
        i += 1

    return arr


def list_to_buckets(arr, i):
    base = 10
    buckets = [[] for _ in range(base)]
    for a in arr:
        # get i-st digit from last
        digit = (a // (base ** i)) % base
        buckets[digit].append(a)
    return buckets


def buckets_to_list(buckets):
    arr = []
    for bucket in buckets:
        for a in bucket:
            arr.append(a)
    return arr


if __name__ == '__main__':
    print(radix_sort([23, 32, 2000, 57, 15, 91, 78, 45, 71, 131]))