Explore
Placement Prep

Edit

Edit

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

Published on 12 Mar 2020

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 Explanation with Examples

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

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 iterationsfor j = 0 to n - 1 // to compare the elements within the particulariteration// swap ifany element is greater than its adjacent elementif 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.

C
C++
Java

Output
Input- 8 5 2 6 12 Output- 2 5 6 8 12

## Optimized Bubble Sort in C, C++, Java

The above programs 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.

C
C++
Java

Output
Input- 8 5 2 6 12 Output- 2 5 6 8 12

## 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 comparisons 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 were making any swaps in our first iteration. If were not, we know that the list is sorted, and we can stop iterating.

Check out other Data Structure Questions