Suppose A is an array of N Integer values. We want to sort A in ascending order, that is, so A(1) is smallest and A(N) is largest.
Bubble Sort is an algorithm to do this as follows: We have the bottom part of the array, which is done, and the top part of the array, which is not yet done. We repeatedly examine pairs of consecutive elements of the unsorted part of the array and swap them if they are in the wrong order.
We use a Swap subroutine which switches the values of two array elements.
Of course, instead of using subroutines, we could easily write all the code we need in the main program, but it is probably better design to use the subroutines.
It is easy to modify this to put the values in descending order instead, so A(1) is largest and A(N) is smallest.
Example
Suppose A is an array of 10 Integer values and the initial values in A are:
67 33 21 4 84 49 15 55 75 6
Pass 1:
As 67 > 33, we swap them:
33 67 21 4 84 49 15 55 75 6
As 67 > 21, we swap them:
33 21 67 4 84 49 15 55 75 6
As 67 > 4, we swap them:
33 21 4 67 84 49 15 55 75 6
As 67 < 4, we do not swap them:
33 21 4 67 84 49 15 55 75 6
As 84 > 49, we swap them:
33 21 4 67 49 84 15 55 75 6
As 84 > 15, we swap them:
33 21 4 67 49 15 84 55 75 6
As 84 > 55, we swap them:
33 21 4 67 49 15 55 84 75 6
As 84 > 75, we swap them:
33 21 4 67 49 15 55 75 84 6
As 84 > 6, we swap them:
33 21 4 67 49 15 55 75 9 84
After the 1st pass, the 10th element is in place and elements 1 through 9 are the unsorted part of the array.
Pass 2:
As 33 > 21, we swap them:
21 33 4 67 49 15 55 75 9 84
As 33 > 4, we swap them:
21 4 33 67 49 15 55 75 9 84
As 33 < 67, we swap them:
21 4 33 67 49 15 55 75 9 84
As 67 > 49, we swap them:
21 4 33 49 67 15 55 75 9 84
As 67 > 15, we swap them:
21 4 33 49 15 67 55 75 9 84
As 67 > 55, we swap them:
21 4 33 49 15 55 67 75 9 84
As 67 < 75, we do not swap them:
21 4 33 49 15 55 67 75 9 84
As 75 > 9, we swap them:
21 4 33 49 15 55 67 9 75 84
After the 2nd pass, elements 9 and 10 are in place and elements 1 through 8 are the unsorted part of the array.
Pass 3:
As 21 > 4, we swap them:
4 21 33 49 15 55 67 9 75 84
As 21 < 33, we do not swap them:
4 21 33 49 15 55 67 9 75 84
As 33 < 49, we do not swap them:
4 21 33 49 15 55 67 9 75 84
As 49 > 15, we swap them:
4 21 33 15 49 55 67 9 75 84
As 49 < 55, we do not swap them:
4 21 33 15 49 55 67 9 75 84
As 55 < 67, we do not swap them:
4 21 33 15 49 55 67 9 75 84
As 67 > 9, we swap them:
4 21 33 15 49 55 9 67 75 84
After the 3rd pass, elements 8 through 10 are in place and elements 1 through 7 are the unsorted part of the array.
Pass 4:
As 4 < 21, we do not swap them:
4 21 33 15 49 55 9 67 75 84
As 21 < 33, we do not swap them:
4 21 33 15 49 55 9 67 75 84
As 33 > 15, we swap them:
4 21 15 33 49 55 9 67 75 84
As 33 < 49, we do not swap them:
4 21 15 33 49 55 9 67 75 84
As 49 < 55, we do not swap them:
4 21 15 33 49 55 9 67 75 84
As 55 > 9, we swap them:
4 21 15 33 49 9 55 67 75 84
After the 4th pass, elements 7 through 10 are in place and elements 1 through 6 are the unsorted part of the array.
I = 5:
As 4 < 21, we do not swap them:
4 21 15 33 49 9 55 67 75 84
As 21 > 15, we swap them:
4 15 21 33 49 9 55 67 75 84
As 21 > 33, we do not swap them:
4 15 21 33 49 9 55 67 75 84
As 33 < 49, we do not swap them:
4 15 21 33 49 9 55 67 75 84
As 49 > 9, we swap them:
4 15 21 33 9 49 55 67 75 84
After the 5th pass, elements 6 through 10 are in place and elements 1 through 5 are the unsorted part of the array.
Pass 6:
As 4 < 15, we do not swap them:
4 15 21 33 9 49 55 67 75 84
As 15 < 21, we do not swap them:
4 15 21 33 9 49 55 67 75 84
As 21 < 33, we do not swap them:
4 15 21 33 9 49 55 67 75 84
As 33 > 9, we swap them:
4 15 21 9 33 49 55 67 75 84
After the 6th pass, elements 5 through 10 are in place and elements 1 through 4 are the unsorted part of the array.
Pass 7:
As 4 < 15, we do not swap them:
4 15 21 9 33 49 55 67 75 84
As 15 < 21, we do not swap them:
4 15 21 9 33 49 55 67 75 84
As 21 > 9, we swap them:
4 15 9 21 33 49 55 67 75 84
After the 7th pass, elements 4 through 10 are in place and elements 1 through 3 are the unsorted part of the array.
Pass 8:
As 4 < 15, we do not swap them:
4 15 9 21 33 49 55 67 75 84
As 15 < 9, we swap them:
4 9 15 21 33 49 55 67 75 84
After the 8th pass, elements 3 through 10 are in place and elements 1 and 2 are the unsorted part of the array.
Pass 9:
As 4 < 9, we do not swap them:
4 9 15 21 33 49 55 67 75 84
At this point, we are done.
In the process, we have done 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45 comparisons and 25 swaps. For an array of 10 elements, Bubble Sort will always do 45 comparisons and may do anywhere from 0 to 45 swaps.
Bubble Sort is usually slower than Selection Sort, but if the values in an array are only slightly out of order (just a few out of place), it works quite well.