Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.

An example of bubble sort. Starting from the beginning of the list, compare every adjacent pair, swap their position if they are not in the right order (the latter one is smaller than the former one). After each iteration, one less element (the last one) is needed to be compared until there are no more elements left to be compared.

From the below animation it can be seen that Bubble sort works fastest for nearly sorted array of elements. The time required to sort the elements increases in the order: few unique, reversed and then random.

What are random, nearly sorted, reversed and few unique elements?

  1. Random: {6, 9, 5, 8, 7, 4, 2, 1, 3}
    Here all the elements are arranged in a random fashion.
  2. Nearly sorted: {5, 6, 7, 8, 9, 1, 2, 3, 4}
    The array is nearly sorted. For example, the above array if divided into two, are sorted individually.
  3. Reversed: {9, 8, 7, 6, 5, 4, 3, 2, 1}
    The array elements are reverse sorted and we are supported to sort them in ascending order.
  4. Few Unique: {1, 1, 2, 9, 4, 3, 2, 5, 9, 6}
    The array contains duplicate entries.
Random Nearly Sorted Reversed Few Unique

Key

  1. Black values are sorted.
  2. Gray values are unsorted.
  3. A red triangle marks the algorithm position.

Algorithm

procedure bubbleSort( A : list of sortable items )
   n = length(A)
   repeat 
     for i = 1 to n-1 inclusive do
       /* if this pair is out of order */
       if A[i-1] > A[i] then
         /* swap them */
         swap( A[i-1], A[i] )
       end if
     end for
end procedure

Implementation:

void bubbleSort(int arr[], int n)
{
   int i, j;
   for (i = 0; i < n; i++)
   {
     for (j = 0; j < n-i-1; j++)      
     {         
        if (arr[j] > arr[j+1])
        {
           swap(&arr[j], &arr[j+1]);
        }
     }
   }
}

Optimizing bubble sort

The bubble sort algorithm can be easily optimized by observing that the n-th pass finds the n-th largest element and puts it into its final place. So, the inner loop can avoid looking at the last n-1 items when running for the n-th time:

Algorithm

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

Implementation

void bubbleSort(int arr[], int n)
{
   int i, j;
   bool swapped;
   for (i = 0; i < n; i++)
   {
     swapped = false;
     for (j = 0; j < n-i-1; j++)      
     {         
        if (arr[j] > arr[j+1])
        {
           swap(&arr[j], &arr[j+1]);
           swapped = true;
        }
     }
 
     // IF no two elements were swapped by inner loop, then break
     if (swapped == false)
        break;
   }
}

Analysis

Bubble sort has worst-case and average complexity both О(n2), where n is the number of items being sorted. There exist many sorting algorithms with substantially better worst-case or average complexity of O(n log n). Therefore, bubble sort is not a practical sorting algorithm when n is large and  should be avoided in the case of large collections. It will not be efficient in the case of a reverse-ordered collection.

The only significant advantage that bubble sort has over most other implementations, is that the ability to detect that the list is sorted is efficiently built into the algorithm. When the list is already sorted (best-case), the complexity of bubble sort is only O(n). By contrast, most other algorithms, even those with better average-case complexity, perform their entire sorting process on the set and thus are more complex. 

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

Auxiliary Space: O(1)
Sorting In Place: Yes
Stable: Yes

Due to its simplicity, bubble sort is often used to introduce the concept of a sorting algorithm.
In computer graphics it is popular for its capability to detect a very small error (like swap of just two elements) in almost-sorted arrays and fix it with just linear complexity (2n). For example, it is used in a polygon filling algorithm, where bounding lines are sorted by their x coordinate at a specific scan line (a line parallel to x axis) and with incrementing y their order changes (two elements are swapped) only at intersections of two lines

Source: Wikipedia