#### 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(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 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; }