CS102: Introduction to Computer Science II

The bubble sort makes multiple passes through an array. It compares adjacent items and exchanges those that are out of order. Each pass through the array places the next largest value in its proper place. In essence, each item "bubbles" up to the location where it belongs.

Figure 1 shows the first pass of a bubble sort. The shaded items are being compared to see if they are out of order. If there are n items in the array, then there are n −1 $n-1$ pairs of items that need to be compared on the first pass. It is important to note that once the largest value in the array is part of a pair, it will continually be moved along until the pass is complete.

At the start of the second pass, the largest value is now in place. There are n−1 $n-1$ items left to sort, meaning that there will be n−2 $n-2$ pairs. Since each pass places the next largest value in place, the total number of passes necessary will be  n−1 $n-1$. After completing the n−1 $n-1$ passes, the smallest item must be in the correct position with no further processing required. ActiveCode 1 shows the complete bubbleSort function. It takes the array as a parameter, and modifies it by swapping items as necessary.

Typically, swapping two elements in an array requires a temporary storage location (an additional memory location). A code fragment such as

temp = alist[i];
alist[i] = alist[j];
alist[j] = temp;

will exchange the ith and jth items in the array. Without the temporary storage, one of the values would be overwritten.

Lines 5-7 in ActiveCode 1 perform the exchange of the i $i$ and (i+1) th $(i+1)th$ items using the three–step procedure described earlier. Note that we could also have used the simultaneous assignment to swap the items.