0

I've been trying to implement quick sort and have been having a lot of problems. I even copied a lot of implementations and accepted answers from the net and they ALL crash on odd sized array/vector if you run it enough times (each time I run I run quick sort against random numbers to be sorted... rather than pretend my code works just cuz it can sort one particular set of numbers).

Here is my code and also prints to help debug the error.

template <typename T>
void quickSortMidPivot(vector<T>&vec, size_t left, size_t right)
{
    mcount++;

    if(right - left < 1)
        return;

    //crash all the time
    //if(left >= right)
    //    return;

    size_t l = left;
    size_t r = right;
    T pivot = vec[left + ((right-left)/2)];
    cout << endl << "PivotValue:" << pivot << endl;

    while (l <= r)
    {
        while (vec[l] < pivot)
            l++;

        while (vec[r] > pivot)
            r--;

        if (l <= r) {
            cout << endl << "swap:" << vec[l] << "&" << vec[r] << endl;
            std::swap(vec[l], vec[r]);
            l++;
            r--;

            for (int i =left; i<=right; i++)
                cout  << vec[i] << " ";
        }
    }

    cout << endl << "left:" << left << " r:" << r << endl;
    cout << "l:" << l << " right:" << right << endl;

    if(left < r)
        quickSortMidPivot(vec, left, r);
    if(l < right)
        quickSortMidPivot(vec, l, right);

}

//in main
quickSortMidPivot(dsVector, 0, dsVector.size() - 1);

mcount is a global just so that I can count number of recursive calls. Help figure out most effective implementation...

Here is some debug info. 

When run on even sized vector.
Test values are (PRE-SORTING):
8 4 6 5 2 4 1 2
PivotValue:5

swap:8&2
2 4 6 5 2 4 1 8
swap:6&1
2 4 1 5 2 4 6 8
swap:5&4
2 4 1 4 2 5 6 8
left:0 r:4
l:5 right:7

PivotValue:1

swap:2&1
1 4 2 4 2
left:0 r:0
l:1 right:4

PivotValue:2

swap:4&2
2 2 4 4
swap:2&2
2 2 4 4
left:1 r:1
l:3 right:4

PivotValue:4

swap:4&4
4 4
left:3 r:3
l:4 right:4

PivotValue:6

swap:6&6
5 6 8
left:5 r:5
l:7 right:7

# Recursions:5 0


Data Sorted.

Sorted test values are (POST-SORTING):
1 2 2 4 4 5 6 8

Here is case with odd sized array (9). Works 90% of time.

Test values are (PRE-SORTING):
7 7 5 6 5 8 9 5 8
PivotValue:5

swap:7&5
5 7 5 6 5 8 9 7 8
swap:7&5
5 5 5 6 7 8 9 7 8
swap:5&5
5 5 5 6 7 8 9 7 8
left:0 r:1
l:3 right:8

PivotValue:5

swap:5&5
5 5
left:0 r:0
l:1 right:1

PivotValue:8

swap:8&8
6 7 8 9 7 8
swap:9&7
6 7 8 7 9 8
left:3 r:6
l:7 right:8

PivotValue:7

swap:7&7
6 7 8 7
left:3 r:4
l:5 right:6

PivotValue:6

swap:6&6
6 7
left:3 r:2
l:4 right:4

PivotValue:8

swap:8&7
7 8
left:5 r:5
l:6 right:6

PivotValue:9

swap:9&8
8 9
left:7 r:7
l:8 right:8

# Recursions:7 0


Data Sorted.

Sorted test values are (POST-SORTING):
5 5 5 6 7 7 8 8 9

Here is print output for when odd sized (9) vector input causes crash.

Test values are (PRE-SORTING):
8 3 2 3 9 3 8 1 5
PivotValue:9

swap:9&5
8 3 2 3 5 3 8 1 9
left:0 r:7
l:8 right:8

PivotValue:3

swap:8&1
1 3 2 3 5 3 8 8
swap:3&3
1 3 2 3 5 3 8 8
swap:3&3
1 3 2 3 5 3 8 8
left:0 r:2
l:4 right:7

PivotValue:3

swap:3&2
1 2 3
left:0 r:1
l:2 right:2

