Bubble Sort in C, C++, Java | FACE Prep

In this article, we will be discussing Bubble sort in C, C++, Java and other languages. Bubble sort example, Bubble sort algorithm implementation, Bubble sort time complexity, Bubble sort advantages and disadvantages will all be discussed in detail.

What is Bubble sort?

Bubble sort is a sorting algorithm which iterates through a given array of elements and compares each pair of adjacent elements one after the other. In any of the adjacent pairs, if the first element is greater/larger than the second element, then it swaps the elements and if not, then it moves on to the next pair of elements. The end objective of bubble sort is to sort the given array in ascending order.

bubble sort in c

Bubble Sort Explanation with Examples

Let us consider an array having 5 elements. Here is the working of bubble sort with an example. 

bubble sort in c implementation

 

 

 

 

 

 

 

 

 

After the first iteration, are the elements in the ascending order?

No. This means we will have to keep repeating this set of actions again and again until the entire array of elements are sorted. But then, how many times will we have to iterate a given array such that the array is completely sorted?

In general, it takes (n-1) iterations in order to sort a given array using the bubble sort algorithm, where n is the number of elements in the array.

So in this case, since there are 5 elements, it takes (5-1), i.e 4 iterations to completely sort the array.

Bubble Sort Pseudo Code

Here is the pseudo-code of bubble sort.

for i = 0 to n - 1  // to keep track of the number of iterations
    for j = 0 to n - 1  // to compare the elements within the particular iteration
        // swap if any element is greater than its adjacent element
        if arr[j] > arr[j + 1] then       
            swap(arr[j], arr[j + 1])
        end if
    end for
end for

Bubble Sort Implementation

 Implementation of Bubble sort in C, C++ and Java is given here.

#include<stdio.h>
int main()
{
int n, i, j, temp;
scanf("%d", &n);
int arr[n];
for(i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
for(i = 0; i < n - 1; i++) // to keep track of number of cycles
{
for(j = 0; j < n - i - 1; j++) // to compare the elements within the particular cycle
{
// swap if one element is greater than its adjacent element
if(arr[j] > arr[j + 1])
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
#include<iostream>
using namespace std;
int main()
{
int n, i, j, temp;
cin >> n;
int arr[n];
for(i = 0; i < n; i++)
{
cin >> arr[i];
}
for(i = 0; i < n - 1; i++)
{
for(j = 0; j < n - i - 1; j++)
{
if(arr[j] > arr[j + 1])
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
for(i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
}
import java.util.Scanner;
public class Main
{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int i, j, temp;
int n = sc.nextInt();
int arr[] = new int[n];
for(i = 0; i < n; i++)
{
arr[i] = sc.nextInt();
}
for(i = 0; i < n - 1; i++)
{
for(j = 0; j < n - 1; j++)
{
if(arr[j] > arr[j + 1])
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
for(i = 0; i < n; i++)
{
System.out.print(arr[i] + " ");
}
}
}

Input:

5 (Number of elements)
8 5 2 6 12

Output: 

2 5 6 8 12

Optimized Bubble Sort in C, C++, Java

The above program’s time complexity is O(n2) even if the array is already in sorted order. This can be minimized by breaking the outer loop if the inner loop swap any elements.

#include<stdio.h>
#include<stdbool.h>

int main()
{
int n, i, j, temp;
bool swapped;
scanf("%d", &n);
int arr[n];
for(i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
for(i = 0; i < n - 1; i++) // to keep track of number of iteration
{
swapped = false; // to check whether swapping of two elements happened or not
for(j = 0; j < n - i - 1; j++) // to compare the elements within the particular iteration
{

// swap if any element is greater than its adjacent element
if(arr[j] > arr[j + 1])
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}

// if swapping of two elements does not happen then break
if(swapped == false)
break;
}
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
#include<iostream>
#include<stdbool.h>
using namespace std;

int main()
{
int n, i, j, temp;
bool swapped;
cin >> n;
int arr[n];
for(i = 0; i < n; i++)
{
cin >> arr[i];
}
for(i = 0; i < n - 1; i++) // to keep track of number of iteration
{
swapped = false; // to check whether swapping of two elements happened or not
for(j = 0; j < n - i - 1; j++) // to compare the elements within the particular iteration
{

// swap if any element is greater than its adjacent element
if(arr[j] > arr[j + 1])
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}

// if swapping of two elements does not happen then break
if(swapped == false)
break;
}
for(i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
}
import java.util.Scanner;

public class Main
{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int i, j, temp;
Boolean swapped;
int n = sc.nextInt();
int arr[] = new int[n];
for(i = 0; i < n; i++)
{
arr[i] = sc.nextInt();
}
for(i = 0; i < n - 1; i++) // to keep track of number of iteration
{
swapped = false; // to check whether swapping of two elements happened or not
for(j = 0; j < n - i - 1; j++) // to compare the elements within the particular iteration
{

// swap if any element is greater than its adjacent element
if(arr[j] > arr[j + 1])
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}

// if swapping of two elements does not happen then break
if(swapped == false)
break;
}
for(i = 0; i < n; i++)
{
System.out.print(arr[i] + " ");
}
}
}

Why is Bubble sort inefficient?

In case of bubble sort, n-1 comparisons will be done in the 1st iteration, n-2 in 2nd iteration, n-3 in the 3rd iteration and so on. So the total number of comparisons will be,

= (n-1) + (n-2) + (n-3) + ….. + 3 + 2 + 1 = n(n-1)/2 = ½ [ n2 – n]

Hence the time complexity of Bubble Sort is O(n2). This shows that too many comparisions are performed in order to sort an array. Hence this might cause inefficiency as the size of the array grows.

Bubble Sort Time Complexity & Space Complexity

As discussed above,

The time complexity of bubble sort in C,C++, Java: O(n2)

  • Space complexity: O(1)
  • The worst-case time complexity: O(n2)
  • Average case time complexity: O(n2)
  • Best case time complexity: O(n) 

The best-case occurs when the given array is already sorted. In such a case, in one iteration (i.e using n comparisons), we can check and see if we’re making any swaps in our first iteration. If we’re not, we know that the list is sorted, and we can stop iterating.

Also See Similar DS Sorting Techniques