Bubble Sort

Bubble Sort sorts a list by comparing two neighbouring values over and over again and swapping them whenever they are in the wrong order. It repeats this until no swap was necessary any more.

It is hardly ever used in practice because it is far too slow. As a starting point it is perfect though: you can see with your own eyes what happens, and it makes clear why an algorithm can take four times as long for twice the data.

One pass walks through the array from left to right:

1. Compare an element with its right neighbour.
2. If the bigger value is on the left, swap the two.
3. Move one position further.

After the first pass the largest value sits at the very right, it has risen like a bubble. That is why the next pass has to check one field less, the one after that two less, and so on.

If a complete pass did not swap anything at all, the list is already sorted and the algorithm stops immediately. For an already sorted list a single pass is enough, and that is exactly the best case of O(n).

public static class BubbleSort
{
    // Sorts the array in place by repeatedly swapping neighbours that are in the wrong order.
    public static void Sort(int[] numbers)
    {
        // Every pass moves the largest remaining value to the end, so the already
        // sorted tail on the right grows by one element per pass.
        for (var pass = 0; pass < numbers.Length - 1; pass++)
        {
            var swapped = false;

            for (var i = 0; i < numbers.Length - 1 - pass; i++)
            {
                if (numbers[i] <= numbers[i + 1])
                    continue;

                (numbers[i], numbers[i + 1]) = (numbers[i + 1], numbers[i]);
                swapped = true;
            }

            // Nothing was swapped during this pass, so the array is already sorted.
            if (!swapped)
                return;
        }
    }
}

var numbers = new[] { 5, 1, 4, 2, 8 };

BubbleSort.Sort(numbers);

Console.WriteLine(string.Join(", ", numbers));

1, 2, 4, 5, 8

• Bubble Sort is stable: equal values keep their original order, because a swap only happens on a real greater than.
• It works in place, so apart from a few variables it needs no extra memory.
• For real work you would use Array.Sort, a highly optimised hybrid that switches strategy depending on the amount of data.

Something to try: remove the early exit with swapped. The result stays correct, but the best case disappears.