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

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, and Bubble sort advantages and disadvantages will all be discussed in detail.


Bubble Sort in C, C++, Java

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, C++, Java


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, C++, Java


After the first iteration, are the elements in 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-in-c-2

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   n      swap(arr[j], arr[j + 1])n    end ifn  end fornend fornn


Bubble Sort Implementation

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

@@coding::1@@


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 swaps any elements.

@@coding::2@@


bubble-sort-in-c-1


Why is Bubble sort inefficient?

In the case of bubble sort, n-1 comparisons will be done in the 1st iteration, n-2 in the 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 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.


Check out other Data Structure Questions


Also, See Similar DS Sorting Techniques



bubble-sort-in

c