Randomized Quick Sort Algorithm - Algorithm

We will discuss the Randomized Quick Sort Algorithm, pseudo code, Code implementation of Randomized Quick Sort in C, C++, Java, JavaScript, Python, advantages & disadvantages, and time & space complexity of Randomized Quick Sort.

1. What is Randomized Quick Sort Algorithm?

Randomized Quick Sort is a variation of the Quick Sort algorithm where we choose a pivot randomly instead of using a fixed position like the first, last, or middle element. This helps in avoiding the worst-case time complexity on already sorted or nearly sorted arrays.

In the randomized version of quick sort, we impose a distribution on the input. This does not improve the worst-case running time, but it improves the probability of getting the average-case running time.

The worst case of randomized quick sort occurs when all the given elements are equal.

2. Pseudocode for Randomized Quick Sort

RANDOMIZED_PARTITION (A, p, r) 
1. i <- RANDOM (p, r) 
2. Exchange A[p] <- A[i] 
3. return PARTITION (A, p, r)

The pseudocode for randomized quick sort has the same structure as quick sort, except that it is called the randomized version of the partition procedure.

RANDOMIZED_QUICKSORT (A, p, r) 
1. If p<r then 
2. Q <- RANDOMIZED_PARTITION (A, p, r) 
3. RANDOMIZED_QUICKSORT (A, p, q)
4. RANDOMIZED_QUICKSORT (A, q+1, r)

3. Code Implementation of Randomized Quick Sort

3.1 Randomized Quick Sort in C

#include <stdio.h>
#include <stdlib.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int low, int high) {
    int pivotIndex = low + rand() % (high - low + 1);
    int pivot = arr[pivotIndex];
    swap(&arr[pivotIndex], &arr[high]);
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

3.1.1 Explanation of Quick Sort

swap: Swaps two elements.
partition: Randomly selects a pivot, partitions the array, and places the pivot in its correct position.
quickSort: Recursively sorts the sub-arrays.

3.2 Randomized Quick Sort in C++

#include <iostream>
#include <cstdlib>
using namespace std;

void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

int partition(int arr[], int low, int high) {
    int pivotIndex = low + rand() % (high - low + 1);
    int pivot = arr[pivotIndex];
    swap(arr[pivotIndex], arr[high]);
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

3.3 Randomized Quick Sort in Java

import java.util.Random;

public class RandomizedQuickSort {
    public static void main(String[] args) {
        int[] arr = {38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72};
        quickSort(arr, 0, arr.length - 1);

        System.out.print("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static int partition(int[] arr, int low, int high) {
        Random rand = new Random();
        int pivotIndex = low + rand.nextInt(high - low + 1);
        int pivot = arr[pivotIndex];
        swap(arr, pivotIndex, high);
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }
}

3.4 Randomized Quick Sort in JavaScript

function swap(arr, i, j) {
    [arr[i], arr[j]] = [arr[j], arr[i]];
}

function partition(arr, low, high) {
    const pivotIndex = low + Math.floor(Math.random() * (high - low + 1));
    const pivot = arr[pivotIndex];
    swap(arr, pivotIndex, high);
    let i = low - 1;

    for (let j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i + 1, high);
    return i + 1;
}

function quickSort(arr, low, high) {
    if (low < high) {
        const pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

const arr = [38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72];
quickSort(arr, 0, arr.length - 1);

console.log("Sorted array:", arr);

3.5 Randomized Quick Sort in Python

import random

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def partition(arr, low, high):
    pivotIndex = random.randint(low, high)
    pivot = arr[pivotIndex]
    swap(arr, pivotIndex, high)
    i = low - 1

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            swap(arr, i, j)
    swap(arr, i + 1, high)
    return i + 1

def quickSort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)

arr = [38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72]
quickSort(arr, 0, len(arr) - 1)

print("Sorted array:", arr)

4. Advantages of Randomized Quick Sort

Average Case Efficiency: The average-case time complexity of O(n log n) is maintained.
Avoids Worst-Case: By randomizing the pivot, it reduces the chances of encountering the worst-case time complexity of O(n²).

5. Disadvantages of Randomized Quick Sort

Additional Randomness: The added randomness may lead to inconsistent performance across different runs.
Not Stable: Quick Sort is not a stable sort, meaning the relative order of equal elements may not be preserved.
Recursive Call Overhead: The recursive nature can lead to stack overflow issues for very large arrays if not implemented with tail recursion or an iterative approach.

6. Time Complexity of Randomized Quick Sort

The best- and average-case running time of randomized quick sort = O(n log n).
The worst-case running time of randomized quick sort = O(n²).

The worst case of randomized quick sort occurs when all the given elements are equal

FAQs

What is Randomized Quick Sort?

What are the advantages of Randomized Quick Sort?

By randomizing the pivot, it reduces the chances of encountering the worst-case time complexity of O(n²).
The average-case time complexity of O(n log n) is maintained.

What are the disadvantages of Randomized Quick Sort?

Quick Sort is not a stable sort, meaning the relative order of equal elements may not be preserved.
The recursive nature can lead to stack overflow issues for very large arrays if not implemented with tail recursion or an iterative approach.
The added randomness may lead to inconsistent performance across different runs.

Table of Contents