Practice question · Sort into groups
Classify each sort as O() average or O(n log n) average.
Groups: O() · O(n log n)
- Selection sort
- Quick sort (avg)
- Bubble sort
- Merge sort
- Insertion sort
Hints
- Ask whether the algorithm splits the problem in half or scans repeatedly.
- Divide-and-conquer buys the logarithmic factor.
Show the answer
O(): Bubble sort, Insertion sort, Selection sort
O(n log n): Merge sort, Quick sort (avg)
Why
Divide-and-conquer sorts achieve O(n log n); simple nested-loop sorts are O().
Practise Searching and sorting ideas
The app has 8 more questions on this lesson, and keeps your place in the course. Physics I is free to start.
More questions on Searching and sorting ideas
- Trace selection sort on the list [7, 2, 9, 1]. Order the states the list passes through.
- You guess a number between 1 and 1000; after each guess you learn "higher" or "lower". A smart player needs…
- Binary search is far faster than linear search but is used less often in practice. Why is it used less often…
- Order the steps of merge sort on [3, 1, 4, 2].
- Binary search finds a name among 1,000 sorted entries in ~10 steps. Estimate the steps needed for…