Optimized Bubble Sort Algorithm
In case of Bubble Sort, after each iteration largest element will be shifted to right.
bubble_sort(int a[], n) {
int swapped, i, j;
for(i = 0; i < n; i++) {
swapped = 0;
for(j = 0; j < n - i - 1; j++) {
if(a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
swapped = 1;
}
}
if(swapped == 0)
break;
}
}It is an optimized version of Bubble Sort which will break the loop once it finds out the loop is already sorted after ith iteration.
Let us suppose the array is, arr = [10, 20 , 30, 40 , 50]
So, after the inner loop completes 1st iteration swapped value will be unchanged at 0 and the outer loop will break. So, using the swapped variable makes the function little optimized.
Worst Case Time Complexity:
Worst case arises when the array is reverse sorted.
So if n = 5
for i = 0, Comparision = 4
for i = 1, Comparision = 3
for i = 2, Comparision = 2
for i = 3, Comparision = 1
for i = 4, Comparision = 0
______________________________
= 10
Total Comparision
= (n-1) + (n-2) + (n-3) + … + 1
= (n-1) * n / 2 = O(n^2)
Best Case Time Complexity:
Total Comparision = n-1 = O(n)
Space Complexity:
Space Complexity of Bubble Sort is = O(1)
