15.1.6. Partitioning Strategies

Try these first

1. 1.

   What is the purpose of a pivot in the Quicksort algorithm?

   Hint

   Think about how partitioning works.

2. 2.

   Explain what partitioning means in the context of Quicksort.

   Hint

   Refer to how elements are grouped around the pivot.

3. 3.

   What is the average time complexity of the Quicksort algorithm?

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

   Hint

   Consider how often the partitions halve the array.

4. 4.

   True or False: Quicksort is a stable sorting algorithm.

   • True
   • False

   Hint

   What does 'stable' mean in sorting contexts?

5. 5.

   Given the array [60, 20, 90, 10, 50], implement a Quicksort function that sorts it in ascending order and explain each step of the recursive process.

   Hint

   Track how the pivot influences the partitioning process at each recursive step.

6. 6.

   Create a scenario showing how Quicksort can lead to inefficient sorting. Use specific examples of pivot selection that could lead to worst-case performance.

   Hint

   Visualize the consequences of poor pivot choices over several recursive layers.