Bubble sort is a comparison based sorting algorithm. It works like following.

We perform series of iterations to 'bubble up' the elements one by one so that they form a sorted order.
For example we have to sort an array [3,1,4,5,2] in ascending order, In the first iteration, the element 5 will be bubbled up to the last spot. In the second iteration element '4' will be moved to the last but first spot and so on. The following sequence shows one iteration. In each step in the iteration, successive pairs of elements are compared, if they violate the order, swap it.

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

This iteration is repeated until the entire array is sorted. In the first iteration, there will be n-1 comparisons. In the second iteration there will be n-2 comparisons. The number of comparisons decreases with each iteration. The last iteration will have only one comparison.
The following code shows the implementation of the above approach. The time complexity of bubble sort is O(n^2).

` `

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

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