Bubble Sort Algorithm

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.

Key Features

In-place, meaning it doesn't require extra space for sorting.
Stable, meaning the relative order of equal elements is preserved.

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.

Complexity Analysis

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.

Space Complexity

In all cases, space complexity is O(1) because Bubble Sort is an in-place sorting algorithm.

Implementation

We implement bubble sort as a finite state machine with the following states:

#bubble-sort(arr<[u64]>) ⇒ <[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 ) → :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, reverse the accumulator to restore order

:Next(arr, swaps) → :Reverse(arr, [], swaps)

: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

.

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:

sorted:=#bubble-sort(a)