24. Sorting

A. Bubble sort

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.

def bubble_sort(arr:List[int]) -> List[int]:

    for i in range(len(arr)):
        for j in range(i+1, len(arr)):

            if arr[i] > arr[j]:
                arr[i], arr[j] = arr[j], arr[i]

    return arr

Time complexity O(n^2)
Space complexity O(1)

B. Selection sort

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.

def selection_sort(arr:List[int]) -> List[int]:

    for i in range(len(arr)):

        min_idx = i
        for j in range(i+1, len(arr)):

            if arr[min_idx] > arr[j]:
                min_idx = j

        arr[min_idx], arr[i] = arr[i], arr[min_idx]

    return arr

Time complexity O(n^2)
Space complexity O(1)

C. Merge sort

Merge sort is a divide and conquer algorithm that was invented by John von Neumann in 1945. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.

def merge(a:List[int], b:List[int]) -> List[int]:

    p,q = 0,0
    res = []

    while p < len(a) and q < len(b):

        if a[p] < b[q]:
            res.append(a[p])
            p += 1

        else:
            res.append(b[q])
            q += 1

    while p < len(a):
        res.append(a[p])
        p += 1

    while q < len(b):
        res.append(b[q])
        q += 1

    return res

def merge_sort(arr:List[int]) -> List[int]:

    if len(arr) < 2:
        return arr

    mid = len(arr)//2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid+1:])

    return merge(left, right)

Time complexity O(nlogn)
Space complexity O(n)