16.1.1. Introduction to Quicksort

Try these first

1. 1.

   What is the primary purpose of Quicksort?

   Hint

   Think about what sorting algorithms aim to achieve.

2. 2.

   What does partitioning mean in Quicksort?

   Hint

   Consider how elements are rearranged around a certain number.

3. 3.

   What is the average-case time complexity of Quicksort?

   • O(n)
   • O(n log n)
   • O(n²)

   Hint

   Think back to the discussed scenarios for average performance.

4. 4.

   True or False: The worst-case scenario of Quicksort occurs when the pivot is the median.

   • True
   • False

   Hint

   Remember the impact of pivot choices on performance.

5. 5.

   Design a scenario with an array where Quicksort would perform at its worst-case time complexity. Explain why this occurs.

   Hint

   Consider how sorted inputs affect pivot choice.

6. 6.

   Propose a method to implement randomized Quicksort and discuss its potential impact on sorting various datasets.

   Hint

   Think about maintaining efficiency across random inputs.