W1352 Bubble Sort

Within these castle walls be forged Mavens of Computer Science ...

— Merlin, The Coder

Research

• Read Bubble Sort (Wikipedia)
• View Bubble Sort (Geeks for Geeks)

Exercises

1. Practice with Playing Cards
   1. Shuffle a “deck” of 13 cards.
   2. Lay out every card in the deck, horizontally, face-up, from left-to-right.
   3. Record the ordering of the deck on a tracking sheet.
   4. Place a two-headed pointer on the left-hand side so that it’s pointing at the first and second card.
   5. If the first card is greater in value than the second card, swap the two cards. If a swap occurs, make a tick mark on the tracking sheet.
   6. Whether a swap occurred or not, advance the pointer forward (to the right) by one card, so that it’s now pointing at the second and third cards.
   7. Again make a comparison following the above rules for swapping.
   8. Continue to track any swaps that occur and advance the pointer until reaching the right-end side of the deck.
   9. At this point, the first pass has completed. Record the number of swaps that occurred during this pass.
   10. If any swaps occurred during the pass, begin a new pass by repeating this procedure, moving the pointer back to the beginning on the far, left-hand side and moving to the right again.
   11. When no swaps have occurred during a pass, you’re done.
2. Complete Merlin exercise 1851

Quiz

1 Bubble sort is too slow and impractical for most problems.

	False
	True

2 Bubble sort is most practical if:

	Elements are already sorted in reverse order
	Doubles (floating point types) are used rather than integers
	The set of elements is very large
	Elements are in nearly sorted order

3 One advantage of bubble sort is that the ability to detect that the list is sorted is built into the algorithm.

	True
	False

4 An element that must move toward the end of the list can move quickly because it can take part in successive swaps.

	True
	False

5 An element that must move toward the beginning of the list can move faster than one step per pass.

	False
	True

6 Elements move toward the beginning of the list very quickly.

	False
	True

7 Consider the list: 5 1 4 2 8
After the first swap, the list will be:

	1 2 4 5 8
	1 4 2 5 8
	1 4 5 2 8
	1 5 4 2 8

8 Consider the list: 5 1 4 2 8
After the second swap, the list will be:

	1 4 2 5 8
	1 4 5 2 8
	1 5 4 2 8
	1 2 4 5 8

9 Consider the list: 5 1 4 2 8
After the third swap, the list will be:

	1 2 4 5 8
	1 4 2 5 8
	1 5 4 2 8
	1 4 5 2 8

10 Consider the list: 5 1 4 2 8
After the first pass, the list will be:

	1 4 2 5 8
	1 4 5 2 8
	1 5 4 2 8
	1 2 4 5 8

11 Consider the list: 5 1 4 2 8
After the second pass, the list will be:

	1 2 4 5 8
	1 5 4 2 8
	1 4 5 2 8
	1 4 2 5 8

12 Consider the list: 5 1 4 2 8
How many passes are required before the algorithm terminates?

	Two
	Three
	Four
	Five