Bubble Sort Algorithm
===============================================================================
1. Algorithm Summary
-------------------------------------------------------------------------------
Bubble Sort is a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.
(1.1) Key Features
- In-place, meaning it doesn't require extra space for sorting.
- Stable, meaning the relative order of equal elements is preserved.
(1.2) Algorithm Steps
- Start from the beginning of the list.
- Compare adjacent elements and swap them if they are in the wrong order.
- Repeat this process for each pair of adjacent elements in the list until no swaps are needed.
2. Complexity Analysis
-------------------------------------------------------------------------------
(2.1) Time Complexity
Best-case: **O(n)** when the list is already sorted.
Average-case and worst-case: **O(n^2)** comparisons and swaps, where n is the number of elements in the list.
(!)> Bubble Sort is not suitable for large datasets due to its quadratic time complexity. It is often used as a teaching tool due to its simplicity, but it's rarely used in practice for real-world applications where efficiency is critical.
(2.2) Space Complexity
In all cases, space complexity is **O(1)** because Bubble Sort is an in-place sorting algorithm.
3. Implementation
-------------------------------------------------------------------------------
We implement bubble sort as a finite state machine with the following states:
#bubble-sort(arr<[u64]>) ⇒ <[u64]> :=
├ :Start(arr<[u64]>)
├ :Pass(arr<[u64]>, acc<[u64]>, swaps<u64>)
├ :Next(arr<[u64]>, swaps<u64>)
├ :Reverse(arr<[u64]>, acc<[u64]>, swaps<u64>)
└ :Done(arr<[u64]>).
#bubble-sort(arr) → :Start(arr)
-- Initialize first pass
:Start(arr) → :Pass(arr, [], 0)
-- Pass: compare adjacent elements and rebuild list in acc
:Pass([a, b | tail], acc, swaps)
├ a > b → :Pass([a | tail], [b | acc], swaps + 1)
└ * → :Pass([b | tail], [a | acc], swaps)
:Pass([x], acc, swaps) → :Next([x | acc], swaps)
:Pass([], acc, swaps) → :Next(acc, swaps)
-- After a pass
:Next(arr, swaps) → :Reverse(arr, [], swaps)
-- Reverse helper to restore order after pass
:Reverse([x | tail], acc, swaps) → :Reverse(tail, [x | acc], swaps)
:Reverse([], acc, 0) → :Done(acc)
:Reverse([], acc, swaps) → :Pass(acc, [], 0)
-- Return the sorted array
:Done(arr) ⇒ arr.
4. Interface
-------------------------------------------------------------------------------
Take a list, a, that's just a list of numbers
a<[u64]> := [4 2 1 3]
We can run the bubble sort algorithm on it:
```mech
sorted := #bubble-sort(a)
```