Bubble Sort

Speaker Notes

Slide 1:

This contains notes on the logic of an internal bubble sort.

Slide 2:

SUB1 points to the first thing we want to compare and SUB2 points to the second. That means SUB1 starts out at 1 and SUB2 starts out at 2.

The HOLD is used when doing a flip.

END-PT tells us how many numbers are being checked and will be changed as we move from pass to pass. Note that it starts at 5.

FLIP-CT is incremented when we do a flip. If an entire pass is done without flipping, we can assume that the sort is done. If this does not happen, the sort is done when we have done one pass less than the number of things being sorted. In this case that would be 4. FLIP-CT is initialized at 0.

Slide 3:

Three steps in flip:

1) Number SUB1 is pointing to is moved to HOLD

2) Number SUB2 is pointing to is moved to the spot where SUB1 is pointing

3) Number from HOLD is moved to spot where SUB2 is pointing

Because a flip took place, one is added to the flip count.

Note: The steps could be that number SUB2 is point to is moved to HOLD and then number SUB1 is point to is moved to spot where SUB2 is pointing and the number from HOLD is moved to spot where SUB1 is pointing.

Slide 4:

6 is greater than 3 so the numbers are flipped. Notice that with the bubble sort, the highest number is sinking to the bottom.

Slide 5:

At this point we notice that 6 has sunk to the bottom.

Slide 6:

When SUB2 is greater than the END-PT, the pass is complete. If FLIP-CT was equal to 0 indicating that no flips had been done, the sort would end. In this case FLIP-CT is 3 so we will initialize for another pass.

Note that the largest number has sunk to the bottom and will not be part of the next pass.

Slide 7:

The resetting involves reestablishing SUB1 at 1 and SUB2 at 2. 1 is subtracted from END-PT and FLIP-CT is reset to 0.

Slide 8:

Note again that with the bubble sort, the heavy number sinks to the bottom.

Slide 9:

Note that the 5 which started at the top in pass two is being processed and flipped until it will finally reach the slot right above the 6. Note also that the bubble sort because it does not compare to an anchored number, but varies both numbers tends to get things in order as it works.

Slide 10:

Another flip is done to push 5 to its final position.

Slide 11:

If you do not use an END-PT then you could go to the end of the pass, but this is not necessary since the bottom was "locked in". At the end of this pass, the bottom two are "locked in". Actually all of the numbers are in order, but we do not know this so another pass must be started.

Since flips happened in this pass, the processing will go to another pass.

Slide 12:

This is not reset for pass 3. Note that the END-PT is now three. Remember if we go through an entire pass without doing a flip (FLIP-CT remains 0), then the sort is complete. Otherwise we would have to do the full 4 passes. Obviously when END-PT is 1 there is nothing to do.

Slide 13:

This is the first comparison in pass three. The original two numbers are in order so no flip is done.

Slide 14:

There is still no need for a flip. The numbers were in order but a last pass with no flips is needed to verify this.

Slide 15:

The sort is complete because there has been a pass with no flips or because there have been the right number of passes (with 5 elements, the right number of passes would be 4). Note that this can be measured against END-PT.