Skip to main content\(
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Section 7.9 Self Check
Checkpoint 7.9.1.
Which of the following sort algorithms are guaranteed to be
\(O(n \log n)\) even in the worst case?
Shell Sort
Incorrect! Shell sort is between \(O(n)\) and \(O(n^2)\)
Quick Sort
Incorrect! Quick sort can be \(O(n \log n)\text{,}\) but if the pivot points are not well chosen and the list is just so, it can be \(O(n^2)\text{.}\)
Merge Sort
Correct! Merge Sort is the only guaranteed \(O(n \log n)\) even in the worst case. The cost is that merge sort uses more memory.
Insertion Sort
Incorrect! Insertion sort is \(O(n^2)\)
Checkpoint 7.9.2.
Match each sorting method with its appropriate estimated comparisons.
Refer to previous sections of the chapter
- Quick Sort
\(O(n \log n)\) or \(O(n^2)\)
- Insertion/Bubble/Merge
\(O(n^2)\)
- Merge Sort
\(O(n \log n)\)
- Shell Sort
between \(O(n)\) and \(O(n^2)\)
Checkpoint 7.9.3.
Which sort should you use for best efficiency If you need to sort through 100,000 random items in a list?
Merge
Correct!
Selection
Incorrect! Selection sort is inefficient in large lists.
Bubble
Incorrect! Bubble sort works best with mostly sorted lists.
Insertion
Incorrect! Insertion sort works best with either small or mostly sorted lists.
You have attempted
of
activities on this page.
