Как предотвратить переполнение стека в моем алгоритме рекурсивной быстрой сортировки - PullRequest
Новая
       37

Как предотвратить переполнение стека в моем алгоритме рекурсивной быстрой сортировки

0 голосов
/ 07 мая 2019

При работе с двусвязными списками, размер которых превышает 5000, я получаю ошибку переполнения стека.Мой алгоритм создает 2 новых объекта двусвязного списка для каждой рекурсии, которые добавляются в отсортированный список после каждой рекурсии.Есть ли альтернативный способ создания объекта, чтобы мне не приходилось делать это в каждой рекурсии быстрой сортировки? 

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);
            }
        }

1 Ответ

0 голосов
/ 08 мая 2019

Чтобы предотвратить переполнение стека, создайте два счетчика, скажем, имена left_counter и right_counter.Во время шагов раздела обновите счетчики так, чтобы left_counter = количество узлов от первого до pivot или pivot.prev, а right_counter - количество узлов от pivot или pivot.next до последнего.Сравните два счетчика и используйте рекурсию в подсписке, который соответствует меньшему количеству.Затем обновите first = pivot.next или last = pivot.prev в зависимости от того, какая часть была отсортирована (с помощью рекурсии) и вернитесь к началу кода для продолжения.

Во время сортировки может произойтиПроще создать круговой двусвязный список, чтобы first.prev указывал на последний узел, а last.next - на первый узел.Это избавило бы от необходимости выполнять проверку на нулевые значения при замене узлов на или рядом с первым или последним узлом.

Код показывает использование типа класса с именем List, но обычно это собственный класс для C # с возможностьюиндексировать (произвольный доступ) элементы в «списке», аналогичном массиву.Вероятно, следует использовать другое имя для класса списка, например, «DLList» для двусвязного списка.

...