Interview Questions

1. Quick Sort Implementation

   coding

   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?