The will to succeed is important, but what's more important is the will to prepare.
~ Bobby Knight

Bubble Sort

Welcome readers!

Today we will start with our new module "Time and Space" of "Dynamic Programming". However, in most of the previous questions done so far, we have discussed Time and Space Complexities. In this article we will discuss the most basic sorting algorithm, Bubble Sort.

Before moving any further we advise you to give this problem a try on our website.

It is one of the easiest problems that you have solved till now. Here you are given an array(arr) of integers. You have to sort the given array in increasing order using bubble sort.

For example: Sample Input: (5 7 -2 4 1 3)

It's quite obvious that size of array is 5 and output for bubble sort on inputting any array will be the sorted array, i.e. (-2 1 3 4 7)

But in order to make sure that you use the Bubble Sort Algorithm in this problem, our IDE will accept the output of the following format.

Sample Output:

Comparing -2 and 7

Swapping -2 and 7

Comparing 4 and 7

Swapping 4 and 7

Comparing 1 and 7

Swapping 1 and 7

Comparing 3 and 7

Swapping 3 and 7

Comparing 4 and -2

Comparing 1 and 4

Swapping 1 and 4

Comparing 3 and 4

Swapping 3 and 4

Comparing 1 and -2

Comparing 3 and 1

Comparing 1 and -2

-2 1 3 4 7(in different lines)

So an advice for you is that you use the same function for swapping and comparing which is already on our IDE of this problem.

You can watch part of the video for better understanding.

Approach :

Let's say that elements of our input array are: (5, 9, 8, 2 and 1).

As the length of the array is 5 that means there will be a total of four iterations. And at the end of each iteration, the largest value will get placed at the correct position of the array. Let's take a look at that.

At the first iteration we compare 9 with 5, but 9 is not smaller than 5 therefore there will be no swapping.

Then 8 is compared with 9, since 8 is smaller than 9 therefore there will be swapping.

Then 2 is compared with 9, since 2 is smaller than 9 therefore there will be swapping.

Then 1 is compared with 9, since 1 is smaller than 9 therefore there will be swapping.

At last, the largest element that is 9 is placed at the last index of the array.

Since the largest element is placed at the right position, that is at the last index. So, next time, for loop of j will run for one iteration less.

Let's try to code this.

First loop of itr, will run only for n-1 times because for n-1 iterations, n-1 largest elements of array will be placed at right positions.

Second loop of j, will only run for the first n-1 elements of the array, comparing the value of the jth index element with (j + 1)th index element. Because when the loop will run for (n-1)th index element nth element will automatically be taken into account.

While comparing values inside the loop, if the value of (j+1)th index element is smaller than jth index element then we simply swap the elements.

And yes, we are done! You can also watch part of the video for any difficulty faced.

import java.io.*;
import java.util.*;
public class Main {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int itr = 1; itr < n; itr++) {
for (int j = 0; j < n - itr; j++) {
if (isSmaller(arr, j + 1, j) == true) {
swap(arr, j + 1, j);
}
}
}
}
// used for swapping ith and jth elements of array
public static void swap(int[] arr, int i, int j) {
System.out.println("Swapping " + arr[i] + " and " + arr[j]);
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// return true if ith element is smaller than jth element
public static boolean isSmaller(int[] arr, int i, int j) {
System.out.println("Comparing " + arr[i] + " and " + arr[j]);
if (arr[i] < arr[j]) {
return true;
} else {
return false;
}
}
public static void print(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
public static void main(String[] args) throws Exception {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scn.nextInt();
}
bubbleSort(arr);
print(arr);
}
}

java;
true";

Analysis

Time Complexity :

Worst Case Time Complexity: O(n*n). Worst case is when the array is in reverse order.

Best Case Time Complexity: O(n) Best case is when the input array is already sorted.

Average Case Time Complexity: O(n*n). The inner loop does O(n) work on each iteration, and the outer loop runs for O(n) iterations, so the total work is O(n ^{2}).

SPACE COMPLEXITY :

Auxiliary Space: O(1), as no extra space is used.

We hope that this article was helpful. However, if you still face any difficulty then you are advised to watch our complete video lecture on Bubble Sort.

We hope that you are enjoying your learning journey. It's very important to understand Time and Space complexities so that when you code your program you look for an optimized algorithm rather than any naive approach.

We wish you all the best. Stay focused and motivated.