How can we avoid unnecessary iterations if array will be sorted before completion of algorithm?
- It is called Optimized bubble sort.
- In the above code, all possible comparisons are made even if the array is already sorted.
- It increases the execution time of sorting.
- We can optimize this by using an extra variable called “any”
- After each iteration, if there is no swapping takes place, we consider the array as already sorted and come out of algorithm execution.
| #include<stdio.h> void BubbleSort(int[], int); int main() { int arr[10],i; for(i=0 ; i<10 ; i++){ arr[i] = rand()%50; } printf(“Before sort : \n”); for(i=0 ; i<10 ; i++) printf(“%d “, arr[i]); BubbleSort(arr,10); printf(“\nAfter sort : \n”); for(i=0 ; i<10 ; i++) printf(“%d “, arr[i]); return 0; } void BubbleSort(int sort[],int n) { int i, swapped, j, temp; for(i=0 ; i<n-1 ; i++) { swapped=0; for(j=0 ; j<n-i-1 ; j++) { if(sort[j]>sort[j+1]) { temp=sort[j]; sort[j]=sort[j+1]; sort[j+1]=temp; swapped=1; } } if(!swapped) break; } } |