PivotValue:1

swap:1&1
1 2
swap:2&0
1 0
swap:3&0
1 0
swap:3&1
1 0
swap:5&0
1 0
swap:3&1
1 0
swap:8&0
1 0
swap:8&0
1 0
swap:9&0
1 0
swap:7274596&0
1 0
swap:666050571&0
1 0
swap:369110150&0
1 0
swap:1&0
1 0
swap:1&0
1 0
swap:110&0
1 0
swap:649273354&0
1 0
swap:134229126&0
1 0
swap:3764640&0
1 0
swap:2293216&0
1 0
swap:8&0
1 0
swap:2&0
1 0
swap:649273354&0
1 0
swap:134229127&0
1 0
swap:3764672&0
1 0
swap:3764608&0
1 0
swap:3&0
1 0
swap:649273354&0
1 0
swap:134229127&0
1 0
swap:3764704&0
1 0
swap:3764640&0
1 0
swap:2&0
1 0
swap:649273354&0
1 0
swap:134229127&0
1 0
swap:3764736&0
1 0
swap:3764672&0
1 0
swap:3&0
1 0
swap:649273354&0
1 0
swap:134229127&0
1 0
swap:3764768&0
1 0
swap:3764704&0
1 0
swap:9&0
1 0
swap:649273354&0
1 0
swap:134229127&0
1 0
swap:3764800&0
1 0
swap:3764736&0
1 0
swap:3&0
1 0
swap:6619252&0
1 0
swap:649273354&0
1 0
swap:134229127&0
1 0
swap:3764832&0
1 0
swap:3764768&0
1 0
swap:8&0
1 0
swap:666050571&0
1 0
swap:402664583&0
1 0
swap:3765152&0
1 0
swap:3764800&0
1 0
swap:1&0
1 0
swap:900931609&0
1 0
swap:268446854&0
1 0
swap:2046&0
1 0
swap:2046&0
1 0
swap:649273354&0
1 0
swap:134229140&0
1 0
swap:2293216&0
1 0
swap:3764832&0
1 0
swap:5&0
1 0
swap:11399&0
1 0
swap:3735896&0
1 0
swap:3735896&0
1 0
swap:548610060&1
1 0
swap:50342980&0
1 0
swap:6356944&-1
1 0
swap:3735800&-2
1 0
swap:3735648&0
1 0
swap:3735648&-1
1 0
swap:3768320&0
1 0
swap:32768&1
1 0
code
  • 1,056
  • 10
  • 22
  • 1
    So what if `right` is 0 and `left` is 1? That subtraction likely isn't what you want. – chris Dec 05 '17 at 22:09
  • I suggest that you go through the output and find where it differs from what you expect. From there figure out why the difference occurs. – Code-Apprentice Dec 05 '17 at 22:12
  • 1
    When you subtract two unsigned numbers and compare the result to 0, you better be sure of the relative values. – stark Dec 05 '17 at 22:15
  • 1
    *I even copied a lot of implementations and accepted answers from the net* -- Did you see the one [posted here](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c)? – PaulMcKenzie Dec 05 '17 at 22:17
  • Thanks guys! It may be premature, but I just ran the code with your suggested changes and it seems to work. I changed the size_t to int and it seems to work now. I'll run it a bunch of more times to make sure. I believe this is why none of the solutions i found on the net worked...I changed the int to size_t for indexing thinking that int is too limiting in a 64bit world for indexing arrays. I guess size_t isn't ideal in this case since it is unsigned... Please post an answer so I can give you guys points. I want to show my appreciation. You're awesome. – code Dec 05 '17 at 22:30
  • Thank you Paul. That is an awesome post! I did not find it while searching Stack. – code Dec 05 '17 at 22:33
  • OK, it was the size_t. Changing to int works. I'm also using if(left <= right) for exit condition. The index was overflowing on subtraction. – code Dec 05 '17 at 22:38
  • I have not really dug through this much but wouldn't it make sense for "if(right - left < 1)" to use a <= instead? No more point in sorting 1 element than there is in sorting 0. – SoronelHaetir Dec 05 '17 at 22:49

0 Answers0