Bubble Sort

Algorithm

Bubble sort is the simplest sorting algorithm. It works by iterating the input array from the first element to the last, comparing each pair of elements and swapping them if needed. Bubble sort continues its iterations until no more swaps are needed. The algorithm gets its name from the way smaller elements “bubble” to the top of the list.

• Iterate

  • Visit each item in the array from the start to the end.

• Swap

  • If two neighboring items are out of order, swap them.

• Repeat

  • Repeat this process until the array is sorted.

Asymptotic Analysis

• Best

  • O(n) Comparisons and Swaps
  • Array is already sorted, comparisons is $O(n)$ and swaps is zero.

• Average and Worst

  • O(n^2) Comparisons and Swaps

Bubble Sort's O(n^2) average case make s it a poor general-purpose algorithm.

The only significant advantage that bubble sort has over other implementations is that it can detect whether the input list is already sorted or not.

Implementation

void BubbleSort(int A[], int n)
{
    for(int pass = n - 1; pass >= 0; pass--)
    {
        for(int i = 0; i <= pass - 1; i++)
        {
            if(A[i] > A[i+1])
            {
                int temp = A[i];
                A[i] = A[i+1];
                A[i+1] = temp;
            }
        }
    }
}

This Algorithm takes $O(n^{2})$ (even in best case). We can improve it by using one extra flag. No more swaps indicate the completion of sorting. If the list is already sorted, we can use this flag to skip the remaining passes.

void BubbleSortImproved(int A[], int n)
{
    int pass, i, temp, swapped = 1;

    for(pass = n - 1; pass >=0 && swapped; pass--)
    {
        swapped = 0;

        for(i = 0; i <= pass - 1; i++)
        {
            if(A[i] > A[i+1])
            {
                temp = A[i];
                A[i] = A[i+1];
                A[i+1] = temp;
                swapped = 1;
            }
        }
    }
}

This modified version improves the best case of bubble sort to $O(n)$.

Performance

• Worst case complexity : O(n^2)
• Best case complexity (Improved version) : O(n)
• Average case complexity (Basic version) : O(n^2)
• Worst case space complexity : O(1) auxiliary