BubbleSort_GL
  1. What is Bubble sort
    1. Bubble Sort Pseudocode
    2. Bubble sort algorithm
    3. Bubble sort dry run
    4. Bubble sort time complexity
    5. Bubble sort space complexity
    6. Bubble sort in C
    7. Bubble sort in java
    8. Bubble sort in C++
    9. Bubble sort in python
  2. Modified Bubble sort
    1. Modified Bubble sort algorithm
    2. Modified Bubble sort time complexity
    3. Modified Bubble sort space complexity
    4. Modified Bubble sort in C
    5. Modified Bubble sort in java
    6. Modified Bubble sort in C++
    7. Modified Bubble sort in python
  3. Bubble sort example
  4. Selection sort vs Bubble sort vs Insertion sort

What is Bubble Sort

Bubble sort is one of the easiest and brute force sorting algorithm. It is used to sort elements in either ascending or descending order. Every element is compared with every other element in bubble sort.

It basically does swapping of elements if they are not in the right order depending on their value and the intended order. A nested loop will be used to implement this algorithm.

Bubble Sort Pseudocode

  1. We are given with an input array which is supposed to be sorted in ascending order
  2. We start with the first element and i=0 index and check if the element present at i+1 is greater then we swap the elements at index i and i+1.
  3. If above is not the case, then no swapping will take place.
  4. Now  “ i ” gets incremented and the above 2 steps happen again until the array is exhausted.
  5. We will ignore the last index as it is already sorted.
  6. Now the largest element will be at the last index of the array.
  7. Now we will again set i=0 and continue with the same steps that will eventually place second largest at second last place in the array. Now the last 2 indexes of the array are sorted.

Bubble Sort Algorithm

Bubble Sort(arr, size)
		for i=0 to n-i-1
			for j=0 to n-i-2
				if arr[j]>arr[j+1]
					Swap arr[j] and arr[j+1]

Bubble Sort Algorithm Dry Run

input:

01234
2310161120

After i=0

01234
1016112023

After i=1

01234
1011162023

After i=2

01234
1011162023

After i=3

01234
1011162023

After i=4

01234
1011162023

Bubble Sort Time Complexity

  • Each and every element is compared with the other elements for array which takes n time
  • And the above steps continues for n iterations
  • Best Time Complexity: O(n^2)
  • Average Time Complexity: O(n^2)
  • Worst Time Complexity: O(n^2)

Bubble Sort Space Complexity

  • No auxiliary space is required in bubble sort implementation
  • Hence space complexity is: O(1)

Now we are going to implement Bubble sort in different programming languages such as C,C++, Python, and Java

Bubble Sort in C 

#include <stdio.h>

void bubbleSort(int arr[], int size) {

 
  for (int j = 0; j < size - 1; ++j) {
    for (int i = 0; i < size - j - 1; ++i) {
      
      if (arr[i] > arr[i + 1]) {
        
        int temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
      }
    }
  }
}

void display(int arr[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", arr[i]);
  }
  printf("\n");
}

int main() {
  int arr[] = {-2, 45, 0, 11, -9};
  int size = sizeof(arr) / sizeof(arr[0]);
  bubbleSort(arr, size);
  printf("Sorted array:\n");
  display(arr, size);
}

Output of the program:

Sorted array:
-9  -2  0  11  45  

Bubble Sort in JAVA


class BubbleSort {
  void bubbleSort(int arr[]) {
    int size = arr.length;
    
   
    for (int i = 0; i < size - 1; i++)
      for (int j = 0; j < size - i - 1; j++)

        if (arr[j] > arr[j + 1]) {

          int temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        }
  }

  void display(int arr[]) {
     int size = arr.length;
	 for (int i = 0; i < size; i++)
		System.out.println(arr[i]+" ");
	
   }
  public static void main(String args[]) {
    int[] arr = { -2, 45, 0, 11, -9 };
    BubbleSort bs = new BubbleSort();
    bs.bubbleSort(arr);
    System.out.println("Sorted array::");
    bs.display(arr);
  }
}

Output of the program:

Sorted array:
-9 
-2 
0 
11 
45

Bubble Sort in C++ 

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int size) {


  for (int j = 0; j < size - 1; ++j) {
    for (int i = 0; i < size - j - 1; ++i) {

      if (arr[i] > arr[i + 1]) {

        int temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
      }
    }
  }
}

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

