quicksort bug not found

after working a whole day on this, i cannot find w开发者_开发知识库hat is wrong with my code, i cannot find where my error is. can someone please help me figure out what i did wrong?

void a_quick(int array[], int i, int j){
    //Array Quick Sort
    if ((j - i) < 2){
        return;
    }
    int top = j;
    int bot = i;
    int p_location = i + (j + i) / 2;
    int pivot = array[p_location];
    while (i < j){
        while (array[i] < pivot){
            i++;
        }
        while (array[j] > pivot){
            j--;
        }
        if (i <= j){
            swap(array[i], array[j]);
            i++;
            j--;
        }
    }
    a_quick(array, bot, p_location);
    a_quick(array, p_location + 1, top);

}

running the code on 64k int arrays will crash the computer, and i need to get it to run on 128k.

im getting:

Test Array:
703 322 673 141 253 547 662 37 723 529 316 190 288 40 264 446 890 370 6 393

Quick Sort w Array:
6 37 40 141 253 190 316 288 264 322 393 370 446 529 723 662 890 547 673 703

this code works fine for me

   void a_quick(int array[], int i, int j){
    //Array Quick Sort

    int top = j;
    int bot = i;
    int p_location = (j + i) / 2;
    int pivot = array[p_location];
    do {
        while (array[i] < pivot)i++;
        while (array[j] > pivot)j--;
        if (i <= j){
            swap(array[i], array[j]);
            i++;
            j--;
        }
    } while (i<=j);
    if (bot<j) a_quick(array, bot, j);// problem is most likely here
    if (i<top) a_quick(array, i, top);// or here
}

It's rather broken. You need to move the pivot item out of the way (conventionally to the beginning of the array you are partitioning) since it's very unlikely that half the elements are less than the pivot and half greater.

And as others have said, you're including the pivot in both sub partitions when you recurse.

I would start by proving one partition run works (i.e don't recurse for now, stop when the partitioning is done, and check the array is now how you would expect)

One problem is that the last two lines should read:

a_quick(array, bot, p_location - 1);
a_quick(array, p_location + 1, top);

Another problem is that you need to be prepared to move the pivot around (and keep track of its index). Your code would only work if the pivot already happens to be in the correct spot, which is unlikely.

For comparison, take a look at the several versions of the pseudocode available in Wikipedia.

The way you compute the pivot has a problem. Ask yourself what happens when the indices are 5 and 9. Instead of this:

p_location = (j - i) / 2;

Try something more like:

p_location = i + (j - i) / 2;

this should work

void a_quick(int array[], int i, int j){
//Array Quick Sort
if (j <= i) return; // change here (j - i) < 1 (not 2)

int top = j;
int bot = i;
int p_location = (j + i) / 2; // change here - by + so you pick the middle
int pivot = array[p_location];
while (i < j){
    while (array[i] < pivot){
        i++;
    }
    while (array[j] > pivot){
        j--;
    }
    if (i <= j){
        swap(array[i], array[j]);
        i++;
        j--;
    }
}
a_quick(array, bot, j); // change here (dont use p_loc, use i and j)
a_quick(array, i, top); // and here

}

This should work

#include <memory>
#include <iterator>
#include <algorithm>
#include <iostream>

void a_quick(int array[], int i, int j){
    //Array Quick Sort
    if ((j - i) < 2){
        return;
    }
    int top = j;
    int bot = i;

    // Bug 1: Pick something in the correct range.
    int pivot = array[i + (j-i)/2];
    while (i < j){
        while (array[i] < pivot){
            i++;
        }
        while (array[j] > pivot){
            j--;
        }
        if (i < j)
        {
            // Bug 2: swap is in the std namespace
            std::swap(array[i], array[j]);

            // Bug 3: Don't increment the pointers.
            //        What if you hit the pivot point.
        }
    }
    // The split is not at where you selected the pivot point.
    // As that could be any number and it may not split evenly.
    // So you pick either of i or j. I picked j as the mid point
    // One sort upto j the other sorts from j+1 to the end.
    a_quick(array, bot, j );
    a_quick(array, j+1 , top );
}


int main()
{
    int d[] = { 703, 322, 673, 141, 253, 547, 662, 37, 723, 529, 316, 190, 288, 40, 264, 446, 890, 370, 6, 393 };
    int size = sizeof(d)/sizeof(d[0]);

    a_quick(d, 0, size - 1 );

    std::copy(d, d+size, std::ostream_iterator<int>(std::cout, ", "));
}

I tried:

void a_quick(int array[], int i, int j){
    //Array Quick Sort
    if ((j - i) < 2){
        return;
    }
    int top = j;
    int bot = i;
    int p_location = (j - i) / 2;
    int pivot = array[p_location];
    while (i < j){
        while (array[i] < pivot){
            i++;
        }
        while (array[j] > pivot){
            j--;
        }
        if (i <= j){
            std::swap(array[i], array[j]);
            i++;
            j--;
        }
    }
    a_quick(array, bot, p_location);// problem is most likely here
    a_quick(array, p_location, top - 1);// or here
}

int main()
{
    // int d[] = { 5, 1, 6, 4, 8, 2, 3, 7, 9, 0};
    int d[] = { 5, 1, 6, 4, 8, 2, 3, 7, 0, 9};
    a_quick(d, 0, 9);

    std::copy(d, d+10, std::ostream_iterator<int>(std::cout));
}

> g++ sort.cpp
> ./a.exe
0124356789 >

And it worked fine.
What we really need is an example of it failing.

Hopefully with a full test harness that just compiles and runs and shows the error.