Bubble sort

Bubble sort is a simple sorting algorithm. It is very simple for understanding and realization therefore it is considered as a training algorithm. In real applications it is not used since it is not efficient.

Algorithm

Algorithm compares every two items which stands side by side and swapping them if they are in the wrong order. Array of n elements can be sorted within n-1 passes. For example:

First pass:
(4, 3, 1, 2) → (3, 4, 1, 2)
(3, 4, 1, 2) → (3, 1, 4, 2)
(3, 1, 4, 2) → (3, 1, 2, 4)

Second pass:
(3, 1, 2, 4) → (1, 3, 2, 4)
(1, 3, 2, 4) → (1, 2, 3, 4)
(1, 2, 3, 4) → (1, 2, 3, 4)

Third pass:
(1, 2, 3, 4) → (1, 2, 3, 4)
(1, 2, 3, 4) → (1, 2, 3, 4)
(1, 2, 3, 4) → (1, 2, 3, 4)

Implementation

Not optimized

static void BubbleSort(int[] array)
{
    int n = array.Length;
    for (int pass = 1; pass <= n - 1; pass++)
        for (int i = 0; i < n - 1; i++)
            if (array[i] > array[i + 1])
            {
                int temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
            }
}

This is not an optimized implementation of the algorithm. It always does n-1 passes even if the array is sorted already. Complexity of this implementation is O(n²-n)

Pass optimized

static void BubbleSort(int[] array)
{
    int n = array.Length;
    bool swapped;
    do
    {
        swapped = false;
        for (int i = 0; i < n - 1; i++)
            if (array[i] > array[i + 1])
            {
                int temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
                swapped = true;
            }
    } while (swapped);
}

This is pass optimized implementation of the algorithm. Obviously, there is no necessity to do passes if array was sorted or became sorted after one of the passes. So in this implementation there is a flag swapped which signalize whether was swaped elements in the current pass or not. If not then cycle is ended. In the best case, then array is sorted already, complexity of this implementation is O(n). In the worst case, then array sorted by descending, complexity is O(n²).

Other websites

Animated bubble sort