Ankur Singh - 1 year ago 88

C++ Question

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 Source

Inside randomPartition() At the line

```
a[i] = a[temp1];
```

replace it with

```
a[i] = temp;
```

just a booboo :P