Рекурсивная быстрая сортировка, испытывающая исключение StackOverflowException

Question

Я работаю над реализацией метода рекурсивной быстрой сортировки в классе GenericList. У меня будет второй метод, который принимает compareDelegate для сравнения разных типов, но для целей разработки я сортирую GenericList <<code>int>.

Я получаю области переполнения стека в разных местах в зависимости от размера списка.

Я часами смотрю и просматриваю этот код, и, возможно, мне просто нужна свежая пара (более опытных) глаз. Я определенно хочу узнать, почему он сломан, а не просто как его починить.

public void QuickSort()
{
    int i, j, lowPos, highPos, pivot;
    GenericList<T> leftList = new GenericList<T>();
    GenericList<T> rightList = new GenericList<T>();
    GenericList<T> tempList = new GenericList<T>();

    lowPos = 1; highPos = this.Count;
    if (lowPos < highPos)
    {
        pivot = lowPos;
        for (i = 2; i <= highPos; i++)
        {
            if (this[i].CompareTo(this[pivot]) <= 0)
                leftList.Add(this[i]);
            else
                rightList.Add(this[i]);
        }
        leftList.Add(this[pivot]);
        leftList.QuickSort();
        rightList.QuickSort();

        for(i=1;i<=leftList.Count;i++)
            tempList.Add(leftList[i]);
        for(i=1;i<=rightList.Count;i++)
            tempList.Add(rightList[i]);

        this.items = tempList.items;
        this.count = tempList.count;
    }

}

Готовая продукция:

public void QuickSort()
{
    Random random = new Random();
    int i, j, lowPos, highPos, pivot;
    GenericList<T> leftList = new GenericList<T>();
    GenericList<T> rightList = new GenericList<T>();
    GenericList<T> tempList = new GenericList<T>();

    if (this.Count > 1)
    {
        pivot = random.Next(1,this.Count);
        for (i = 1; i <= this.Count; i++)
        {
            if (i == pivot) continue;
            if (this[i].CompareTo(this[pivot]) < 0)
                leftList.Add(this[i]);
            else
                rightList.Add(this[i]);
        }
        leftList.QuickSort();
        rightList.QuickSort();

        for(i=1;i<=leftList.Count;i++)
            tempList.Add(leftList[i]);
        tempList.Add(this[pivot]);
        for(i=1;i<=rightList.Count;i++)
            tempList.Add(rightList[i]);

        this.items = tempList.items;
        this.count = tempList.count;
    }

}

Answer 1

Ваша реализация включает в себя стержень в ваших подсписках. Включив сводку в свои подсписки (в данном случае в ваш левый список, потому что ваше условие <=), вы настраиваете себя на возможную бесконечную рекурсию, если эта сводка окажется в середине подсписка. </p>

Пример:

1. Список = [3, 6, 12 , 4, 8] Pivot = 3 ( 12 ) Слева = [3, 6, 12 , 4 , 8] Справа = [Пусто]
2. Список = [3, 6, 12 , 4, 8] Pivot = 3 ( 12 ) Слева = [3, 6, 12 , 4 , 8] Справа = [Пусто]
3. Список = [3, 6, 12 , 4, 8] Pivot = 3 ( 12 ) Слева = [3, 6, 12 , 4 , 8] Справа = [Пусто]
4. ... Бесконечный цикл

Поскольку сводная точка не исключена (хотя ее конечная позиция известна), она может привести к тому, что вы сортируете один и тот же список снова и снова навсегда, а не уменьшаете размер списков для сортировки с каждым рекурсивным вызовом.

Если вы исключите свой свод (по индексу, а не по значению) из подсписков и добавите его обратно в окончательный список tempList между leftList и rightList, он будет работать правильно.

        ...
        for (i = 1; i <= highPos; i++)
        {
            if (i == pivot) continue; // Add this
            if (this[i].CompareTo(this[pivot]) <= 0)
        ...
        for (i = 1; i <= leftList.Count; i++)
            tempList.Add(leftList[i]);
        tempList.Add(this[pivot]); // Add this
        for (i = 1; i <= rightList.Count; i++)
            tempList.Add(rightList[i]);
        ...

См. Также: Статья в Википедии о быстрой сортировке (с псевдокодом)

Answer 2

Я бы не рекомендовал ставить точку в одну из двух групп. Если у вас есть только два равных элемента, вы можете получить бесконечный цикл. Например, если вы попытаетесь отсортировать массив {1,1}, вы должны получить бесконечный цикл, который может быть причиной переполнения вашего стека. Большинство быстрых сортировок избегают этого, меняя шарнир с элементом на краю и затем сортируя остальную часть массива. Другой способ справиться с этим - вставить строку, чтобы убедиться, что вы не добавили сводку в leftList, например

if(i != pivot)

Затем вы добавили бы сводную таблицу в tempList между добавлением leftList и rightList.

Edit:

Ник прав, потому что вы получите проблему для других случаев, таких как {5,2}. Однако, даже если вы исправите текущую проблему, не помещая сводную таблицу в список, который будет снова отсортирован, вы можете убедиться, что ваш код может обрабатывать повторяющиеся элементы. Большой массив с таким же числом даст вам O (N ^ 2) временную сложность, и если N достаточно велико, вы получите переполнение стека.

Answer 3

Вы можете получить представление из этой серии блогов:

http://reprog.wordpress.com/2010/04/25/writing-correct-code-part-1-invariants-binary-search-part-4a/

http://reprog.wordpress.com/2010/04/27/writing-correct-code-part-2-bound-functions-binary-search-part-4b/

http://reprog.wordpress.com/2010/04/30/writing-correct-code-part-3-preconditions-and-postconditions-binary-search-part-4c/

Когда вы закончите с этим, проследите свой код в уме с помощью набора входных данных {1, 2} и скажите мне, каков будет результат.

Answer 4

Посмотрите, что произойдет, если у вас есть List, содержащий [5,2]. Ваш pivot будет равен 1, поэтому используемое для сравнения значение будет 5. Строка this[i].CompareTo(this[pivot]) <= 0 будет True, а число 5 будет помещено в leftList. Ваше следующее сравнение с 2 также будет True, поместив 2 в leftList. Теперь ваш leftList будет в точности тем, с чего он начинался: [5,2], который вы снова и снова будете называть QuickSort ... и он получится точно такой же, как и тошнотворный: StackOverflow.