Optimized Bubble Sort Algorithm with C++ Code | Sorting Algorithms | Data Structures & Algorithms
In this tutorial we understand the working of optimized bubble sort algorithm in data structures.
Optimized Bubble Sort –
- Optimized bubble sort is basically a smarter version of bubble sort algorithm. Hence the algorithm is same with a mechanism to determine whether the list/array DS is sorted or not after every iteration
- This ensures that the algorithm only runs till the array/list is sorted.
- Regular bubble sort runs iterations which are equal to the size of the array irrespective of whether the array is sorted before those number of iterations or not.
- In optimized bubble sort, we have a flag variable that keeps track of whether the list is completely sorted or not.
- In optimized bubble sort, whenever there is a swapping in any iteration, it means that the array/list is still not sorted & hence the flag is set to FALSE.
- Whenever there is no swapping in a particular iteration, the flag is set to TRUE
- At the end of every iteration, this flag variable is checked. If value is true, it means swapping happened & hence the list isn’t sorted completely so next iteration is allowed. If value is false, it means swapping never happened, hence the list is already sorted & there is no point in further iterations hence exit algorithm.
Working –
- Step 1 – Starting with the first element(index = 0), compare the current element with the next element of the array. Set flag = false
- Step 2 – If the current element is greater than the next element of the array, swap them. Set flag = true
- Step 3 – If the current element is less than the next element, move to the next element.
- Step 4 – At end of iteration check flag, if true, continue iteration else exit iterations.
- Step 4 – Repeat Step 1 till the list is sorted.
Algorithm –
- declare variables – i, j
- loop : i = 0 to n – 1 // outer looploop : j = 0 to n -i- 1 //
- set flag = false
- inner loopif ( a[j]>a[j+1] ) then
- set flag = true
- swap a[j] & a[j+1]
- end loop // inner loop
- if flag == false then
- EXIT
- inner loopif ( a[j]>a[j+1] ) then
- end loop // outer loop
C++ Program to Implement Optimized Bubble Sort –
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | #include < iostream > using namespace std; void optimizedbubbleSort(int a[]) { int rounds = 0; for (int i = 0; i < 5; i++) { rounds++; int flag = false; for (int j = 0; j < (5 - i - 1); j++) { if (a[j] > a[j + 1]) { flag = true; int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } if (flag == false) { break; } } cout << "No of rounds : " << rounds << endl; } int main() { int myarray[5]; cout << "Enter 5 integers in any order: " << endl; for (int i = 0; i < 5; i++) { cin >> myarray[i]; } cout << "Before Sorting" << endl; for (int i = 0; i < 5; i++) { cout << myarray[i] << " "; } cout << endl; optimizedbubbleSort(myarray); // sorting cout << "After Sorting" << endl; for (int i = 0; i < 5; i++) { cout << myarray[i] << " "; } return 0; } |