Popular sorting algorithms all build from two facts. 1. That any element is out of place if it’s larger than any other element with a larger index. 2. We grow a sorted subarray by swapping out of order elements.

We need a swap fn()

def swap(a, i, j):
    a[i], a[j] = a[j], a[i]

selection sort: Grow the sorted subarray in the front

Our sorted subarray starts at index 0 and grows to n-1. At each instance, find the smallest element and swap element in place.

def selectionsort(a):
    for sorted_array_idx in range(0, len(a)):
        i = sorted_array_idx
        for j in range(i+1, len(a)):
            if a[j] < a[i]:
                i = j
        swap(a, i, j)

insertion sort: Being more clever about growing the sorted subarray from the front

At any element j, we loop from j to 0 while the loop invariant array[j] < array[j-1] continues to be true. When the invariant is false, the previous swap() puts element j in place in the sorted subarray.

def insertionsort(a):
    for i in range(1, len(array)):
        j = i
        while j > 0 and array[j] < array[j-1]:
            swap(a, j, j-1)
            j -= 1

bubblesort: Grow the sorted subarray at the back

For any element i, we can swap with i+1 if a[i] > a[i+1]. If we loop over an array and swap at each of these conditions, then the last element will be the array’s largest value.

def bubblesort(a):
  SORTED = False
  sorted_array_idx = len(a)-1

  while not SORTED:
    SORTED = True

    for i in range(0, sorted_array_idx):
      if a[i+1] < a[i]:
        swap(a, i, i+1)
        SORTED = False
    sorted_array_idx -= 1

Quicksort: find the absolute index of the first element

All the previous sorting algorithms depend on a sorted subarray index. This is the index we continue to swap until the correct value is in place.

Quicksort uses the unsorted part of an array to find the absolute final place of the sorted subarray index (now called a pivot index). Because the pivot index is in it’s final place. We recurse over the unsorted left/right subarrays.

def quicksort(a, start, end):
    if end <= start:
        return

    pivot_idx = start
    left = start+1
    right = end

    while right >= left:
        if a[left] > a[pivot_idx] 
            and a[right] < a[pivot_idx]:
                swap(a, i, j)
        if a[left] <= a[pivot_idx]:
            i += 1
        if a[right] >= a[pivot_idx]:
            j -= 1
    # this swap places the correct value of j
    # into the pivot index.
    swap(a, pivot_idx, j)

    quicksort(a, start, right-1)
    quicksort(a, right+1, end)