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.

How Randomized QuickSort Works

  1. Pick a Pivot Randomly: Instead of taking the first or last item in the list as the pivot, Randomized QuickSort picks a random item. It’s like guessing a number and using that guess to start organizing things.
  2. Partition the List: Once the pivot is chosen, the list is divided into two parts – one with items smaller than the pivot and one with items bigger. It’s like splitting toys into two boxes based on their size compared to the random toy you picked.
  3. Sort Each Part: With the two smaller lists, Randomized QuickSort repeats the first two steps, picking new random pivots each time, until everything is in the right order. It’s like organizing each box of toys one at a time until everything is neatly arranged.

Why Randomized QuickSort is Awesome

  • Fairness: By picking pivots randomly, every list has an equal chance to be sorted quickly. It’s like giving every player in a game the same chance to win.
  • Avoids Slowdowns: Some lists can make regular QuickSort take a lot longer. Random choices help avoid these lists, making sorting faster on average.
  • Easy to Understand: Even with the randomness, it’s still simple. You’re just picking a random place to start each time you sort.

Conclusion

Randomized QuickSort adds a layer of randomness to the pivot selection, which helps avoid the worst-case scenarios of traditional QuickSort (like already sorted arrays causing slow performance). By randomly choosing a pivot and then partitioning and recursively sorting the sub-arrays, we effectively and efficiently sort the entire array, regardless of its initial state. This method ensures that, on average, we get good performance for a wide variety of input arrays.