Selection sort, Insertion sort, Shell sort, Merge sort, Quick sort (+in-place), Radix sort

sort_algorithms.py

def selection_sort(arr):
    """
    Is named selection sort, because we are selecting smallest element each time and putting it as next
    Time Complexity - O(N**2)
    Space Complexity - O(1)
    12.471 seconds for 10_000 numbers
    """
    t = mn = 0
    for i in range(len(arr)):
        mn = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[mn]:
                mn = j
        if mn != i:
            t = arr[i]
            arr[i] = arr[mn]
            arr[mn] = t
    return arr


def insertion_sort(arr):
    """
    Thinking where to place each element - while it is smaller than it's left element we are swapping them
    Time Complexity - O(N) for best case and O(N**2) for worst case
    Space Complexity - O(1)
    12.442 seconds for 10_000 numbers
    """
    for i in range(len(arr)):
        j = i
        while j and arr[j] < arr[j - 1]:
            t = arr[j]
            arr[j] = arr[j - 1]
            arr[j - 1] = t
            j -= 1
    return arr


def shell_sort(arr):
    """
    Time Complexity - O(N) for best case and O(N**2) for worst case
    Space Complexity - O(1)
    12.156 seconds for 10_000 elements - reversed range
    """
    gap = 4  # Setting initial gap
    while gap:
        for i in range(len(arr) - gap):  # Maybe wrong this part
            if arr[i] > arr[i + gap]:
                t = arr[i]
                arr[i] = arr[i + gap]
                arr[i + gap] = t
        gap -= 1
    return insertion_sort(arr)


def merge(a, b):
    r = 0
    res = []
    for l in range(len(a)):
        while r < len(b) and b[r] <= a[l]:
            res.append(b[r])
            r += 1
        res.append(a[l])
    while r < len(b):
        res.append(b[r])
        r += 1
    return res


def merge_sort(arr, l=None, r=None):
    """
    Sort half of the array and then merge results
    Time Complexity - O(N*log(N))
    Space Complexity - O(N*log(N))
    0.074 seconds for 10_000 numbers
    """
    if r is None:
        l = 0
        r = len(arr) - 1
    length = r - l + 1
    if length == 1:
        res = arr[l:r + 1]
    elif length == 2:
        if arr[l] > arr[r]:
            res = arr[r:l - 1:-1] if l else arr[r::-1]
        else:
            res = arr[l:r + 1]
    else:
        mid = (r + l) // 2
        lf = merge_sort(arr, l, mid)
        rg = merge_sort(arr, mid + 1, r)
        res = merge(lf, rg)
    return res


def quick_sort(arr):
    """
    Pick a pivot point and move all smaller elements to the left and bigger elements to the right.
    Splitting array every time, so time complexity is O(N*log(N))
    Space complexity - O(N*log(N))
    """
    if len(arr) <= 1:
        return arr
    mid = (len(arr) - 1) // 2
    lh = []
    rh = []
    for i in range(len(arr)):
        if i != mid:
            if arr[i] <= arr[mid]:
                lh.append(arr[i])
            else:
                rh.append(arr[i])
    lh = quick_sort(lh)
    rh = quick_sort(rh)
    lh.append(arr[mid])
    return lh + rh


def quick_sort_inplace(arr, l=None, r=None):
    """
    Moving pivot element to the right, replacing elements and them moving the pivot element back
    Time complexity - O(N*log(N)) - worst case will be O(N**2)
    Space complexity - O(1)
    """
    if r is None:
        l = 0
        r = len(arr) - 1
    if l >= r:
        return
    mid = (l + r) // 2
    arr[mid], arr[r] = arr[r], arr[mid]
    ls = l
    for i in range(l, r):
        if arr[i] < arr[r]:
            arr[i], arr[ls] = arr[ls], arr[i]
            ls += 1
    arr[r], arr[ls] = arr[ls], arr[r]
    quick_sort_inplace(arr, l, ls - 1)
    quick_sort_inplace(arr, ls + 1, r)
    return arr


def radix_sort(arr):
    """
    Time complexity - O(N*max_length_of_number)
    In theory is a good algorithm but in practice has problems - copying data
    0.099 seconds for 10_000 numbers in descending order
    """
    mem = [[] for _ in range(10)]
    depth = 1
    while True:
        working = False
        for num in arr:
            n = num // depth
            if n:
                working = True
            e = n % 10
            mem[e].append(num)
        if not working:
            break
        depth *= 10
        # Aggregating
        i = 0
        for ind, bn in enumerate(mem):
            for j in bn:
                arr[i] = j
                i += 1
            # bn.clear()  # This way is slowed
            mem[ind] = []

    return arr


# print(radix_sort([10, 9, 2, 100, 8]))
radix_sort(list(range(10000, -1, -1)))
# sorted(list(range(100000, -1, -1)))