15.1. Quicksort

Try these first

1. 1.

   What is Quicksort?

   Hint

   Think about how it sorts without needing extra storage.

2. 2.

   Who invented Quicksort?

   Hint

   Consider prominent figures in computer science.

3. 3.

   What is the time complexity of Quicksort in the average case?

   • O(n^2)
   • O(n log n)
   • O(n)

   Hint

   Consider the efficiency of other sorting algorithms as a comparison.

4. 4.

   True or False: The choice of the pivot in Quicksort does not affect performance.

   • True
   • False

   Hint

   Reflect on how a well-balanced partition helps efficiency.

5. 5.

   Given the array [9, 4, 8, 3, 7], implement Quicksort and demonstrate the complete sorting process with all partitioning steps.

   Hint

   Identify the pivot selections and result after each partition.

6. 6.

   Illustrate a scenario where selecting the first element as a pivot leads to the worst-case performance.

   Hint

   Look at how the partitioning occurs with each choice of pivot.