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).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.