Question

（C++）Randomized Quicksort: Write C++ codes for randomized quicksort. You may need rand()

to generate random numbers. Run the randomized quicksort 5 times for input array A = {1, 2, 3, …, 99,

100} and report the 5 running times.

Answer 1

#include <bits/stdc++.h>

using namespace std;

void swap(int array[], int i, int j)
{
        //This function swaps i and j indexes of array
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
}

void randomize_array(int array[]) {
        //This function randomizes the given array positions
        srand(time(NULL));
        for (int i = 99; i > 0; i--) {
                int j = rand() % (i + 1);
                swap(array, i, j);
        }
}

int Partition(int array[], int start, int end) {
        int i, pivot = end, j = start;
        for (i = start; i < end; i++) {
                if (array[i] < array[pivot]) {
                        swap(array, i, j);
                        j++;
                }
        }
        swap(array, pivot, j);
        return j;
}
int RandomPartition(int array[], int start, int end) {
        // Random selection of pivot.
        int pivot;
        srand(time(NULL));
        pivot = start + rand() % (end - start + 1); // Randomizing the pivot value from sub-array.
        swap(array, end, pivot);
        return Partition(array, start, end);
}
void quickSort(int array[], int start, int end) {
        //Algorithm for quickSort
        if (start < end) {
                int pivot = RandomPartition(array, start, end); //randomly choose pivot
                quickSort(array, start, pivot - 1);
                quickSort(array, pivot + 1, end);
        }
}
int main() {
        int array[100];
        int no_of_times = 5;

        clock_t start_time, end_time;

        while (no_of_times--) {
                //Iterate 5 times
                for (int i = 1; i <= 100; i++)
                        array[i - 1] = i;
                //Measure start time of algorithm
                start_time = clock();
                randomize_array(array);
                //Sort the elements using quick sort algorithm
                quickSort(array, 0, 99);
                //Measure end time of algorithm
                end_time = clock();
                cout << (5 - no_of_times) << ")Array after sorting is \n";
                for (int i = 0; i < 100; i++)
                        cout << array[i] << " ";
                cout << endl;
                double time_elapsed = double(end_time - start_time) / double(CLOCKS_PER_SEC);
                cout << "\nDuration for sorting is " << fixed
                     << time_elapsed << setprecision(6) << " sec" << endl;
                cout << endl;
        }
        return 0;
}