a of numbers, with length n,
here's a snippet of C code for bubble sort:
for (i=0; i<n-1; i++) {
for (j=0; j<n-1-i; j++)
if (a[j+1] < a[j]) { /* compare the two neighbors */
tmp = a[j]; /* swap a[j] and a[j+1] */
a[j] = a[j+1];
a[j+1] = tmp;
}
}
As we can see, the algorithm consists of two nested loops. The index
j in the inner loop travels up the array, comparing
adjacent entries in the array (at j and
j+1), while the outer loop causes the inner loop to make
repeated passes through the array. After the first pass, the largest
element is guaranteed to be at the end of the array, after the second
pass, the second largest element is in position, and so on. That is
why the upper bound in the inner loop (n-1-i) decreases
with each pass: we don't have to re-visit the end of the array.
Here's a demonstration of bubble sort. If you need instructions on running the demo, look here.
The algorithm starts with an array of random numbers. Each number is represented with a vertical stick. The height of the stick indicates the value of the number, and its left-right position indicates its location in the array.
Now let's see what happens if the numbers in the array are already sorted, but in reverse order. Notice that swapping two adjacent elements is not a very efficient way to move elements from one end of the array to the other!
Next we run bubble sort on an array of numbers which is already almost sorted. As you can see, there are fewer swaps this time. In fact, the array is sorted after just a few passes of the inner loop.