Randomized Version of Quick Sort Explanations

by

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

  1. First Select a pivot element randomly from the array.
  2. After selecting the pivot element, Partition the array around the pivot.
  3. All elements that are smaller than the pivot will be on its left side. And all the larger elements will be at its right.
  4. 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

Explanation

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.