Bubble Sort

Bubble sort is a simple comparison-based algorithm that repeatedly steps through a list, swapping adjacent elements whenever they are out of order. Although not the most efficient for large datasets, it’s an excellent starting point for understanding iterative sorting logic and basic algorithmic thinking.

Example Walk-through

Let’s start with a small array:

[5, 1, 4, 2, 8]

Bubble sort compares each pair of adjacent elements and swaps them if they are in the wrong order. A single pass moves the largest element to the end - like a bubble floating to the surface.

Pass 1

Compare 5 and 1 → swap → [1, 5, 4, 2, 8]
Compare 5 and 4 → swap → [1, 4, 5, 2, 8]
Compare 5 and 2 → swap → [1, 4, 2, 5, 8]
Compare 5 and 8 → in order → [1, 4, 2, 5, 8]

Largest element (8) is now in its final place.

Pass 2

Compare 1 and 4 → in order → [1, 4, 2, 5, 8]
Compare 4 and 2 → swap → [1, 2, 4, 5, 8]
Compare 4 and 5 → in order → [1, 2, 4, 5, 8]

Now 5 is settled.

The algorithm continues until a full pass occurs with no swaps - meaning the list is sorted. Even though this approach does a lot of repeated comparisons, its structure makes it an ideal first sorting algorithm to study: it’s driven by simple repetition, checks, and swaps.

Rust Implementation

Below is a practical, in-place bubble sort implementation in rust. It stops early if the slice is already sorted, which reduces unnecessary passes.

pub fn bubble_sort(arr: &mut [i32]) {
    let mut n = arr.len();
    if n < 2 {
        return;
    }

    loop {
        let mut swapped = false;

        for i in 1..n {
            if arr[i - 1] > arr[i] {
                arr.swap(i - 1, i);
                swapped = true;
            }
        }

        // After each full pass, the last element is guaranteed correctly placed
        n -= 1;

        if !swapped {
            break;
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn it_sorts() {
        let mut input = vec![5, 1, 4, 2, 8];
        bubble_sort(&mut input);
        assert_eq!(input, vec![1, 2, 4, 5, 8]);
    }
}

Example Usage

fn main() {
    let mut values = vec![29, 10, 14, 37, 13];
    bubble_sort(&mut values);
    println!("{:?}", values); // [10, 13, 14, 29, 37]
}

Time and Space Complexity

Bubble sort is easy to understand because it relies on repeated comparison and swapping, but this simplicity comes with an efficiency cost. Its performance depends heavily on how sorted the input is.

Case	Time Complexity	Order of Growth	Reason
Best	O(n)	Linear	If the array is already sorted, the first pass makes no swaps and the algorithm stops immediately.
Average	O(n²)	Quadratic	On a typical unsorted list, each element requires repeated comparison during multiple passes.
Worst	O(n²)	Quadratic	When the data is sorted in reverse order, every adjacent pair must be swapped during every pass.

Space Complexity

Space	Complexity	Order of Growth	Reason
Auxiliary space	O(1)	Constant	Bubble sort modifies the array in-place and uses only a few additional variables.

Great idea - adding a Playground Links section helps readers experiment with the code directly.

Here is a clean, ready-to-paste section that matches the tone and formatting of your existing tutorial style.

Playground Links

If you’d like to experiment with the full implementation, explore variations, or test additional inputs, you can use the interactive playground links below. Each link contains the complete runnable code for this tutorial.

Rust - Bubble Sort

These external playgrounds allow you to:

Modify the algorithm logic
Try different input arrays
Debug step-by-step
Compare behavior with other sorting algorithms