Ankur Singh Ankur Singh - 2 months ago 19
C++ Question

Reverse Quick Sort

I am trying to perform quick sort on a given array in decreasing order but the first number output is always some arbitrary number like 456752.

I am unable to identify the source of problem. Please help

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

long randPartition(long a[],long start,long end0)
{
long pivot = start + rand()%(end0 - start);

//swap a[end] with [pivot]
long temp = a[end0];
a[end0] = a[pivot];
a[pivot] = temp;

//now partitioning
long i = start;
for(int j = start; j < end0 ; j++)
{
if(a[j] > a[end0])
{
long temp1 = a[j];
a[j] = a[i];
a[i] = a[temp1];
i++;
}
}

//swapping pivot with its correct position
long temp2 = a[end0];
a[end0] = a[i];
a[i] = temp2;

return i;
}

void quickSort(long ar[],long start,long end0)
{
if (start < end0)
{
long i = randPartition(ar,start,end0);
quickSort(ar,start,i-1);
quickSort(ar,i+1,end0);
}
}

int main()
{
int testCases;
cin >> testCases;

while(testCases--)
{
long size0;
cin >> size0;
long arr[size0];

for(int i = 0; i < size0; i++)
{
cin >> arr[i];
}
//cin >> endl;

//using quick sort algo
quickSort(arr, 0, size0 - 1);

//printing the sorted array
for(int j = 0; j < size0; j++)
{
cout << arr[j] << " ";
}
cout << endl;
}

return 0;
}

Answer

Inside randomPartition() At the line

a[i] = a[temp1];

replace it with

a[i] = temp;

just a booboo :P