Practice question · Sort into groups
Sort each sorting algorithm by its typical asymptotic cost.
Groups: Quadratic O(n^2) · Linearithmic O(n log n)
- Bubble sort
- Merge sort
- Heapsort
- Insertion sort
- Quicksort (average case)
- Selection sort
Hints
- The three 'simple sorts' are quadratic; the efficient sorts are linearithmic.
- Merge, quick (average), and heap are the O(n log n) family.
Show the answer
Quadratic O(n^2): Bubble sort, Selection sort, Insertion sort
Linearithmic O(n log n): Merge sort, Quicksort (average case), Heapsort
Why
Bubble, selection, and insertion are the simple O(n^2) sorts; merge, quicksort (on average), and heapsort are the efficient O(n log n) sorts real systems use for large data.
Practise Sorting Strategies
The app has 5 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Sorting Strategies
- Order the steps of one round of selection sort.
- Stability in a sort, preserving the order of equal elements, sounds like a technicality. When does it become…
- Sorting stability only matters when the records carry information beyond the key being sorted on.
- Comparison-based sorting cannot beat O(n log n), and counting sort runs in O(n). Why is that not a…
- Match each sort to its distinguishing property.