Sorting

Here are implementations of a few array sorting algorithms.

a = list('sortingexample')

1. Selection Sort

• Iteratively put the ith smallest element at ith location from the left.
• We maintain a sorted section from the left.
• In each iteration, we expand the sorted section by swap the smallest element from the unsorted section into the location.

def selection_sort(a):
    n = len(a)
    for i in range(n):
        s = i
        for j in range(i + 1, n):
            if a[j] < a[s]:
                s = j
        a[i], a[s] = a[s], a[i]

2. Bubble Sort

• Iteratively put the ith largest element to ith location from the end.
• We maintain a sorted seciton from the right.
• In each iteration, we compare adjacent pairs of elements and swap larger values to the right until we reach the sorted part.
• Bubble sort can have O(N) best case time complexity, with a bit more code to detect if the array is sorted and terminates early.

def bubble_sort(a):
    n = len(a)
    for i in range(1, n):
        swapped = False
        for j in range(n - i):
            if a[j] > a[j + 1]:
                a[j + 1], a[j] = a[j], a[j + 1]
                swapped = True
        if not swapped: break

3. Insertion Sort

• Iteratively insert new element into the sorted part.
• We maintain a sorted section from the left.
• In each iteration, we sink one new element from the right to the correct location in the sorted part.

def insertion_sort(a):
    n = len(a)
    for i in range(n):
        for j in range(i, 0, -1):
            if a[j] < a[j - 1]:
                a[j - 1], a[j] = a[j], a[j - 1]

4. Merge Sort

• Recursively divide the array into two halves, sort both(recursively) and then merge the two sorted array.
• It follows the Divide-and-Conquer paradigm.

# A quick and dirty non-inplace version
def merge_sort(a):
    def merge(left, right):
        merged = []
        while left and right:
            merged.append(left.pop() if left[-1] > right[-1] else right.pop())
        merged.extend(left + right)
        return merged[::-1]

    if len(a) <= 1: return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    return merge(left, right)

# A in place version
def merge_sort(a):
    temp = a.copy()

    def merge(low, mid, high):
        for i in range(low, high + 1):
            temp[i] = a[i]

        i, j = low, mid + 1
        for k in range(low, high + 1):
            if i > mid:
                a[k] = temp[j]
                j += 1
            elif j > high:
                a[k] = temp[i]
                i += 1
            elif temp[j] < temp[i]:
                a[k] = temp[j]
                j += 1
            else:
                a[k] = temp[i]
                i += 1

    # bottom-up version
    # n = len(a)
    # step_size = 1
    # while step_size < n:
    #     for low in range(0, n, 2 * step_size):
    #         mid = low + step_size - 1
    #         high = min(n - 1, low + 2 * step_size - 1)
    #         merge(low, mid, high)
    #     step_size *= 2

    # # top-down version
    def _merge_sort(low, high):
        if low >= high: return
        mid = (low + high) // 2
        _merge_sort(low, mid)
        _merge_sort(mid + 1, high)
        merge(low, mid, high)

    _merge_sort(0, len(a) - 1)

5. Quick Sort

• Pick a random pivot item, put it in the right place by moving items smaller than it to its left and items larger than it to its right.
• Use the pivot item(since its in the right location now), to cut the problem in two halves and recursively sort the whole thing.

import random

# an inplace implementation, with random pivot item instead of shuffle and alwasy pick leftmost as pivot.
def quick_sort(a):
    def partition(l, h):
        if l >= h: return
        p = random.randint(l, h)
        a[l], a[p] = a[p], a[l]
        pivot = a[l]
        i, j = l, h
        while i < j:
            while i < h and a[i] <= pivot: i += 1
            while j > l and a[j] >= pivot: j -= 1
            if j > i and a[i] > a[j]: a[i], a[j] = a[j], a[i]
        a[j], a[l] = a[l], a[j]
        return j

    def sort(l, h):
        if h > l:
            j = partition(l, h)
            sort(l, j - 1)
            sort(j + 1, h)

    sort(0, len(a) - 1)

6. Heap Sort

• Heapify the array then poping item one at a time.
• See Heap section for how heap works.