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.
