Bubble Sorting

Bubble sort is one of the simple sorting algorithms and also popularly known as a Brute Force Approach. The logic of the algorithm is very simple as it works by repeatedly iterating through a list of elements, comparing two elements at a time and swapping them if necessary until all the elements are swapped to an order.

For e.g. if we have a list of 10 elements, bubble sort starts by comparing the first two elements in the list. If the second element is smaller than the first element then it exchanges them. Then it compares the current second element with the third element in the list. This continues until the second last and the last element is compared which completes one iteration through the list. By the time it completes the first iteration the largest element in the list comes to the rightmost position.

Image courtesy from Annieink.com

The algorithm gets its name as we start from lowest point and “bubble up” the higher elements to the highest point in the list. We can also follow other approach where we start from highest point and “bubble down” lowest elements in the list. Since it only uses comparisons to operate on elements, it is a comparison sort.

Graphical Example

As we can see in above example the list sorted by third iteration and it is useless to go for 4th and 5th iterations. So we use a flag which determines whether a swap operation is done in last iteration or not. If a swap operation is not done in last iteration we will stop remaining iterations since the list is already in sorted order. For the above example we will stop iterating once third iteration is done as the whole list is sorted by then.

Pseudo-code

procedure bubbleSort( A : list of sortable items )
   repeat     
     swapped = false
     for i = 0 to length(A) - 1 
       if A[i] > A[i+1] then
         swap( A[i], A[i+1] )
         swapped = true
       end if
     end for
   until not swapped
end procedure

Code Snippet

void bubbleSort(int arr[], int numberOfElements) 
{
  char swapped = 1;
  int tmp, i;

  while (swapped) 
    {
      swapped = 0;

      for (i = 0; i < (numberOfElements - 1); i++) 
        {
          if (arr[i] > arr[i + 1]) 
            {
              tmp = arr[i];
              arr[i] = arr[i + 1];
              arr[i + 1] = tmp;
              swapped = 1;
            }
        }
    }
}

As we know, every iteration bubbles up the highest element to the end of the list. So there is no need to compare the same in next iteration. Above logic can be further enhanced by ignoring last n-1 elements when running for the nth iteration.

void bubbleSort(int arr[], int numberOfElements) 
{
  char swapped = 1;
  int numberOfElementsToSwap = numberOfElements;
  int tmp, i;

  while (swapped) 
    {
      swapped = 0;
      numberOfElementsToSwap = numberOfElementsToSwap - 1;

      for (i = 0; i < numberOfElementsToSwap; i++) 
        {
          if (arr[i] > arr[i + 1]) 
            {
              tmp = arr[i];
              arr[i] = arr[i + 1];
              arr[i + 1] = tmp;
              swapped = 1;
            }
        }
    }
}

Complexity Analysis

Worst case performance - \(O(n^2)\)
Best case performance - O(n)
Average case performance - \(O(n^2)\)
Worst case space complexity - O(1) auxiliary

Although bubble sort is one of the simplest sorting algorithms to understand and implement, its \(O(n^2)\) complexity means that its efficiency decreases dramatically on lists of more than a small number of elements. Even among simple \(O(n^2)\) sorting algorithms, algorithms like insertion sort are usually considerably more efficient.

Rabbits and turtles

The positions of the elements in bubble sort plays a large part in determining its performance. Large elements (Rabbits) at the beginning of the list do not pose a problem, as they are quickly swapped. But small elements (Turtle) towards the end, however, move to the beginning extremely slowly. This has led to these types of elements being named rabbits and turtles, respectively.

For e.g. In case of {2, 3, 4, 5, 1} list it takes a complexity of \(O(n^2)\) to sort the list as smallest element (Turtle) 1 is at the end of the list while {6, 2, 3, 4, 5} list takes a complexity of \(O(n)\) to sort the list.

Various efforts have been made to eliminate turtles to improve upon the speed of bubble sort. Cocktail sort achieves this goal fairly well, but it retains \(O(n^2)\) worst-case complexity.