int main() {
  int arr[] = {-2, 45, 0, 11, -9};
  int size = sizeof(arr) / sizeof(arr[0]);
  bubbleSort(arr, size);
  cout << "Sorted array :\n";
  display(arr, size);
}

Output of the program:

Sorted array :
  -9  -2  0  11  45

Bubble Sort in Python

def bubbleSort(array): 
    length = len(array) 
  

    for i in range(length-1): 
        for j in range(0, length-i-1): 
   
            if array[j] > array[j+1] : 
                array[j], array[j+1] = array[j+1], array[j] 

arr = [10 7 8 9 1 5 ] 
print ("Elements of array before sorting:") 
Elements of array before sorting:
for i in range(len(arr)): 
    print ("%d" %arr[i]), 

bubbleSort(arr) 
  
print ("Elements of array after sorting:") 
for i in range(len(arr)): 
    print ("%d" %arr[i]),  

Output of the program:

Elements of array before sorting:
10 7 8 9 1 5 
Elements of array after sorting:
1 5 7 8 9 10 

Modified Bubble Sort 

Bubble sort complexities remain o(n2) is all cases including sorted array. We can reduce the time complexity to O(n) if the array is already sorted.Also,we need to introduce a flag variable to stop the bubble sort as soon as it becomes sorted.

The flag variable is initialized as true in every iteration and in for loop if array goes in for swapping we will initialize it to false. But if no swapping takes place in the inner loop then its value will remain true and we will have an if condition after the nested loop that will check the flag value and if flag value remains true, we will break

Modified Bubble Sort Algorithm

bubbleSort(arr)
  flag = false
  for i=0 to n-1
    for j=0 to n-1-i
	  if leftEle > rightEle
		swap leftEle and rightEle
		flag =true
	  if flag is true
		break
end 

Modified Bubble Sort Time Complexity

  • Best Time Complexity : O(n), i.e when the elements in the given array are sorted.So, only once the every element is accessed or traversed. 
  • Average Time Complexity : O(n^2)
  • Worst Time Complexity : O(n^2)

Modified Bubble Sort Space Complexity

  • No auxiliary space is required in bubble sort implementation
  • Hence space complexity is : O(1)

Modified Bubble Sort in C 

#include <stdio.h>

void bubbleSort(int arr[], int size) {  // sorting function
  for (int j = 0; j < size - 1; ++j) {

    int flag = 0;

    for (int i = 0; i < size - j - 1; ++i) {

      if (arr[i] > arr[i + 1]) {
        
        int temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        flag = 1;
      }
    }

    if (flag == 0)
      break;
  }
}

void display(int arr[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", arr[i]);
  }
  printf("\n");
}

int main() { // main function or driver function
  int arr[] = {-2, 45, 0, 11, -9};
 printf("Elements before Sorting:\n");
  display(arr, size);

  int size = sizeof(arr) / sizeof(arr[0]);
  bubbleSort(arr, size);
 printf("Elements after Sorting:\n");
  display(arr, size);
}

Output of the program:

Elements before Sorting:
-2 45 0 11 -9 10
Elements after Sorting:
-9  -2  0 10 11  45  

Modified Bubble Sort in JAVA

class BubbleSort {
  void bubbleSort(int arr[]) {   //sorting method
    int size = arr.length;

  
    for (int i = 0; i < size - 1; i++) {
 
      boolean flag = true;
      for (int j = 0; j < size - i - 1; j++) {

        if (arr[j] > arr[j + 1]) {
          
          int temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
          
          flag = false;
        }
      }
      
      if (flag == true)
        break;
    }
  }
  void display(int arr[]) {   //method for displaying the elements
     int size = arr.length;
	 for (int i = 0; i < size; i++)
		System.out.println(arr[i]+" ");
	
   }

  public static void main(String args[]) {   //main method or driver method
    int[] arr = { -2, 45, 0, 11, -9 };

    BubbleSort  bs = new BubbleSort();
    System.out.println("Elements before Sorting:");
    bs.display(arr);
    bs.bubbleSort(arr);
    System.out.println("Elements after Sorting:");
    bs.display(arr);
  }
}

Output of the program:

Elements before Sorting:
-2 
45
0
11
-9
Elements after Sorting:
-9 
-2 
0 
11 
45

Modified Bubble Sort in C++ 

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int size) {  //sorting function
  for (int j = 0; j < size - 1; ++j) {

    int flag = 0;
    for (int i = 0; i < size - j - 1; ++i) {
      if (arr[i] > arr[i + 1]) {

        int temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        flag = 1;
      }
    }

    if (flag == 0)
      break;
  }
}

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

