W1352 Bubble Sort

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

— Merlin, The Coder

Reflection in a Soap Bubble

Background

• Read Bubble Sort (Wikipedia)
• View Bubble Sort 1- Algorithm (YouTube)
• View Bubble Sort Algorithm (YouTube)

Quiz

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

	True
	False

2 Bubble sort is most practical if:

	Doubles (floating point types) are used rather than integers
	Elements are already sorted in reverse order
	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.

	False
	True

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.

	True
	False

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 5 4 2 8
	1 4 2 5 8
	1 4 5 2 8
	1 2 4 5 8

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

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

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

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

10 Consider the list: 5 1 4 2 8
After the first 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

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

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

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

	Four
	Three
	Five
	Two