BS Pass 1

Consider the following representation of data in an array. It is not in any sorted order, and we wish to sort the data so that the higher values are to the left and the lower values are to the right. We use the convention that the leftmost array element is element zero, and the index increases by one as we move to the right.

The first step of the process is to compare the contents of element [0] with the contents of element [1]. If element [0] is less than element [1] the two items are unsorted relative to each other, and they must be exchanged. In this case the two elements are already in order, and should not be exchanged.

ADS 03 D

Next, we compare element [1] with element [2]. Again, if the two items are not sorted relative to each other they must be exchanged. In this instance, 6 > 2 so the two items must be exchanged. After performing the exchange, the array will look like this:

ADS 03 E

The third step requires that element [2] be compared with element [3]. Again, if the two are out of order, the two items must be exchanged. In this example 7 > 2 so the exchange takes place, modifying the array to look like this:

ADS 03 F

The fourth step is to compare element [3] with element [4], In this example, 9 > 2 so the exchange takes place, leaving the array looking like this:

ADS 03 G

Notice that the lowest value in the array has been ‘bubbled’ to the rightmost element of the array. This signals the end of the first phase of the sort, as we have now reached the end of the array. (To compare element [4] with element [5] would take us off the end of the array – in some programming languages this would trigger a run-time error.)

Next: BS Pass 2