int main() {                   // main function or driver function
  int arr[] = {-2, 45, 0, 11, -9};
  int size = sizeof(arr) / sizeof(arr[0]);
  bubbleSort(arr, size);
  cout << "Sorted array :\n";
  display(arr, size);
}

Output of the program:

Sorted array :
  -9  -2  0  11  45

Modified Bubble Sort in Python

def bubbleSort(arr):
    
  
    for i in range(len(arr)):
        
        flag = True
        for j in range(0, len(arr) - i - 1):

            if arr[j] > arr[j + 1]:

                (arr[j], arr[j + 1]) = (arr[j + 1], arr[j])
                flag = False
                
                if flag:
                    break


arr = [-2, 45, 0, 11, -9]
bubbleSort(arr)
print('Sorted array:')
print(arr)

Output of the program:

Sorted array:
[-9, -2, 0, 11, 45]

Bubble Sort Example

Example1:

If the input array is sorted, return 1 else return 0. Assuming sorting here is in ascending order.

  • Input:
  • 1 2 3 4 5 6
  • 90 80 55 70 40 10
  • Output
  • 1
  • 0

Code for implementation

import java.util.* ;

class Main { 
  
   
    static boolean check(int arr[], int n) 
    { 
  
        if (n == 0 || n == 1) 
            return true; 
  
        for (int i = 1; i < n; i++) 
  
            if (arr[i - 1] > arr[i]) 
                return false; 
  
        return true; 
    } 
  
    public static void main(String[] args) 
    { 
  		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		int arr[] = new int[n];
		for(int i=0;i<n;i++)
		    arr[i]=in.nextInt();
		
        if (check(arr, n)) 
            System.out.print("Array is sorted"); 
        else
            System.out.print("Array is unsorted"); 
    } 
} 

Output:

Input:12 45 78 90 45 10

Output:Array is unsorted

Difference between Selection, Bubble and Insertion Sort

  • In terms of algorithm
    • In Bubble sort, adjacent elements are compared and sorted if they are in the wrong order.
    • In Selection Sort, we select the smallest element and swap it with the 0th index element in the first iteration. This selection continues for n-1 elements and the single element is already sorted and we will have array sorted by 1 element in every iteration
    • In Insertion sort, we create partitions of sorted and unsorted parts. One by one element from the sorted art is taken and sent to the unsorted part for checking and placing it to the right position in sorting using swaps.
  • In terms of time and space complexity
    • All 3 sort have O(n2) time complexity. But via flag variable we can reduce the time complexity of bubble and insertion to O(n) is the best case.
    • Space Complexity is the same for all i.e., O(1)

BestAverageWorstSpace
SelectionO(n2)O(n2)O(n2)O(1)
BubbleO(n)O(n2)O(n2)O(1)
InsertionO(n)O(n2)O(n2)O(1)
  • In terms of speed
    • Bubble sort is slower than the maximum sort algorithm.
    • There are a lot of swaps that might take place in the worst case.
  • In terms of in-place
    • In-place states that the algorithm is in-place if it does not need extra memory barring some variable creation which counts to constant space.
    • Selection, Bubble and Insertion are in-place algorithms and do not require any auxiliary memory.
  • In terms of stability
    • Stability states that the algorithm is stable if the relative ordering of the same elements in the input and output array remains the same.
    • Bubble and Insertion are stable algorithms but the naive selection is not as swapping may cost stability.
SelectionBubbleInsertion
Select smallest in every iteration do single swapAn adjacent swap of every element with the other element where ordering is incorrectTake and put the element one by one and put it in the right place in the sorted part.
Best case time complexity is O(n2)Best case time complexity is O(n)Best case time complexity is O(n)
Works better than bubble as no of swaps are significantly lowWorst efficiency as too many swaps are required in comparison to selection and insertionWorks better than bubble as no of swaps are significantly low
It is in-placeIt is in-placeIt is in-place
Not stableStableStable

This brings us to the end of this article where we learned about bubble sort and its implementation in different languages. Also, we learned how to optimize this algorithm to get better performance. I would highly suggest to take up this free course for data structures and algorithms to improve your coding skills.

Bubble sort algorithm with Great learning academy

0

LEAVE A REPLY

Please enter your comment!
Please enter your name here

19 − fourteen =