What does one insertion step do?
- It slides the next value into its slot among the sorted ones
- It finds the smallest remaining value and swaps it to the front
- It deletes the largest value
What does one bubble sort pass do?
- It picks the minimum of the whole list at once
- It swaps out-of-order neighbours as it walks
- It splits the list in half
With an early exit flag, what does bubble sort do on a list that is already sorted?
- 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)?
- Comparisons grow with n times n
- They each use exactly n comparisons
- They never compare anything
In the worst case, how many comparisons does insertion sort make on seven values?
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?