Interview Questions

1. Quick Sort Implementation

   coding

   Practice

   Title: Quick Sort Implementation

   Problem: Given an array of integers, implement the Quick Sort algorithm to sort the array in ascending order. Use a divide-and-conquer approach to partition the array around a pivot and recursively sort the subarrays.

   Function Signature: def quick_sort(arr: List[int]) -> List[int]:

   Input: arr: list[int] — an unsorted list of integers

   Output: A list[int] sorted in ascending order

   Sample Input: [3, 1, 4, 1, 5, 9]

   Sample Output: [1, 1, 3, 4, 5, 9]

   Example: The array [3, 1, 4, 1, 5, 9] is sorted to [1, 1, 3, 4, 5, 9] by choosing a pivot (e.g., first element 3), partitioning into [1, 1], [3], [4, 5, 9], and recursively sorting each partition.

   Constraints: 1 ≤ len(arr) ≤ 10^5; -10^9 ≤ arr[i] ≤ 10^9

   Hints: Use recursion: choose a pivot, partition the array into elements less than or equal to the pivot and those greater than the pivot, then recursively sort the partitions. In-place partitioning can reduce space usage.

   Follow-up: Discuss the best, average, and worst-case time complexities of Quick Sort. How might choosing a random pivot or using median-of-three improve performance?