3<->1 4 5 2

1 3<->4 5 2

1 3 4<->5 2

1 3 4 5<->2

1 3 4 2 5

` `

#include <iostream>

using namespace std;

//helper method to swap two elements

void swap( int &a, int &b)

{

int temp = a;

a = b;

b = temp;

}

//bubble sort function, takes array and it's size

//as parameters

void bubble_sort(int *array, int n)

{

int i,j;

//outer loop runs for n-1 iterations

for( i = 0 ; i < n-1 ; i++)

{

//inner loop is for comparisons

//in each iteration comparisons reduce by 1

for( j = 0 ; j < n-1-i ; j++)

{

//if elements are out-of-order, swap them

if( array[j] > array[j+1] )

swap(array[j], array[j+1]);

}

}

}

int main()

{

int n;

cin>>n;

int *array = new int[n];

int i;

for( i = 0 ; i < n ; i++ )

{

cin>>array[i];

}

bubble_sort(array,n);

for( i = 0 ; i < n ; i++)

{

cout<<array[i]<<" ";

}

return 0;

}

In bubble sort there is a mechanism to detect if the input array is already sorted. In any iteration, if there are no swappings performed, then we can conclude that the array is sorted. Here is how we can modify the bubble sort to implement this.

void bubble_sort(int *array, int n)

{

int i,j;

bool swap_flag = false;

//outer loop runs for n-1 iterations

for( i = 0 ; i < n-1 ; i++)

{

//inner loop is for comparisions

//in each iteration the comparisions count reduce by 1

for( j = 0 ; j < n-1-i ; j++)

{

//if elements are out-of-order, swap them

if( array[j] > array[j+1] )

{

swap(array[j], array[j+1]);

swap_flag = true;

}

}

//if no swaps are performed in the inner loop, break

if( !swap_flag )

break;

}

}