Quick sort with middle element as pivot

Dec 16, 2018 at 3:45pm
closed account (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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
  #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;
}
Last edited on Dec 16, 2018 at 3:51pm
Dec 17, 2018 at 8:07am
Why don't you use std::sort ?
Dec 17, 2018 at 8:25am
> 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.
Dec 17, 2018 at 2:35pm
closed account (1vf9z8AR)
@Thomas1965
would like to know how things work.
@salem c
Ok. Thanks. Probably array was causing the issue. will try with vector
Dec 17, 2018 at 2:52pm
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.
Dec 17, 2018 at 3:22pm
> Are you referring to "5" appearing twice in the input?
Yes, sorry, mis-read on my part :(
Dec 17, 2018 at 3:40pm
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?
Dec 17, 2018 at 5:55pm
closed account (1vf9z8AR)
@ne555
doesn't matter.
the middle element is in left partition

Dec 18, 2018 at 12:57am
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.
Last edited on Dec 18, 2018 at 12:59am
Dec 18, 2018 at 3:58am
closed account (1vf9z8AR)
@ne555

but swap only occurs when arr[i]>=pivot>=arr[j];
since 9 is maximum it will never move
Dec 18, 2018 at 11:28am
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
1
2
3
4
5
6
if(arr[i]>=pivot && arr[j]<=pivot){
   //...
}
else{ //here you may have arr[i]>pivot
   i++; //but you leave it on the left
}
Topic archived. No new replies allowed.