QuickSort algorithm failed with stackoverflow error

Question

I tried to implement QuickSort algorithm from Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein - Introduction to Algorithms, Third Edition - 2009 * Section 7.1

in JavaScript.

So here is my implementation:

function swap(arr, i, j) {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

function partition(arr, left = 0, right = arr.length - 1) {
    let pivot = arr[right];
    let i = left - 1;
    let j;

    for (j = left; j < right; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr, i, j);
        }
    }

    swap(arr, i + 1, right);
    return i + 1;
}

function quickSort(arr, left = 0, right = arr.length - 1) {
    if (left >= right) return arr;
    const p = partition(arr, left, right);
    quickSort(arr, left, p - 1);
    quickSort(arr, p + 1, right);
    return arr;
}

The problem with this code that it fails with stackoverflow error IF i pass already sorted array with length > 10 000

In case i pass array with fully random integers - everything working like expected even with 50 000 elements. So i can't understand is it problem with my code, or my node just can't handle such big call stack for worst-case quick sort usage.

Already sorted arrays can be a problem for naive versions of quicksort. The algorithm is typically O(n log n), but the worst case performance is O(n^2) with a stack depth of O(n). — dmckee --- ex-moderator kitten
– dmckee --- ex-moderator kitten, Commented Jun 22, 2019 at 16:32

Nicholas Tower · Accepted Answer · 2019-06-22 16:40:33Z

4

With large enough arrays, you will eventually reach the maximum stack size and get that exception. The reason you're seeing it on sorted arrays earlier is because of the way you're choosing your pivot.

You've implemented it with your pivot as the last element of the array, which happens to mean that your worst case scenario occurs when you're given a sorted array. Your pivot value is always the largest value (or smallest if sorted in the opposite direction), and thus every element is less than the pivot, with none greater. So rather than splitting the array into two roughly equal subarrays, you split it into a single sub array that has only one fewer element than you started with.

One way to choose the pivot to avoid this is to pick the pivot randomly. This makes it unlikely (but not impossible) to hit the worst case, and so on average will work well. It does have a vulnerability in that if someone knows the random number algorithm and seed that you're using, then they can craft an array which will force you into the worst case.

The ideal pivot is the median value. So one approach is to try to find the median or close to it. For example, you can take a sample of 3 random elements of the array, and use the median of those 3 as your pivot. This is unlikely to be exactly the median but is good enough most of the time. You could sample more to get a better approximation of the median, but then you're spending more time trying to find the pivot than just moving forward with the algorithm; it's a bit of a tradeoff.

edited Jun 22, 2019 at 16:40

answered Jun 22, 2019 at 16:31

Nicholas Tower

87.1k10 gold badges115 silver badges127 bronze badges

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

1 Comment

Vololodymyr Over a year ago

thank you, now I see. I thought quicksort is a best choice, but now i see what is the problem with this algorithm. Even if i choose pivot index as random value - it might fail in very rare cases. To avoid this problem I need to analyze array somehow before doing actual sorting. Thats why most programming language use mergesort variations as default sort implementation.

Bergi · Accepted Answer · 2019-06-22 16:33:54Z

3

it fails with stackoverflow error IF i pass already sorted array with length > 10 000

The problem - as usual with quicksort - is the choice of the pivot element. You are taking pivot = arr[right], so in an already-sorted array the partition function will divide the range into [left, right-1] and [right, right]. Your binary tree of recursive calls degenerates to a list, and 10 000 recursive calls are too much for the stack.

Alternatives are choosing the pivot index randomly (which is unlikely, but not impossible, to fail), or to find the median value.

answered Jun 22, 2019 at 16:33

Bergi

671k162 gold badges1k silver badges1.5k bronze badges

Comments

rcgldr · Accepted Answer · 2019-06-22 19:53:52Z

No matter what pivot you pick, there's always a chance of stack overflow. To avoid this, here is an example C++ quicksort function that uses recursion on the smaller part, then loops back for the larger parts. This limits stack space to O(log(n)), but worst case time complexity remains at O(n^2).

void QuickSort(uint64_t a[], int lo, int hi)
{
    while (lo < hi){
        uint64_t p = a[hi];
        int i = lo;
        for (int j = lo; j < hi; ++j){
            if (a[j] < p){
                std::swap(a[j], a[i]);
                ++i;
            }
        }
        std::swap(a[i], a[hi]);
        if(i - lo <= hi - i){
            QuickSort(a, lo, i-1);
            lo = i+1;
        } else {
            QuickSort(a, i+1, hi);
            hi = i-1;
        }
    }
}

Collectives™ on Stack Overflow

QuickSort algorithm failed with stackoverflow error

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related