What does one insertion step do?
- It takes the next value and slides it into its slot among the sorted values
- It swaps random pairs until lucky
- It deletes the largest value
What does one bubble sort pass do?
- It picks the minimum of the whole list at once
- It walks along comparing neighbours and swapping out-of-order pairs
- It splits the list in half
With an early exit flag, what does bubble sort do on nearly sorted input?
- It still grinds through every pass
- It can finish in one pass with no swaps
- It runs slower than on reversed input
Why are both methods O(n squared)?
- Their comparison counts grow with the square of n
- They each use exactly n comparisons
- They never compare anything
Worst case comparisons to insertion sort six values? Work it out as 5 + 4 + 3 + 2 + 1.
Answer: ______________
Insertion sort runs in nearly linear time on nearly sorted input.
Circle one: True False
A student claims bubble sort always beats insertion sort because swapping looks faster. What is the error?
- Swapping decides nothing; on nearly sorted input insertion slots values in almost at once
- Bubble sort can never sort at all
- Insertion sort cannot handle small lists
Six values need 15 worst case comparisons. Roughly how many for twelve values?