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.
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.
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.
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
Implementation of Bubble sort in C, C++ and Java is given here.
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.
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.
As discussed above,
The time complexity of bubble sort in C,C++, Java:O(n2)
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.