Bubble sort

From Wikipedia, the free encyclopedia
Jump to: navigation, search
A bubble sort illustrated

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[change | edit source]

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[change | edit source]

Not optimized[change | edit source]

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(n2-n)

Pass optimized[change | edit source]

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 swapped 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(n2).

Other websites[change | edit source]