CODEWITHSUNDEEP
c++algorithmsortingquicksort
Eslam Hamdy
Eslam Hamdy

Reputation: 7396

My quick sort implementation fails in some cases

I have implemented a quick sort algorithm but when I tested it I noticed that it fails when the input array has the largest element in the first element (this is the element I got the pivot from). Here's my code:

void partition(int *a,int size){
    if(size<=1){return;}
    int pivot=a[0];
    int left=0,right=0;
    for(left=1,right=size-1;left<=right;){    //was size-1
        if(a[left]>=pivot&&a[right]<=pivot) {
            swap(left,right,a);
        }

        if(a[left]<pivot){left++;}
        if(a[right]>pivot){right--;}
    }
    swap(0,right,a);
    partition(a,right-1);
    partition(&(a[right+1]),size-right-1);
}

Some samples that it fails on:

I/P 245  111  32    4
O/P 4   111  32  245     `

I/P 154   11   43  3  7
O/P   7   11   43  3  154

What are the possible mistakes I have made?

Upvotes: 0

Views: 415

Answers (2)

Aman
Aman

Reputation: 9035

Well, the problem lies here : 

partition(a,right-1); // <- It's partition(array,size)!

Change it to 

partition(a,right);

And it will work. I think you know the reason.
For the partition function to work correctly, you must supply 2 things :

1) The array to work on.
2) The number of elements it has, the size.

The problem lies in the first recursive call to partition the left subarray:  partition(a,right-1)

The argument 2, the size, is incorrectly specified to be right-1, when it is actually right.

This can be worked out by using the fact that the number of elements in an array from an index a to b ( both included,b>=a) are N= b-a+1.

Here, we have a=0, b=right-1, thus the number of elements in the left sub array, the size, N=(right-1)-(0)+1=right.

Thus the to work correctly, you must call it like partition(a,right);. The left sub array ends at right-1, but it has right-1+1=right elements.

Happens all the time :)

Upvotes: 2

amit
amit

Reputation: 178521

You are missing a case where there is an element in the array which is the pivot, in the partition function.

Assume arr = { 5, 5, 1 , 1, 5, } 

pivot = 5
iter1:
left=1, arr[left]=5 ; right=4,arr[right]=5
(swapping)
not increasing left nor decreasing right - since 5 < 5 == false ; 5 > 5 == false

Next iteration, the same scenario will repeat itself, and you will actually get an infinite loop.

One way to deal with it is to determine that the "big" part will also increase all elements that are exactly the pivot, and swap elements if arr[right] < pivot (not <=), and decrease right if arr[right] >= pivot (not >), something like:

...
for(left=1,right=size-1;left<=right;){    //was size-1      
        if(a[left]>=pivot&&a[right]<pivot) { 
        //                         ^ note < not <=
        swap(left,right,a);
    }

    if(a[left]<pivot){left++;}
    if(a[right]>=pivot){right--;}
    //        ^ note >=
}
...

Upvotes: 2

Related Questions