Quicksort

After reading this chapter and engaging in the embedded activities and reflections, you should be able to:

• Explain and trace the operations of QuickSort on a particular data sequence.
• Implement QuickSort efficiently.
• Analyze the best- and worst-case space and time efficiency of partitioning phase and QuickSort overall.
• Recognize that the average-case time efficiency for QuickSort is the same as the best case.
• Compare the advantages and disadvantages of various pivot choices when implementing the general QuickSort algorithm.
• Trace the operations of QuickSort on a particular data sequence using the median of three pivot choices.
• Explain what stable sorting means and determine which sorting algorithms (that we learned so far) are stable.

Starter code for this chapter.