Bubble Sort Algorithm

Bubble sort is one of the simple sorting techniques and it is also easier to code and understand. Bubble sort follows the simple principle of comparing two adjacent elements and swapping them according to our desired order.

How Bubble Sort works?

Consider the below example where we try to sort the given array in ascending order, we start from the beginning comparing the first two elements, and if the first element is greater than the second element we swap them.

Explanation

This is our array and we need to sort in ascending order

[4][1][3][2]

Take a look at the below pictures, the Yellow-colored numbers are the ones being compared and if the first number is greater than the second they are swapped, this starts from the beginning till the end of the array

Next Iteration

Now again we start comparing and swapping all array elements from the beginning but now we do it till (n-1)th element of the array as the last one is already sorted, and this keeps on repeating until the whole array is sorted.

Bubble Sort Code in C++

#include <iostream>
using namespace std;

void bubbleSort(int array[], int size)
{
  //we use two loops
  //one for iterating through the array
  //and another for comparing

  for (int step = 0; step < size - 1; ++step)
  {
    for (int i = 0; i < size - step - 1; ++i)
    {
      // To sort in descending order, change > to < in this line.
      if (array[i] > array[i + 1])
      {
        // swap if first element is greater
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
      }
    }
  }
}

void display(int array[], int size)
{
  for (int i = 0; i < size; ++i)
    cout << " " << array[i];
  cout <<" \n";
}

int main()
{
  int data[] = {5, 1, 0, 4, 3, 2};
  int size = sizeof(data) / sizeof(data[0]);
  bubbleSort(data, size);
  cout << "Sorted Array in Ascending Order:\n";
  display(data, size);
  return 0;
 }

Output

  0  1  2  3  4  5

Space Complexity

The Space complexity for Bubble Sort is O(1) , because we use only one extra temp variable for swapping and that’s it.

Time Complexity

Best Case : O(N) , when the given array is already sorted we iterate through the whole array only once and nothing is swapped.

Worst Case : O(N^2) , when the given array is already sorted but in an opposite order then we have to swap every element compulsorily.

Ex: Given array in ascending order and we need descending order

Average Case : O(N^2) , when the elements are in random order, we might need to swap many elements.

Conclusion

Learning Bubble Sort is fun, isn’t it? I really tried to explain it as simple as possible, comment below if you have any doubts or suggestions, I’ll be happy to help.

This post is a part of my #30DaysChallenge to write a blog post every day on what I learn. Happy Coding ~ Abhiram Reddy.