15.1.5. Recursive Sorting

Try these first

1. 1.

   What is the purpose of Quick sort?

   Hint

   Think about the overheads of other sorting methods.

2. 2.

   What term is used for the element chosen for partitioning?

   Hint

   It's a key element in the sorting process.

3. 3.

   What is the average case time complexity of Quick sort?

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

   Hint

   Consider how the algorithm's efficiency improves with proper pivot selection.

4. 4.

   True or False: Quick sort requires additional storage for merging.

   • True
   • False

   Hint

   Recall the characteristics of both sorting algorithms.

5. 5.

   Given the array [38, 27, 43, 3, 9, 82, 10], manually perform Quick sort and show each step.

   Hint

   Remember to list all intermediate partitions and pivots.

6. 6.

   Discuss the impact of an unbalanced choice of pivot on the time complexity of Quick sort and provide an example.

   Hint

   Think back on the lessons learned about pivot selection.