16.1.8. Practical Usage of Quicksort

Try these first

1. 1.

   What is the average-case time complexity of Quicksort?

   Hint

   Think about how the array gets divided on average.

2. 2.

   What is a pivot in the context of Quicksort?

   Hint

   It's the element that divides the array into two parts.

3. 3.

   What is the average case time complexity of Quicksort?

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

   Hint

   Affected by how evenly the array gets divided.

4. 4.

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

   • True
   • False

   Hint

   Consider what happens with sorted arrays.

5. 5.

   Given the array [7, 2, 1, 6, 8, 5, 3, 4], manually apply the Quicksort algorithm by choosing the first element as the pivot through two partitions.

   Hint

   Focus on where each element should go relative to the pivot.

6. 6.

   Design a randomized Quicksort and explain how your pivot selection helps mitigate worst-case scenarios while considering a worst-case input.

   Hint

   Think about how random choices can alter expected performance.