TL/DR

I recently came across The Last Algorithms Course You'll Need by the mighty ThePrimeagen. And this is it. This is THE course that will satisfy my algorithmic thirst (I will admit I am to dull to enjoy Mr. Knuth's books).

1. Understand

We are given a list of numbers (or any items that can be operands to equality operators). We need to sort this list in ascending order.

The key to Bubble sort is to make sure that every time we iterate over the list, we end up moving/pushin/bubbling the largest (for asc[ending] order) or the lowest (for desc[ending]) element to the end of the list AND forget about it. Then on the next pass our list is n-1 smaller, eventually we run out of things to move, and that is when we have our list sorted.

Here is a drawing of the concept:

2. Plan

Here is a pseudo code:

// use two pointers
// left one works to drag (bubble) values
// right is the boundary btw [unsorted | sorted]
// parts 
list  
left is 0
right is length(list) - 1 
while left < right and right > 1  
    iterate from beginning to right    
        at each step check:    
        if value > next-value then      
            swap them     
        else     
            don't swap them  
    decrement right pointer by one

3. Execute

TypeScript

Solution is straightforward:

export default function bubbleSort(arr: number[]): void {   
    let right = arr.length - 1    
    do {      
        for (let i = 0; i < right; ++i) {        
            if (arr[i] > arr[i+1]) {          
                let temp = arr[i]          
                arr[i] = arr[i+1]          
                arr[i+1] = temp        
            }      
        }      
        right -= 1    
    } while (right > 1)}

The flow of algorithms almost exactly follows the pseudo code (I guess I subconsciously think of Python when I write pseudo code, no offence Python 😂)

The swapping part requires a temp variable so we don't lose the value.

Elixir

With Elixir we need to stop thinking about iterative solution and make things work recursively. The trickiest part for me was the pain of admitting that the iterative solution makes more sense here 😂

To hell with it, let's have two recursions! Since we have two loops in our algorithm, this should do it.

defmodule KataMachineEx.BubbleSort do  

    def sort(list), do: sort(list, [])   
    defp sort([], acc), do: acc  
    defp sort(list, acc) do    
        [head | tail] = sort_list(list)    
        sort(tail, [head | acc])  
    end   

    defp sort_list(list), do: sort_list(list, length(list) - 1)  
    defp sort_list(list, 0), do: list  
    defp sort_list(list, i) do    
        if Enum.at(list, i) > Enum.at(list, i - 1) do      
            # swap      
            temp = Enum.at(list, i)       
            new_list =        
                list        
                |> List.replace_at(i, Enum.at(list, i - 1))        
                |> List.replace_at(i - 1, temp)       
            sort_list(new_list, i - 1)    
        else      
            # don't swap      
            sort_list(list, i - 1)    
        end  
    end
end

One trick that I used here was to walk the list from the right to left (in the reverse order). Simply because adding/removing the first element to Elixir list (which is a linked list) is a cheap operation. So we bubble our sorted values not to the top, but to the bottom 🤔

Shall we then call it a Sediment sort ???

Also, this kinda blows.. the codesize. Admittedly, this is not how I would like to sort my bubbles, so I'll stick with the iterative approach.

4. Review

The algorithm itself is very simple and intuitive, especially once you draw it step by step.

Implementing it with in-place swaps makes it if not fast (O(n*n) is worst case) but memory-friendly (O(n) worst case).

Implementing with via recursion with a immutable linked lists where it's cheap to add/remove values at the beginning adds a bit of trickery.

But hey, who doesn't like to use two recursions for one simple algo?