Quick sort with middle element as pivot

[1vf9z8AR]

Question-
https://www.codechef.com/problems/TSORT

Test cases give expected output.
I am getting the wrong answer in codechef.

Pivot is middle element always

  #include<iostream>
using namespace std;
int quicksort(int arr[],int low,int high)
{
    if(low>=high)
        return 0;

    int mid=(low+high)/2;
    int pivot=arr[mid];
    int i=low,j=high;
    int temp;
    while(i<j)
    {
        if(arr[i]>=pivot && arr[j]<=pivot)
        {
            temp=arr[j];
            arr[j]=arr[i];
            arr[i]=temp;
            i++;
            j--;
        }
        else
        {
            i++;
        }
    }
    quicksort(arr,low,mid);
    quicksort(arr,mid+1,high);
}
int main()
{
    int t;
    cin>>t;
    if(t<=0)
        return 0;
    int arr[t];
    for(int i=0;i<t;i++)
        cin>>arr[i];
    quicksort(arr,0,t-1);
    for(int i=0;i<t;i++)
        cout<<arr[i]<<endl;
   return 0;
}

[Thomas1965]

Why don't you use std::sort ?

[salem c]

> https://www.codechef.com/problems/TSORT
> Test cases give expected output.
> I am getting the wrong answer in codechef.
The example on the problem page suggests you should be removing duplicates.

> return 0;
You may as well return void, because no other call captures the return result, and no return result is ever used.

> int arr[t];
This isn't valid C++.
Even if it was, given t is upto 10^6, it's likely to blow the stack for larger values of t.
Use int *arr = new int[t]; or better, a std::vector.

[1vf9z8AR]

@Thomas1965
would like to know how things work.
@salem c
Ok. Thanks. Probably array was causing the issue. will try with vector

[dhayden]

The example on the problem page suggests you should be removing duplicates.

Are you referring to "5" appearing twice in the input? The first one is the number of elements in the array, so there are no duplicates to remove.

[salem c]

> Are you referring to "5" appearing twice in the input?
Yes, sorry, mis-read on my part :(

[ne555]

if(arr[i]>=pivot && arr[j]<=pivot)
¿what do you want to do with the `pivot' elements? ¿should they be on the left partition, the right partition or doesn't matter?

[1vf9z8AR]

@ne555
doesn't matter.
the middle element is in left partition

[ne555]

quicksort(arr,low,mid);
that's wrong, the partition doesn't end on `mid'

for example
{6, 7, 8, 1, 2, 3, 4, 5, 9}
mid is 4, pivot is arr[4] = 2
after the partition you may have
{1, 2, 9, 8, 7, 6, 5, 4, 3}
and you part on position 4 so the recursive calls have
{1, 2, 9, 8, 7}
{6, 5, 4, 3}
now you may never move 9 to the last position.

[1vf9z8AR]

@ne555

but swap only occurs when arr[i]>=pivot>=arr[j];
since 9 is maximum it will never move

[ne555]

change the initial array then
after partition the left part should be lesser than the pivot and the right part greater
my point is that when you launch the recursive call you take more than you should (in the example, it should have been divided {1, 2} {9, 8, 7, 6, 5, 4, 3})

also

if(arr[i]>=pivot && arr[j]<=pivot){
   //...
}
else{ //here you may have arr[i]>pivot
   i++; //but you leave it on the left
}