StackOverflowException when perform Quicksort with ordered list

Question

I'm implementing Quick sort algorithm in C#. Implementation as follow:

    /// <summary>
    /// Perform Sort
    /// </summary>
    /// <returns></returns>
    public override List<int> Sort(List<int> list)
    {
        try
        {
            this.quick(ref list, 0, list.Count - 1);

            return list;
        }
        catch (Exception)
        {                
            throw;
        }
    }

    /// <summary>
    /// Quick sort main algorithm
    /// </summary>
    /// <param name="list"></param>
    /// <param name="left"></param>
    /// <param name="right"></param>
    private void quick(ref List<int> list, int left, int right)
    {
        try
        {
            int i, j;
            int x, y;
            i = left;
            j = right;
            x = list[left];

            do
            {
                while (list[i] < x && i < right)
                {
                    i++;
                }

                while (list[j] > x && j > left)
                {
                    j--;
                }

                if (i <= j)
                {
                    y = list[i];
                    list[i] = list[j];
                    list[j] = y;

                    i++;
                    j--;
                }
            }
            while (i <= j);

            if (left < j)
            {
                this.quick(ref list, left, j);
            }

            if (i < right)
            {
                this.quick(ref list, i, right);
            }
        }
        catch (Exception)
        {                
            throw;
        }
    }

If I call Sort and pass in an unordered list, it works ok. But if I pass in an ordered list, a StackOverflowException occur. I tried to figure out why is it but still have no clue. So please point out for me what wrong did I do.

Update

I found the cause of error: at the first recursion, the algorithm set j = -1, so that i will never meet j, and led to StackOverflow. So how to get rid of this behavior? I mean is there anyway to figure out that the list that has been passed in is an ordered list and terminate the algorithm?

Did you try debuging your failing case? Looks like the recursion does not hit the end. — MarcinJuraszek
– MarcinJuraszek, Commented Dec 6, 2013 at 2:55
@SimonWhitehead the error only occur when you pass in an ordered list — Doan Cuong
– Doan Cuong, Commented Dec 6, 2013 at 3:01
I passed in a list of 1, 5, 4 and it worked fine.. then I passed in 1,4,5 and it was fine.. — Simon Whitehead
– Simon Whitehead, Commented Dec 6, 2013 at 3:02

Amadan · Accepted Answer · 2013-12-06 03:04:19Z

1

Without inspecting your code...

The naive quicksort has best-case complexity of O(n log n), but worst case of only O(n). The worst case is (you guessed it) when the list is sorted. On a sorted collection, the pivot chosen as the leftmost element will separate a sublist into an empty list and everything else, and then recurse into a sublist that is just one element less than the original (the pivot). Thus, your stack depth needs to be at least the same as the number of elements you're sorting. So if you have a largish collection, a StackOverflowException is not unexpected.

The only fix, really, is not using the naive quicksort. You can detect if the collection is sorted or nearly sorted and switch to another algorithm; or you can use another method of choosing a median that will decrease the likelihood of the degenerate case (for example, while sorted collections are commonly possible, such collections that will trigger a degenerate case when you select the middle element instead of the left one as pivot are much rarer). Cases where you expect near-sorted collections to be common can also benefit from three-value-median method of pivot selection; many more variations are possible.

EDIT: If you have a bug in your code, that is a pretty good source of errors too :P An empty list is sorted by default - nothing to do, move along... Same with one-element lists. So if you just have a check if right is before or at left and return early without changing it, your bug should go away. It's as simple as

if (right < left) return;

answered Dec 6, 2013 at 3:04

Amadan

200k23 gold badges252 silver badges321 bronze badges

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

2 Comments

Doan Cuong Over a year ago

Thank you very much for help me understand the downside of quick sort. But I have one more thing want to ask. Can you suggest me a technique to detect if the collection is sorted or nearly sorted?

Amadan Over a year ago

One way to do it is to loop through the collection and see how many adjacent items are in the wrong order. It does increase execution time, obviously. But as I said, the degenerate case can be mitigated. In case the data is random, you have a random, but very small chance of getting the O(n) But given that humans manipulate data, not all orders are equally probable. Thus, selecting a pivot not from left, but from the center of the sublist, or randomly, or as a median from left/center/right, will severely decrease the probability of the degenerate case, without impacting speed too much.

Collectives™ on Stack Overflow

StackOverflowException when perform Quicksort with ordered list

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related