Question

Consider the quick sort algorithm.

The quick sort algorithm is a divide and conquer approach which chooses a pivot value and divides the subarrays as the lower values on the left and the bigger values on the right (comparing them to pivot). Then, each subarray is processed similarly until the array becomes sorted.

Quick sort algorithm has an average time complexity of O(nlogn). However, if the array to be used in the quicksort is already sorted, then the complexity becomes O(n²).

In this question, modify the quicksort algorithm. Therefore, you will use a randomized partitioning algorithm that shuffles the array first and then chooses a pivot value. (in your cpp file)

Also analyze, what will change by following such an approach. What will be the complexity? Write down your analysis (in a docx file).

Answer 1

PLEASE GIVE IT A THUMBS UP

#include <cstdlib>
#include <iostream>
using namespace std;
int p(int quick[], int l, int h)
{
int pt = quick[h];
int i = (l - 1);

for (int j = l; j <= h - 1; j++) {
if (quick[j] <= pt) {

i++;
swap(quick[i], quick[j]);
}
}
swap(quick[i + 1], quick[h]);
return (i + 1);
}
int p_random(int quick[], int l, int h)
{
srand(time(NULL));
int random = l + rand() % (h - l);
swap(quick[random], quick[h]);
return p(quick, l, h);
}
void qucikRandomSort(int quick[], int l, int h)
{
if (l < h) {
int pi = p_random(quick, l, h);   
qucikRandomSort(quick, l, pi - 1);
qucikRandomSort(quick, pi + 1, h);
}
}
int main()
{
int quick[] = { 85, 69, 25, 35 };
qucikRandomSort(quick, 0, 3);
for(int i=0; i<4;i++)
cout<<quick[i]<<" ";
cout<<endl;
return 0;
}

By using such type of approach we can improve the expected time complexity to O(Nlog N)