Difference between revisions of "W1352 Bubble Sort"

@@ Line 1: / Line 1: @@
-[[File:DRAFT ICON.png|DRAFT ICON]]
+[[File:Reflection in a soap bubble edit.jpg|thumb|link=|Reflection in a Soap Bubble]]
 == Background ==
 * Read [https://en.wikipedia.org/wiki/Bubble_sort Bubble Sort] (Wikipedia)
 * View [https://www.youtube.com/watch?v=gaC4MKqn41g Bubble Sort 1- Algorithm] (YouTube)
 * View [https://www.youtube.com/watch?v=18OO361--1E Bubble Sort Algorithm] (YouTube)
+== Quiz ==
-== Exercises ==
-# Practice with Playing Cards
-## Shuffle a “deck” of 13 cards.
-## Lay out every card in the deck, horizontally, face-up, from left-to-right.
-## Record the ordering of the deck on a tracking sheet.
-## Place a two-headed pointer on the left-hand side so that it’s pointing at the first and second card.
-## 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.
-## 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.
-## Again make a comparison following the above rules for swapping.
-## Continue to track any swaps that occur and advance the pointer until reaching the right-end side of the deck.
-## At this point, the first pass has completed.  Record the number of swaps that occurred during this pass.
-## 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.
-## When no swaps have occurred during a pass, you’re done.
-# Complete Merlin exercise 1851
-=== Quiz ===
 <quiz shuffleanswers=true display=simple>
 {
@@ Line 115: / Line 99: @@
 </quiz>
+== Exercises ==

Revision as of 22:55, 29 March 2020

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

— Merlin, The Coder

Reflection in a Soap Bubble

Background[edit]

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

Quiz[edit]

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

	False
	True

2 Bubble sort is most practical if:

	The set of elements is very large
	Doubles (floating point types) are used rather than integers
	Elements are in nearly sorted order
	Elements are already sorted in reverse 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.

	False
	True

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

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

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

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

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

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

	Five
	Four
	Two
	Three

Difference between revisions of "W1352 Bubble Sort"

Revision as of 22:55, 29 March 2020

Background[edit]

Quiz[edit]

Exercises[edit]