Explore
ProGrad Programs
Placement Prep
TCS Codevita
Live Placement Training
Live Aptitude Training
Live Programming Training
Webinars
About Us

Edit
Reply




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 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 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


Also See Similar DS Sorting Techniques


If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in