EXPLANATION FILE OF BUBBLE SORTING
Suppose we declare:
static int a[] = {7, 3, 66, 3, -5, 22, -77, 2};
The following table shows the elemnts of a[] after
each pass of the i loop:
unordered data: 7 3 66 3 -5 22 -77 2
first pass: -77 7 3 66 3 -5 22 2
second pass: -77 -5 7 3 66 3 2 22
third pass: -77 -5 2 7 3 66 3 22
fourth pass: -77 -5 2 3 7 3 66 22
fifth pass -77 -5 2 3 3 7 22 66
sixth pass: -77 -5 2 3 3 7 22 66
seventh pass: -77 -5 2 3 3 7 22 66
At the start of the first pass a[6] is compared to a[7].
Since the values are in order they are not exchanged. Then
a[5] is compared with a[6], and since these values are out
of order they are exchanged. Then a[4] is compared with
a[5], etc. Adjacent out-of-order values are exchanged. The
effect of the first pass is to "bubble" the samllest value
in the array into the elemnt a[0]. In the second pass a[0]
is left unchanged and a[6] is compared with a[7], etc.
After the second pass, the next to the smallest value is in
a[1]. Since each pass bubbles the next smallest element to
its appropriate array position, the algorithm will, after
n - 1 passes, have all the elements ordered. Notice in this
example that after the fifth pass all the elements have been
ordered. It is possible to modify the algorithm to terminate
earlier by adding a variable that detects if no exchanges
are made in a given pass. We leave this as an exercise.
A bubble sort is very inefficient. If the size of the array
is n, then the number of comparisons performed is proportio-
nal to nē.
[From BIBLI 09].