Stack overflow in quicksort

Question

Before starting, I just want to say that I've spent the last 2 hours or so reading SO post about "Quicksort" and "stack overflow", so I'm not just asking randomly, I literally don't know what to do anymore...

Ok, I have to implement a quick sort algorithm and for some reason I couldn't find, I keep getting stack overflow errors. I'm using VS2010, so I've debugged it from beginning to end.

So, here's my code:

const int THRESHOLD = 1;

std::vector<int> data = *new std::vector<int>();

void GetPivotPoint( bool first, int leftBound, int rightBound, int& pivotID )
{
    if( first ) // We are choosing the first element as a pivot
    {
        pivotID = 0;
        return;
    }
    else // We are choosing the median between 1, n/2 and n for our pivot
    {
        int left = leftBound;
        int right = rightBound;
        int center = ( left + right ) / 2;

        if( data[center] - data[left] < 0 ) data_manip::Swap( data, left, center );
        if( data[right] - data[left] < 0 ) data_manip::Swap( data, left, right );
        if( data[right] - data[center] < 0 ) data_manip::Swap( data, center, right );

        data_manip::Swap( data, center, right );
        pivotID = right;
    }
}

int Partition( int left, int right )
{
    int pivotID = 0;
    GetPivotPoint( true, left, right, pivotID );
    int pivot = data[pivotID];

    int i = left - 1;
    int j = right + 1;

    while( i < j )
    {
        i++;
        while( data[i] < pivot ) i++;
        j--;
        while( data[j] > pivot ) j--;

        if( i < j )
        {
            data_manip::Swap( data, i, j );
        }
    }

    return j;
}

void Quicksort( int left, int right )
{
    if( left + THRESHOLD > right )
    {
        algo::Bubblesort( data, left, right );
    }
    else
    {
        int partitionPoint = Partition( left, right );

        Quicksort( left, partitionPoint );
        Quicksort( partitionPoint + 1, right );
    }
}

and here's the implementation of the Swap() method

inline void Swap( std::vector<int>& data, int p1, int p2 )
    {
        int temp = data[p1];
        data[p1] = data[p2];
        data[p2] = temp;
    }

I'm using set with over 1k and up to 500K in them. Also, in this particular code, I'm using the option to get the first element as a pivot, now I know that this isn't optimal, but I need to test that option too. If I do use the median-of-three instead of the first element, than I don't get a stack overflow, however, what could be causing it when I do use the first element as pivot.

Tanks for the help

"for some reason I couldn't find" - that'll be recursion. The stack has a limited size, and each recursive call eats a lump of it. (Using median-of-three, you're less likely to encounter quicksort's pathological worst case, and so less likely to recurse too deeply.) — Mike Seymour
– Mike Seymour, Commented Feb 10, 2014 at 23:38
Is this for your own learning purposes? Otherwise, std::sort. — Chad
– Chad, Commented Feb 10, 2014 at 23:39
Knuth and Sedgewick both mention that it's better to recurse on the smaller partition first, to save stack growth. Most implementations use insertion sort below the threshold. Bubble sort has nothing to recommend it in this or any other application. — user207421
– user207421, Commented Feb 10, 2014 at 23:43
The following isn't the source of your stack overflow but it is bad code and a memory leak. When you create your vector just do std::vector<int> data; and nothing else. The way you are using new is a memory leak and a very odd practice. — Blastfurnace
– Blastfurnace, Commented Feb 10, 2014 at 23:47

Tushar Jadhav · Accepted Answer · 2014-02-11 00:00:47Z

1

You get stack overflow because of the below line. It is subtle but very important. You have to add the lower offset to the mid value that you calculate.

int center = ( left + right ) / 2;

Try this instead :

int center = left + (right - left) / 2;

///////////////////////////////////////////////////////////////////////////////////////////

Also, I have a simple and elegant implementation. It is templated it so that it will work with any data type. This solution makes use of C++11 move semantics and good API design.

You can optimize it by performing Insertion Sort or Bubble Sort if the array size is less than maybe 7 items which is a good idea since QuickSort itself is too much overhead for small array sizes

#include <vector>
#include <memory>

template <typename Item>
bool less(Item v, Item w)
{
    // Below line is written assuming that you data implements compareTo method
    // You can also replace it with simple v < w
    return v.compareTo(w) < 0;
}

template <typename Item>
void exch(std::vector<std::shared_ptr<Item>> &arr, int i, int j)
{
    if (i == j) return;

    arr[i].swap(arr[j]);
}

template <typename Item>
class QuickSort
{
public:
    static void sort(std::vector<std::shared_ptr<Item>> &arr)
    {
        sort(arr, 0, arr.size() - 1);
    }

private:
    static void sort(std::vector<std::shared_ptr<Item>> &arr, int lo, int hi)
    {
        if (hi <= lo) return;
        int j = partition(arr, lo, hi);
        sort(arr, lo, j - 1);
        sort(arr, j + 1, hi);
    }

    static int partition(std::vector<std::shared_ptr<Item>> &arr, int lo, int hi)
    {
        int i = lo, j = hi + 1;

        while (true)
        {
            // Find item on left to swap
            while (less((*arr[++i]), (*arr[lo])))
                if (i == hi) break;

            // Find item on right to swap
            while (less((*arr[lo].get()), (*arr[--j].get())))
                if (j == lo) break;

            // Check if pointers swap
            if (i >= j) break;

            // Swap
            exch(arr, i, j);
        }

        // Swap with partitioning item
        exch(arr, lo, j);

        return j;
    }
};

edited Feb 11, 2014 at 0:00

answered Feb 10, 2014 at 23:55

Tushar Jadhav

3555 silver badges14 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

daniel gratzer Over a year ago

Nitpick, a class with just static members is really just a namespace.

Tushar Jadhav Over a year ago

I agree. This can be improved by making the methods as non-static or not using class at all. I just wanted to expose only one API to sort and hide the private methods from clients.

Collectives™ on Stack Overflow

Stack overflow in quicksort

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related