Problem with quick sort algorithm

general
, ,
#1

Here’s the code
/****************************************
** Solution by Siddhartha **
****************************************/
#include
#define ll long long int
#define fe(i, a, b) for (long long int i = a; i <= b; i++)
#define fl(i, a, b) for (long long int i = a; i < b; i++)
#define vc vector
#define mod 1000000007
#define el “\n”
#include <bits/stdc++.h>
using namespace std;

int partition(int a[], int l, int h)
{
int pivot = a[l];
int i = l, j = h;
while (i < j)
{
do
{
i++;
} while (a[i] <= pivot);
do
{
j–;
} while (a[j] > pivot);
if (i < j)
swap(a[i], a[j]);
}
swap(a[l], a[j]);
return j;
}

void qSort(int a[], int l, int h)
{
if (l < h)
{
int p = partition(a, l, h);
qSort(a, l, p);
qSort(a, p + 1, h);
}
}

int main()
{

ios_base::sync_with_stdio(false);
cin.tie(NULL);

int n;
cin >> n;
int a[n];
fl(i, 0, n)
{
    cin >> a[i];
}
qSort(a, 0, n - 1);
fl(i, 0, n)
{
    cout << a[i] << " ";
}

return 0;

}

Wrong output for
6
10 7 8 9 1 5
Can anyone point out the error?

#2

#include
#define ll long long int
#define fe(i, a, b) for (long long int i = a; i <= b; i++)
#define fl(i, a, b) for (long long int i = a; i < b; i++)
#define vc vector
#define mod 1000000007
#define el “\n”
#include <bits/stdc++.h>
using namespace std;
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}

int partition(int a[], int l, int h)
{
int p = a[h]; // pivot
int i = (l - 1); // Index of smaller element

for (int j = l; j <= h - 1; j++)  
{  
    // If current element is smaller than the pivot  
    if (a[j] < p)  
    {  
        i++; // increment index of smaller element  
        swap(&a[i], &a[j]);  
    }  
}  
swap(&a[i + 1], &a[h]);  
return (i + 1);

}

void qSort(int a[], int l, int h)
{
if (l < h)
{
int p = partition(a, l, h);
qSort(a, l, p - 1);
qSort(a, p + 1, h);
}
}

int main()
{

ios_base::sync_with_stdio(false);
cin.tie(NULL);

int n;
cin >> n;
int a[n];
fl(i, 0, n)
{
cin >> a[i];
}
qSort(a, 0, n - 1);
fl(i, 0, n)
{
cout << a[i] << " ";
}

return 0;
}

1 Like
#3

Well thanks a lot but it would have been better if u had pointed out the error in my code rather than providing me with a diffrent code.

#4

Format your code. Use ``` at the start and the end of code to format.

This should work

int partition(int a[], int l, int h)
{
int pivot = a[l];
int i = l, j = h;
while (i <= j)
{
    do{
        i++;
    }while (a[i] < pivot);

while (a[j] > pivot)
j--;

if (i <= j)
swap(a[i], a[j]);
}
swap(a[l],a[j]);
return j;
}