Implement Quick Sort Using Randomization in C++

The quick sort technique is based on partitioning of array of data into smaller arrays. Initially, a pivot element is chosen by the partitioning algorithm. The left part of the pivot holds smaller values than the pivot, and the right part holds the larger value. In this case, we are choosing the pivot element randomly. After choosing the pivot, we do the partitioning and then sort the array recursively.

In this article, we have an array having 100 elements. Our task is to implement quick sort on this array using randomization in C++. Here is an example of a quick sort algorithm:

Input:
arr = {90, 45, 22, 11, 50}

Output:
Array after Sorting: {11, 22, 45, 50, 90}

Steps to Implement Quick Sort Using Randomization

We will follow these steps to implement quick sort on a given array using quick sort:

• The random_shuffle() function is used to randomize the array elements. It selects random elements from 0 to 100 and swaps with i.
• The partition() function separates the array of elements around a pivot element by keeping the elements smaller than the pivot to the left and elements greater than the pivot to the right.
• The randomPivotPartition() function selects a random pivot element using the rand() function between low to high array elements. Then again partition function is called to sort around the new pivot element.
• The quick_sort() function accepts the array, low, and high elements as parameters. This function implements the randomized quick sort array. First, using the randomPivotPartition() function it generates a random partition and then recursively divides the array into two sub-array and sorts them.

C++ Program to Implement Quick Sort Using Randomization

The following code implements the above-mentioned steps to implement quick sort on 100 elements using randomization.

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

const int MAX = 100;

void random_shuffle(int arr[]) {
    for (int i = MAX - 1; i > 0; i--) {
        int j = rand() % (i + 1);   // Random index between 0 and i
        swap(arr[i], arr[j]);   // Swap elements
    }
}

int partition(int a[], int low, int high) {
    int pivot = a[high];    // Last element as the Pivot
    int index = low;
    for (int i = low; i < high; i++) {
        if (a[i] < pivot) {
            swap(a[i], a[index]);   // Swap smaller element to the left
            index++;
        }
    }
    swap(a[high], a[index]);    // Place pivot in the correct position
    return index;
}

int randomPivotPartition(int a[], int low, int high) {
    int n = rand();   // Generate a random number
    int pvt = low + n % (high - low + 1);   //Choose a random index between low and high
    swap(a[high], a[pvt]);  // Swap pivot with last element
    return partition(a, low, high); 
}

void quick_sort(int arr[], int low, int high) {
    if (low < high) {
        int pindex = randomPivotPartition(arr, low, high);
        quick_sort(arr, low, pindex - 1);
        quick_sort(arr, pindex + 1, high);
    }
}

int main() {
    srand(time(NULL));  // Seed RNG once

    int arr[MAX];
    for (int i = 0; i < MAX; i++)
        arr[i] = i + 1;

    random_shuffle(arr);
    quick_sort(arr, 0, MAX - 1);

    for (int i = 0; i < MAX; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

The output of the above code is:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 

Complexity of Quick Sort Using Randomization

The time and the space complexity of the quick sort using randomization is as follows:

• Time Complexity: The time complexity is O(n logn) for best case and average case, O(n^2) for worst case.
• Space Complexity:The space complexity is O(log n).