Bubble Sort

by codecrucks · Published 10/09/2021 · Updated 02/09/2022

Bubble sort is comparison based sorting method, and also known as sinking sort. It is perhaps most simple sorting algorithm.

Bubble Sort is a simple method for sorting a given set of n elements provided in the form of an array with n elements. It analyzes each element individually and sorts them based on their values.

It compares the first and second elements of the array; if the first element is greater than the second element, it will swap both elements, and then compare the second and third elements, and so on.

In general, sorting is accomplished by comparing neighboring elements A[j] and A[j+1]. If the components being compared are out of sequence, they are switched. The biggest element bubbles up at the final place in the unsorted array at the end of each iteration. For array of size n, this process is repeated n – 1 times.

Sorting an array starts from the end. The largest element is moved to the last place in the first iteration, the second largest element is moved to the second last position in the second iteration, and so on.

It is called as bubble sort because, with each complete iteration, the largest element in the given array bubbles up to the last position or the highest index, similar to how a water bubble rises to the water’s surface.

This basic method performs badly in practice and is mostly used as an educational tool. Sorting libraries integrated into popular computer languages like as Python and Java utilize more efficient algorithms such as quicksort, timsort, or merge sort.

Example of Bubble Sort

Bubble sort compares adjacent elements and swaps them if they are out of order. In every iteration, the largest element from unsorted array moves to the last location. Following figures show the step by step simulation of it.

let us sort the letters of word “DESIGN” in alphabetical order using bubble sort.

Step by step comparison and output of every pass is depicted in following figures. Adjacent cells in light gray colors are under comparison and dark gray cells indicate sorted elements.

Pass – 6

Algorithm for Bubble Sort

Algorithm BUBBLE_SORT(A)
// A is an array of size n

for i ← 1 to n do
  for j ← 1 to n – i do
    if A[j] > A[j+1] do
      swap(A[j], A[j+1])
    end
  end
end

Although the above logic would sort an unsorted array, the technique is inefficient since the outer for loop will continue to execute for n iterations even if the array is sorted.

Optimized version of the algorithm is mentioned below:

Algorithm OPTIMIZED_BUBBLE_SORT(A)
// A is an array of size n

for i ← 1 to n do
  flag ← 1
  for j ← 1 to n – i do
    if A[j] > A[j+1] do
      temp ← A[j]
      A[i] ← A[j+1]
      A[j+1] ← temp
      flag ← 0
    end
    if (flag) do
      break
    end
  end
end

Complexity Analysis

For first iteration of outer loop, inner loop does n comparisons. For second iteration of outer loop, inner loop dose n – 1 comparison and so on. In last iteration of outer loop, inner loop does only one comparison. Outer loop itself iterates n times. Running time of algorithm is defined as total number of comparisons. Thus,

Despite the fact that statements within the inner loop do not execute, the complexity of bubble sort is O(n²). The quadratic complexity is caused by the two nested for loops, which iterate regardless of the input data pattern. As a result, the complexity of bubble sort is the same whether the situation is best, worst, or average.

It’s self-explanatory, that if no swapping occurs in the first run, the list is already sorted. By setting an appropriate flag, we can break the cycle. In this scenario, the best-case bubble sort running time would be linear, i.e. O(n).

During the first iteration of the outer loop, the inner loop executes n times without changing the flag, indicating that the data is sorted.

Following table shows the time complexity of bubble sort for both versions, normal (without flag) and optimized (with flag):

	Best Case	Average case	Worst case
Without flag	O(n²)	O(n²)	O(n²)
With flag	O(n)	O(n²)	O(n²)

Other O(n²) sorting algorithms, such as insertion sort, are typically quicker than bubble sort and are not any more complex. As a result, bubble sort is not a useful sorting algorithm.

The single important benefit it has over most other algorithms, including quicksort but not insertion sort, is that the ability to discover if list is sorted. The complexity of this algorithm is only O(n) when the list is already sorted (best-case).

Most other algorithms, even ones with lower average-case complexity, execute their whole sorting operation on the set, making them more complicated.

Simulation

Working of bubble sort is nicely simulated in following diagram

Image Source: https://commons.wikimedia.org/wiki/File:Bubble-sort.gif [Link]

Rabbits and Turtles

Because elements flow in different directions at different speeds, the distance and direction that elements must move during the sort influence the performance of bubble sort.

Larger element may participate in consecutive swaps and moves faster toward end. smaller elements moves quite slowly towards beginning. Consider following data patter, where the largest element is at beginning and the smallest is at end.

A = <8, 7, 6, 5, 4, 3, 2, 1>

After first iteration, array A would be,

A = <7, 6, 5, 4, 3, 2, 1, 8>

As can be seen, in one iteration, 8 moved from first to last position (moved seven positions.) Whereas, element 1 moved from last to second last position (moved one position only).

So larger element, which moved quickly towards the end are known as hare, and smaller elements which moves slowly towards beginning are known as turtle.

Discussion and Comparison

Several attempts have been made to eliminate turtles in order to increase the speed of bubble sorting. Cocktail sort is a bidirectional bubble sort that moves from beginning to end and then reverses direction, moving from end to beginning. It can move turtles rather effectively, but its worst-case complexity is O(n²).

In his famous book “The Art of Computer Programming”, Donald Knuth concludes that “the bubble sort appears to have little to recommend it, except a catchy name and the fact that it leads to some interesting theoretical issues

Comb sort compares elements separated by large gaps and can move turtles fast before moving on to smaller and smaller gaps to smooth down the list. Its average performance is comparable to that of quicker algorithms such as quicksort.

In the worst situation, bubble sort is asymptotically identical to insertion sort in terms of running time, but the two algorithms differ significantly in terms of the number of swaps required. Astrachan’s experimental results also demonstrate that insertion sort works significantly better even on random lists. For these reasons, many current algorithm textbooks prefer the insertion sort method over the bubble sort technique.

Bubble sort also has a bad interaction with current CPU technology. It generates at least twice the number of writes as insertion sort, double the number of cache misses, and asymptotically more branch mispredictions. Astrachan’s experiments sorting strings in Java demonstrate that bubble sort is about one-fifth as quick as an insertion sort and 70% faster than a selection sort.

Code for Bubble Sort

Some Popular Sorting Algorithms

Following are the few popular sorting algorithms used in computer science: