CODEWITHSUNDEEP
algorithmsortingdebuggingquicksort
Himanth
Himanth

Reputation: 35

What is the mistake in this quicksort implementation?

The code works for a few test cases but fails for most. Where am I getting it wrong?

Also if anything could be done to make the code more efficient.

void quicksort(int *a, int a1, int b1)
{
if ((b1 - a1) > 0)
{
    int pivot = (a1 + b1) / 2;
    int i = a1;
    int j = b1;
    while (i <= j)
    {
        while (a[i] < a[pivot]) //left to right
            i++;
        while (a[j] > a[pivot]) //right to left
            j--;
        if (i < j) // swapping
        {
            int temp;
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i++;
            j--;
        }

    }
    quicksort(a, a1, j);
    quicksort(a, i, b1); //recursive calls
}

}

Upvotes: 3

Views: 214

Answers (1)

Gentian Kasa
Gentian Kasa

Reputation: 776

You don't consider the case when i == j and also, as @MK said in a comment, the pivot should be a value and not an index (pivot = (a1+b1)/2; should be something like pivot = a[(a1+b1)/2]).

For example, if you start the array a = {2, 45, 56, 3, 125} (the array you indicated in a comment) your implementation could transform into {2, 3, 45, 56, 125} with i = 2, j = 2, and also pivot = 2 (treated as an index). In this case the program would go into an infinite loop because it never enters the last if block.

If you change the inner if's condition to i <= j it should be correct.

In the end, applying also some minor optimizations, your code should look like the following:

void quicksort(int *a, int a1, int b1)
{
    if (b1 > a1)    // one less operation (subtraction) with respect to the original
    {
        int pivot = a[a1 + ((b1 - a1) / 2)];    // it is now a value and not an index. the index is calculated in this way to avoid an arithmetic overflow
        int i = a1;
        int j = b1;
        while (i <= j)
        {
            while (a[i] < pivot) //left to right
                i++;
            while (a[j] > pivot) //right to left
                j--;
            if (i <= j) // swapping
            {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                i++;
                j--;
            }
        }
        quicksort(a, a1, j);
        quicksort(a, i, b1); //recursive calls
    }
}

As a last optimization I would suggest to optimize the tail call.

Let me know if anything is unclear.

Upvotes: 1

Related Questions