16.1. Quicksort: Analysis

Try these first

1. 1.

   What is a pivot in the Quicksort algorithm?

   Hint

   Think about its role in dividing the array.

2. 2.

   List the time complexity for the worst-case scenario of Quicksort.

   Hint

   Consider what leads to poor pivot choices.

3. 3.

   What is the worst-case time complexity of Quicksort?

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

   Hint

   Look at conditions leading to poor performance.

4. 4.

   True or False: Randomized Quicksort has an expected time complexity of O(n log n).

   • True
   • False

   Hint

   Consider why randomness is beneficial.

5. 5.

   Given an array with negative and positive integers, explain how to choose a pivot to improve average performance and show steps for partitioning.

   Hint

   Consider how mixing values affects sorting.

6. 6.

   Design an iterative Quicksort algorithm using pseudocode, explaining how to handle the stack for segment management.

   Hint

   How do recursive calls maintain state?