Bubble Sort Algorithm

Bubble sort is an algorithm used to sort (or order) elements present in a list. It sorts elements present in the list by iterating over each element in the list and moving it up by one position if it is greater than the next element. The algorithm continues bubbling elements until each element is less than the element next to it, which indirectly means that the entire list is sorted.

You can visualize the bubble sort algorithm as larger numbers in the list bubbling (or moving) towards the end of list one by one. Visualizations provided below makes it more clear on the operations Bubble Sort algorithm does to sort the list.

Idea Behind the Algorithm

Like the name indicates, the idea is to keep bubbling each element towards right until we reach end of the list. The algorithm stops when there is no element left to bubble.

For example, let’s assume that the bubble sort algorithm is provided with the below input:

The algorithm starts comparing each number with the next number and performs a swap if the current number is greater than the next number. By doing this on all the indices, the largest number (11) bubbles to the end. And that will be the correct position of the largest number in sorted list.

The algorithm repeats the previous iteration until last but one index. In this iteration, the second biggest number (6) bubbles to the end. Note that after the numbers are bubbled to the correct position, we marked in green. At the end of this iteration, the last 2 numbers in the list are sorted and are in the correct positions.

The algorithm does the same iteration again and this time the third biggest number (5) bubbles to the end. At the end of this iteration, the last 3 numbers in the list are sorted and are in the correct positions.

Another iteration is made and this time the fourth biggest number (2) is already at the end of unsorted portion. So there are no swaps.

Finally the only remaining number (the least number) is already at the first position and so the list is sorted.

In short this is what we are doing: Bubble up the largest element in the unsorted portion list to the end until all the elements are in correct positions and the list is sorted. You may experiment with the slide show provided below for better understanding on how each iteration increases the sorted portion of list by size 1.

Visualization of Bubble Sort Algorithm

A minor optimization is to check if we did any swaps in an iteration. If we did not do any swaps in the previous iteration, we can confirm that the list is already sorted and stop making further iterations.

Implementing Bubble Sort Algorithm


# Python program for implementation of Bubble Sort

# Function that sorts an input array in place
# using bubble sort algorithm
def bubbleSort(arr):
  n = len(arr)

  # Make iterations equal to the size of list
  # In each iteration, the size of sorted portion
  # of list increases by 1 from left side 
  for i in range(n):

    # Last i elements are already in place
    # So we just bubble elements in unsorted portion
    for j in range(0, n-i-1):

      # traverse the array from 0 to n-i-1
      # Swap if the element found is greater
      # than the next element
      if arr[j] > arr[j+1] :
        arr[j], arr[j+1] = arr[j+1], arr[j]

# Let's now use the bubble sort algorithm to sort an array
arr = [68, 70, 28, 94, 67, 48]

bubbleSort(arr)

print ("The Sorted array is:")
for i in range(len(arr)):
  print ("%d" %arr[i]),


// C++ program for implementation of Bubble sort

#include <bits/stdc++.h>

// A function implementing bubble sort algorithm
// It sorts any input array / vector in place
void bubbleSort(std::vector<int> &arr)
{
  int n = arr.size();
  for (int i = 0; i < n-1; i++){
    // Last i elements are already in place
    for (int j = 0; j < n-i-1; j++){
      if (arr[j] > arr[j+1]){
        std::swap(arr[j], arr[j+1]);
      }
    }
  }
}

// Let us now use bubble sort algorithm to sort an array
int main()
{
  std::vector<int> arr = {68, 70, 28, 94, 67, 48};
  bubbleSort(arr);
  std::cout<<"Sorted array: \n";
  for(auto n : arr) std::cout << n << " ";
  return 0;
}

Characteristics of Bubble Sort Algorithm

Time Complexity

In the best case scenario, all the elements given in the list might be already sorted. In this case, after the first iteration, we observe that there are no swaps and infer that the list is already sorted. So in best case scenario, we do only one iteration and the time complexity is O(n). (Proportional to the size of list).

In the worst case scenario, we need to make n iterations and each iteration takes O(n) time. So the worst case time complexity is n * O(n) or O(n^2).

Space Complexity

Both the best and worst case space complexity of this algorithm is O(1) since we are not allocating any new list and sorting the list in place.

Stability

Any sorting algorithm is said to be stable if the relative order of elements with similar id is maintained. For example, if we are given an unordered list of objects [1#, 2%, 1%, 2#], the output has to be [1#, 1%, 2%, 2#]. i.e., the relative order of similar elements has to be maintained.

In this algorithm, we bubble elements in the sorted portion of list only if it is greater than the next number. So if there is a relative sequence of something like: [1#, 1%, 1*], the order is maintained since no bubbling between same numbers happen. Hence we maintain relative order of similar elements and bubble sort is a stable algorithm.

Resources & References

https://en.wikipedia.org/wiki/Bubble_sort