Bubble Sort Exploration (Part 1) (Click here for Part 2)

We will start by watching bubble sort run slowly on a reasonably small data set. When you watch it, look for these things:

• where do you see the sorting first?
• what values are i and j taking on?
• can you see that the swaps are only between neighbors (i.e. that no data moves very far in one swap)?
• do you see the biggest unsorted item moving into its position?

The introduction told us that each pass would put the largest unsorted item into place, but actually more than that is occurring. Watch again to see what happens to items that are medium-sized (not small, but not the larges unsorted item).

Watching the movement of the medium-sized values gives a different description of what the inner for loop is doing: it moves the first entry to the right until it finds something bigger. Then it moves that item to the right until it finds something bigger. This continues until it reaches the sorted part of the array. That will have moved the largest unsorted item into its correct position.

Now that you have spotted the basic behavior of this algorithm, run it again and look for the bigger picture. We saw that the sorting started at the end of the array, but watch what happens in the beginning portion of the array.

Did you see a gentle curve appear in the beginning of the array before the sorted part got there? This shows that some ordering is occurring even in the unsorted portion of the array. This effect is caused by the previous observation you made: the inner loop is moving medium-sized entries closer to their positions. Since that movement is being made by making swaps with smaller items, the smaller items are also moving closer to their positions.