Difference between revisions of "W1352 Bubble Sort"
From Coder Merlin
Line 4: | Line 4: | ||
* Read [https://en.wikipedia.org/wiki/Bubble_sort Bubble Sort (Wikipedia)] | * Read [https://en.wikipedia.org/wiki/Bubble_sort Bubble Sort (Wikipedia)] | ||
* View [https://www.youtube.com/watch?v=nmhjrI-aW5o Bubble Sort (Geeks for Geeks)] | * View [https://www.youtube.com/watch?v=nmhjrI-aW5o Bubble Sort (Geeks for Geeks)] | ||
== Exercises == | == Exercises == | ||
Line 19: | Line 20: | ||
## When no swaps have occurred during a pass, you’re done. | ## When no swaps have occurred during a pass, you’re done. | ||
# Complete Merlin exercise 1851 | # Complete Merlin exercise 1851 | ||
=== Quiz === | |||
<quiz shuffleanswers=true display=simple> | |||
{ | |||
Bubble sort is too slow and impractical for most problems. | |||
|type="()"} | |||
+ True | |||
- False | |||
{ | |||
Bubble sort is most practical if: | |||
|type="()"} | |||
+ Elements are in nearly sorted order | |||
- Elements are already sorted in reverse order | |||
- The set of elements is very large | |||
- Doubles (floating point types) are used rather than integers | |||
{ | |||
One advantage of bubble sort is that the ability to detect that the list is sorted is built into the algorithm. | |||
|type="()"} | |||
+ True | |||
- False | |||
{ | |||
An element that must move toward the end of the list can move quickly because it can take part in successive swaps. | |||
|type="()"} | |||
+ True | |||
- False | |||
{ | |||
An element that must move toward the beginning of the list can move faster than one step per pass. | |||
|type="()"} | |||
- True | |||
+ False | |||
{ | |||
Elements move toward the beginning of the list very quickly. | |||
|type="()"} | |||
- True | |||
+ False | |||
{ | |||
Consider the list: 5 1 4 2 8<br/> | |||
After the '''first swap''', the list will be: | |||
|type="()"} | |||
+ 1 5 4 2 8 | |||
- 1 4 5 2 8 | |||
- 1 4 2 5 8 | |||
- 1 2 4 5 8 | |||
{ | |||
Consider the list: 5 1 4 2 8<br/> | |||
After the '''second swap''', the list will be: | |||
|type="()"} | |||
- 1 5 4 2 8 | |||
+ 1 4 5 2 8 | |||
- 1 4 2 5 8 | |||
- 1 2 4 5 8 | |||
{ | |||
Consider the list: 5 1 4 2 8<br/> | |||
After the '''third swap''', the list will be: | |||
|type="()"} | |||
- 1 5 4 2 8 | |||
- 1 4 5 2 8 | |||
+ 1 4 2 5 8 | |||
- 1 2 4 5 8 | |||
{ | |||
Consider the list: 5 1 4 2 8<br/> | |||
After the '''first pass''', the list will be: | |||
|type="()"} | |||
- 1 5 4 2 8 | |||
- 1 4 5 2 8 | |||
+ 1 4 2 5 8 | |||
- 1 2 4 5 8 | |||
{ | |||
Consider the list: 5 1 4 2 8<br/> | |||
After the '''second pass''', the list will be: | |||
|type="()"} | |||
- 1 5 4 2 8 | |||
- 1 4 5 2 8 | |||
- 1 4 2 5 8 | |||
+ 1 2 4 5 8 | |||
{ | |||
Consider the list: 5 1 4 2 8<br/> | |||
How many passes are required before the algorithm terminates? | |||
|type="()"} | |||
- Two | |||
+ Three | |||
- Four | |||
- Five | |||
</quiz> |
Revision as of 18:25, 7 April 2019
Within these castle walls be forged Mavens of Computer Science ...
— Merlin, The Coder
Research[edit]
Exercises[edit]
- 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[edit]