How to prevent stack overflow in my recursive quicksort algorithm

Question

When dealing with doubly-linked-lists above size 5000, I get a stack overflow error. My algorithm creates 2 new objects of the doubly-linked-list each recursion which are appended to the sorted list after each recursion. Is there an alternate way to create an object so that I don't have to do it in each recursion of the quick sort?

static void quick_sort(List sortList, Node first, Node last)
        {
            //Quick sort algorithm
            Node left, pivNode;
            List bigList = new List();
            List endList = new List();
            int pivot;              
            pivNode = first;        //Sets node to become pivot (1st node in given range)
            left = first.next;      //Sets comparison node
            pivot = first.data;     //Sets integer for pivot

            if (last.next != null)
            {
                //Creates a new list if there are nodes after last node
                endList.firstNode = last.next;
                last.next = null;
                endList.firstNode.prev = null;
            }

            if (left != null)
            {
                do
                {
                    if (left.data > pivot)
                    {
                        Node popNode;
                        popNode = left;
                        removeNode(popNode, sortList);           //Removes node larger than pivot from sortList
                        left = pivNode;                         //Resets left node to pivNode
                        if (bigList.firstNode == null)          //Inserts larger node into bigList
                        {
                            insertBeginning(popNode, bigList);
                        }
                        else
                        {
                            popNode.next = popNode.prev = null;
                            insertEnd(popNode, bigList);
                        }
                    }

                    if (left.data <= pivot)
                    {
                        swapNode(left, pivNode);        //Swaps smaller node with pivNode(moves smaller nodes to left of list)
                        pivNode = left;                 //Resets pivNode to correct node
                    }

                    left = left.next;

                } while (left != last.next);            //Iterates until last given node
            }


            if (endList.firstNode != null)
            {
                //If endList exists
                if (bigList.firstNode != null)
                {
                    //If bigList exists
                    appendLists(bigList, endList);  //Appends endList at end of bigList
                }
                else
                {
                    //If bigList doesn't exist, changes it to endList
                    bigList = endList;              
                }
            }

            appendLists(sortList, bigList);         //Appends bigList to end of sortList

            if (endList.firstNode != null)
            {
                last = endList.firstNode.prev;     //Set's correct last node 
            }

            //Recursion until last has been fully sorted
            if (pivNode.prev != first && pivNode != first)
            {
                quick_sort(sortList, first, pivNode.prev);
            }
            if (pivNode != last && first != last)
            {
                quick_sort(sortList, pivNode.next, last);
            }
        }

"_How to prevent stack overflow in my recursive quicksort algorithm_" You need an stop/exit condition where your method decides not to call itself recursively anymore... — , May 07 '19 at 19:03
Since you have some stop conditions (`if` statements) in your code already, something clearly is not going as you expect, making the stop conditions ineffective. Use the [debugger](https://learn.microsoft.com/en-gb/visualstudio/debugger/navigating-through-code-with-the-debugger) and analyze the state of the program (especially the values of all the variables in your recursive method) when the StackOverflowException throws... — , May 07 '19 at 19:04
My professor stated that we have to use recursion for this task unfortunately. And just to clarify, the problem isn't caused by the creation of too many objects from my class? — lem1, May 07 '19 at 19:09
I've tested the code with smaller lists (sizes up to 5000) and they have all worked correctly as the if statements will eventually lead to the end of the recursion. This lead me to believe that the problem isn't with the stop condition. — lem1, May 07 '19 at 19:11
With regard to your last comment, it could be that if you have huge amounts of elements to sort, then your recursion might become too deep, i.e., the call stack becoming exhausted and thus triggering the SO exception. The solution out of this problem is normally to avoid such very deep recursions, which means converting your algorithm into an iterative algorithm. (If your prof forbade you to use an iterative approach, you will have to limit yourself to "not so large lists", or increase the call stack size: https://stackoverflow.com/questions/2556938/how-to-change-stack-size-for-a-net-program) — , May 07 '19 at 19:39
Recursion always has a risk to end up with stack overflow under conditions of multiple recursive calls (the actual limit depends on platform/technology stack limitations). That's why many modern compilers are able to optimize tail-recursive methods into iterative methods and this technique is treated as safe enough. Unfortunately that's not a case for C# compiler so you'll have to deal with fact that you have a risk to get stack overflow or you need to remake your method to use trampolining which is closest to recursion technique and which guarantees stack safety. — Dmytro Mukalov, May 07 '19 at 19:40
Okay, at least this has improved my understanding on recursion and it's limitations. Thanks for the help. — lem1, May 07 '19 at 19:45
Your prof said you had to use recursion. Did he/she also say you had to use a list of a certain minimum size? And to not bump up the call stack size? Usually the primary point of the exercise is to get a good understanding of recursion, not to write a high performance, industrial strength piece of software. There *will* be limits. — MickeyfAgain_BeforeExitOfSO, May 07 '19 at 21:38

rcgldr · Answer 1 · 2019-05-09T09:34:28.777

To prevent stack overflow, create two counters, say the names are left_counter and right_counter. During the partition steps, update the counters so that left_counter = number of nodes from first to pivot or pivot.prev, and right_counter is number of nodes from pivot or pivot.next to last. Compare the two counters and use recursion on the sub-list that corresponds to the smaller count. Then update first = pivot.next or last = pivot.prev depending on which portion was sorted (via recursion) and loop back to the top of the code to continue.

During the sort, it might be simpler to create a circular doubly linked list, so that first.prev points to the last node and last.next points to the first node. This would eliminate having to do check for nulls when swapping nodes at or next to first or last node.

The code shows using a class type called List, but that is normally a native class for C#, with the ability to index (random access) elements in the "list", similar to an array. A different name should probably be used for the list class, perhaps, "DLList" for doubly linked list.

How to prevent stack overflow in my recursive quicksort algorithm

1 Answers1