#### Sorting

Problem
Implement the Bubble sort algorithm.

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(n2).
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 Array
void displayArray(int arr[], int size) {
int i;
for (i=0;i<size;i++) {
cout<<arr[i]<<" ";
}
}

// swap elements in the array
void swap(int arr[],int idx1,int idx2) {
int temp;
temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;
}

// bubble sort
void 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);
}
}
}
}

// main
int 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;
}```