Random Quick Sort is divide-and-conquer algorithm that selects a 'pivot'
element and partitions the other elements into two groups: those less than
the pivot and those greater than the pivot. It then recursively applies the
same process to each group.
Time Complexity
Best Case: O(n log n)
Average Case: O(n log n) - This becomes more likely outcome with randomized
pivot selection.
Worst Case: O(n^2) - Though still possible, it becomes increasingly unlikely
as the size of the array grows.
Space Complexity: O(log n) - It is because the quick sort algorithm is a
recursive algorithm, and it needs to keep track of the recursion stack.
Using a random pivot is a practical optimization to make quicksort work well
in real-world scenarios and to prevent performance degradation on specific
types of input (like sorted arrays).
Type Parameters
TElement extends string | number
Parameters
arr: TElement[]
unsorted array of elements (may be strings or numbers)
left: number = 0
right: number = ...
Returns TElement[]
sorted array of elements (may be strings or numbers)
Random Quick Sort is divide-and-conquer algorithm that selects a 'pivot' element and partitions the other elements into two groups: those less than the pivot and those greater than the pivot. It then recursively applies the same process to each group.
Time Complexity
Best Case: O(n log n)
Average Case: O(n log n) - This becomes more likely outcome with randomized pivot selection.
Worst Case: O(n^2) - Though still possible, it becomes increasingly unlikely as the size of the array grows.
Space Complexity: O(log n) - It is because the quick sort algorithm is a recursive algorithm, and it needs to keep track of the recursion stack.
Using a random pivot is a practical optimization to make quicksort work well in real-world scenarios and to prevent performance degradation on specific types of input (like sorted arrays).