The Randomized Version of the QuickSort algorithm is a variation of the normal QuickSort algorithm. In Randomized QuickSort, the pivot element is selected on a random basis. Whereas in normal quick sort pivot element is selected left most or right most.
In Randomized QuickSort, Instead of using the last element A[last] as pivot we can choose from A[left_index, …,……,….,right_index]. This random selection of pivot helps to avoid the worst-case time complexity of QuickSort.
In this version, randomizing the choice of the pivot element helps to avoid the worst-case time complexity of QuickSort.
Actually, the previous version of the QuickSort algorithm had a problem, if the input array is already sorted or nearly sorted, choosing a fixed pivot could result in a worst-case time complexity of O(n^2). The Randomized QuickSort solves this worst-case problem.
Steps Followed by Randomized Quick Sort
- First Select a pivot element randomly from the array.
- After selecting the pivot element, Partition the array around the pivot.
- All elements that are smaller than the pivot will be on its left side. And all the larger elements will be at its right.
- The same process will apply to each subarray on the left and right of the pivot.
Randomized Quick Sort has reduced the probability of encountering worst-case scenarios. And this selection gives an average-case time complexity of O(n log n).
Randomized Version of Quick Sort Algorithm
function randomizedQuickSort(arr, l, r) if l < r pivotIndex = randomizedPartition(arr, l, r) randomizedQuickSort(arr, l, pivotIndex - 1) randomizedQuickSort(arr, pivotIndex + 1, r) function randomizedPartition(arr, l, r) randomIndex = random(l, r) swap arr[randomIndex] and arr[r] return partition(arr, l, r) function partition(arr, l, r) pivot = arr[r] i = low - 1 for j = l to r - 1 if arr[j] < pivot i = i + 1 swap arr[i] and arr[j] swap arr[i + 1] and arr[r] return i + 1
The randomizedQuickSort function is the entry point of the algorithm. randomized quicksort function takes an array (arr), the lower index (l), and the right index (r) as parameters.