The best programs are written so that computing machines can perform
them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist
who works with traditional aesthetic and literary forms as well as mathematical concepts, to
communicate the way that an algorithm works and to convince a reader that the results will be correct.
― Donald E. Knuth

Solution :-
This algorithm works by repeatedly iterating over the array elements, comparing each of the adjacent elements and swapping them if necessary.
The iteration through the list continues until no swaps are required which indicates that the list is sorted.Complexity of the
algorithm is O(n^{2}).
We implement an optimized version of Bubble sort which is based on an observation that 'n'th pass through the array finds the
'n'th largest element in the list and puts it into its final position in the array.
Consider the following array { 7, 2, 5, 3, 4 }. Let's see how Bubble sort technique works :-

First Pass :- { 7, 2, 5, 3, 4 } -> { 2, 7, 5, 3, 4 } ( Swap 2 & 7 since 7 > 2 ) { 2, 7, 5, 3, 4 } -> { 2, 5, 7, 3, 4 } ( Swap 5 & 7 since 7 > 5 ) { 2, 5, 7, 3, 4 } -> { 2, 5, 3, 7, 4 } ( Swap 3 & 7 since 7 > 3 ) { 2, 5, 3, 7, 4 } -> { 2, 5, 3, 4, 7 } ( Swap 4 & 7 since 7 > 4 )
Element 7 is placed in its final position in the sorted array.

Second Pass :- { 2, 5, 3, 4, 7 } -> { 2, 5, 3, 4, 7 } ( No swapping since 2 < 5 ) { 2, 5, 3, 4, 7 } -> { 2, 3, 5, 4, 7 } ( Swap 3 & 5 since 5 > 3 ) { 2, 3, 5, 4, 7 } -> { 2, 3, 4, 5, 7 } ( Swap 4 & 5 since 5 > 4 )
Element 5 is placed in its final position in the sorted array.

Third Pass :- { 2, 3, 4, 5, 7 } -> { 2, 3, 4, 5, 7 } ( No swapping since 2 < 3 ) { 2, 3, 4, 5, 7 } -> { 2, 3, 4, 5, 7 } ( No swapping since 3 < 4 )
Element 4 is placed in its final position in the sorted array.

Fourth Pass :- { 2, 3, 4, 5, 7 } -> { 2, 3, 4, 5, 7 } ( No swapping since 2 < 3 )
Element 3 is placed in its final position in the sorted array.

Finally, after four passes, the array is sorted. We could optimize the algorithm further by exiting after the Third Pass in which there were no swaps. In general, we can exit early once we see a pass with no swaps.

#include<iostream>using namespace std;
// Display the Arrayvoid displayArray(int arr[], int size) {
int i;
for (i=0;i<size;i++) {
cout<<arr[i]<<" ";
}
}
// swap elements in the arrayvoid swap(int arr[],int idx1,int idx2) {
int temp;
temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;
}
// bubble sortvoid bubbleSort(int arr[], int size) {
int i,j;
for (i=0;i<(size-1);i++) {
for (j=0;j<(size-i-1);j++) {
if (arr[j] > arr[j+1]) {
swap(arr,j,j+1);
}
}
}
}
// mainint main() {
int arr[] = {7,4,5,2,3,19,11,6,9,12,8};
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"\nOriginal Array :: ";
displayArray(arr,size);
bubbleSort(arr,size);
cout<<"\nSorted Array :: ";
displayArray(arr,size);
cout<<endl;
return 0;
}

#include<iostream>using namespace std;
// Display the Arrayvoid displayArray(int arr[], int size) {
int i;
for (i=0;i<size;i++) {
cout<<arr[i]<<" ";
}
}
// swap elements in the arrayvoid swap(int arr[],int idx1,int idx2) {
int temp;
temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;
}
// bubble sortvoid bubbleSort(int arr[], int size) {
int i,j;
for (i=0;i<(size-1);i++) {
for (j=0;j<(size-i-1);j++) {
if (arr[j] > arr[j+1]) {
swap(arr,j,j+1);
}
}
}
}
// mainint main() {
int arr[] = {7,4,5,2,3,19,11,6,9,12,8};
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"\nOriginal Array :: ";
displayArray(arr,size);
bubbleSort(arr,size);
cout<<"\nSorted Array :: ";
displayArray(arr,size);
cout<<endl;
return 0;
}