Sorting

Bubble Sort

This is one of the simplest sorting algorithms. It can be implemented in just a few lines.

def bubble_sort(values):
    for i in range(0, N):
        for j in range(i + 1, N):
            if values[i] > values[j]:
                values[i], values[j] = values[j], values[i]

The process can be visualized like this:

Speed:

Quick Sort

This is a more complex algorithm, but it runs faster. It works by recursively pivoting the data:

Define a start/end range (grey)
Pick an pivot value within the range (orange)
Move everything smaller than the pivot left of the pivot (red is active swap)
Move everything greater to the right.
The left recursive problem is the values smaller than the pivot
The right recursive problem is the values greater than the pivot

def quicksort_inplace(arr, low, high):
    if low < high:
        # Partition the array and get the pivot index
        pivot_index = hoare_partition(arr, low, high)
        # Recursively sort elements before and after the pivot
        quicksort_inplace(arr, low, pivot_index)
        quicksort_inplace(arr, pivot_index + 1, high)

def hoare_partition(arr, low, high):
    mid = (low + high) // 2
    pivot = arr[mid]  # Choose the middlde element as the pivot, good choice for rand, sorted, reverse sorted
    i = low - 1
    j = high + 1

    while True:
        # Move `i` to the right until an element greater than or equal to the pivot is found    
        i += 1
        while arr[i] < pivot:
            i += 1

        # Move `j` to the left until an element less than or equal to the pivot is found
        j -= 1
        while arr[j] > pivot:
            j -= 1

        # If pointers have crossed, return the partition index
        if i >= j:
            return j

        arr[i], arr[j] = arr[j], arr[i]
        
quicksort_inplace(values, 0, len(values) - 1)

The process can be visualized like this:

Speed: