Bubble sort is one of the simplest sorting algorithms but yet it is powerful. Bubble sort compares the element on the index and if that element is greater than i+1th element, it just swaps the element.

The worst and average case time complexity of Bubble sort is O(n^2). 

Let’s see pseudo code and understand the algorithm through an example.

Pseudo Code :

swapped = true
while swapped
    swapped = false
    for j from 0 to N - 1
	if a[j] > a[j + 1]
		swap( a[j], a[j + 1] )
		swapped = true

Bubble Sort Steps:

Bubble Sort Steps

Implementation:

C

#include <stdio.h>
void bubbleSort(int array[], int size)
{
  for (int step = 0; step < size - 1; ++step)
  {
    for (int i = 0; i < size - step - 1; ++i)
    {
      
      if (array[i] > array[i + 1])
      {
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
      }
    }
  }
}

void printArray(int array[], int size)
{
  for (int i = 0; i < size; ++i)
  {
    printf("%d  ", array[i]);
  }
  printf("\n");
}
int main()
{
  int data[] = {4 ,1 , 10 , 7};
  int size = sizeof(data) / sizeof(data[0]);
  bubbleSort(data, size);
  printf("Sorted Array in Ascending Order:\n");
  printArray(data, size);
}


Python

def bubbleSort(array):
    for i in range(len(array)):
        for j in range(0, len(array) - i - 1):
           
            if array[j] > array[j + 1]:
                (array[j], array[j + 1]) = (array[j + 1], array[j])
data = [4,1,7,10]
bubbleSort(data)
print('Bubble sort : ')
print(data)

Java

import java.util.Arrays;
class BubbleSort {
  void bubbleSort(int array[]) {
    int size = array.length;
    for (int i = 0; i < size - 1; i++)
      for (int j = 0; j < size - i - 1; j++)
        
        if (array[j] > array[j + 1]) {
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
        }
  }
  public static void main(String args[]) {
    int[] data = { 4 , 1 , 7 ,10 };
    BubbleSort bs = new BubbleSort();
    bs.bubbleSort(data);
    System.out.println("After bubble sort : ");
    System.out.println(Arrays.toString(data));
  }
}

C++

// Bubble sort in C++
#include <iostream>
using namespace std;
void bubbleSort(int array[], int size)
{
  for (int step = 0; step < size - 1; ++step)
  {
    for (int i = 0; i < size - step - 1; ++i)
    {
      
      if (array[i] > array[i + 1])
      {
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
      }
    }
  }
}
void showArray(int array[], int size)
{
  for (int i = 0; i < size; ++i)
  {
    cout << "  " << array[i];
  }

}
int main()
{
  int data[] = {4 , 1  , 10 , 7};
  int size = sizeof(data) / sizeof(data[0]);
  bubbleSort(data, size);
  cout << "After Bubble Sort:\n";
  showArray(data, size);
}

Few Interview questions on Bubble Sort:

Question-What will be the time complexity of bubble sort in worst case?

Answer: The time complexity will be O(n^2) .

  • Worst Case Time Complexity [ Big-O ]: O(n2)
  • Best Case Time Complexity : O(n) (When array is already sorted)
  • Average Time Complexity [Big-theta]: O(n2)
  • Space Complexity: O(1)


Question– How many iterations is required in bubble sort (Suppose you have 5 elements in an array then how many iterations will be required)?


Answer : Number of iteration in bubble sort will be n(n-1) / 2 ,Where n is the size of array.
So, in this case size is 5 i.e. n = 5 ==> 5(5-1)/2

10 will be the answer.

That’s all I have and thanks a lot for reading. Please let me know if any corrections/suggestions. Please do share and comments if you like the post. Thanks in advance… 😉

Thanks Abhijeet Gupta for helping us to grow day by day. Abhijeet is expert in Data Structure and loves to solve competitive problems.


2 Comments

Pooja agrawal · November 29, 2019 at 5:17 am

Very nice site.. For learners.. Added interview questions.. It’s a plus point.

    admin · November 29, 2019 at 6:20 am

    Thanks a lot for visiting the blog and valuable feedback. It means a lot for us. As a team, we are continously working to make the content quite useful for everyone.

Leave a Reply

Your email address will not be published. Required fields are marked *

Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert