Bubble Sort Algorithm

Problem Statement: Given an array of N integers, write a program to implement the Bubble Sorting algorithm.

Examples:

Example 1:
Input: N = 6, array[] = {13,46,24,52,20,9}
Output: 9,13,20,24,46,52
Explanation: After sorting we get 9,13,20,24,46,52


Input: N = 5, array[] = {5,4,3,2,1}
Output: 1,2,3,4,5
Explanation: After sorting we get 1,2,3,4,5

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Approach

  • Repeatedly swap 2 adjacent elements if arr[j] > arr[j+1] .
  • Here, the maximum element of the unsorted array reaches the end of the unsorted array after each iteration.
  • Unlike selection sort, here, sorting is done from the back as shown in the dry run.
  •  After (N-1) iterations , we get a sorted array.

Dry Run:

Iteration 1:

Iteration 2:

Iteration 3:

Iteration 4:

Iteration 5:

Code:

C++ Code

#include<bits/stdc++.h>

using namespace std;
void bubble_sort(int arr[], int n) {
  // bubble sort
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }

  cout << "After Using bubble sort: " << "\n";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";

}
int main() {
    int arr[] = {13,46,24,52,20,9};
    cout<<"Before Using Bubble Sort: "<<endl;
    for(int i=0;i<6;i++)
    {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
    int n = sizeof(arr) / sizeof(arr[0]);
    bubble_sort(arr, n);
    return 0;
}

Output:

Before Using Bubble Sort:
13 46 24 52 20 9
After Using bubble sort:
9 13 20 24 46 52

Time Complexity: O(n^2), (nested for loop)

Space Complexity: O(1)

Java Code

public class bubble_sort {
  public static void main(String args[]) {
    int arr[] = {13,46,24,52,20,9};
    int n = arr.length;
    System.out.println("Before Using Bubble Sort: ");
    for(int i=0;i<6;i++)
    {
        System.out.print(arr[i]+" ");
    }
    System.out.println();
    // bubble sort
    for (int i = 0; i < n - 1; i++) {
      for (int j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
          int temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        }
      }
    }

    System.out.println("After bubble sort: ");
    for (int i = 0; i < n; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }

}   

Output:

Before Using Bubble Sort:
13 46 24 52 20 9
After Using bubble sort:
9 13 20 24 46 52

Time Complexity: O(n^2), (nested for loop)

Space Complexity: O(1)

Special thanks to Rishiraj Girmal for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article