QuickSort vs. Sort Sort в Linded List: Performance

cs.stackexchange https://cs.stackexchange.com/questions/1354

Вопрос

Я написал программу для сортировки связанных списков, и я заметил, что моя сортировка вставки работает намного лучше, чем мой алгоритм QuickSort. У кого -нибудь есть идеи, почему это? Вставка сортирует сложность $ theta (n^2) $ и QuickSort $ O (n log n) $, поэтому QuickSort должен быть быстрее. Я попытался для случайного размера ввода, и это показывает мне наоборот. Странный...

Здесь код на Java:

public static LinkedList qSort(LinkedList list) {

    LinkedList x, y;
    Node currentNode;
    int size = list.getSize();

    //Create new lists x smaller equal and y greater
    x = new LinkedList();
    y = new LinkedList();

    if (size <= 1)
        return list;
    else {

        Node pivot = getPivot(list);
        // System.out.println("Pivot: " + pivot.value);     
        //We start from the head
        currentNode = list.head;

        for (int i = 0; i <= size - 1; i++) {
            //Check that the currentNode is not our pivot
            if (currentNode != pivot) {
                //Nodes with values smaller equal than the pivot goes in x
                if (currentNode.value <= pivot.value) {
                    {
                        x.addNode(currentNode.value);
                        // System.out.print("Elements in x:");
                        // x.printList();
                    }

                } 
                //Nodes with values greater than the pivot goes in y
                else if (currentNode.value > pivot.value) {
                    if (currentNode != pivot) {
                        y.addNode(currentNode.value);
                        // System.out.print("Elements in y:");
                        // y.printList();
                    }
                }
            }
            //Set the pointer to the next node
            currentNode = currentNode.next;
        }

        //Recursive calls and concatenation of the Lists and pivot
        return concatenateList(qSort(x), pivot, qSort(y));

    }
}
Это было полезно?

Решение

Ответ Педро охватывает, что идет не так с вашей первой попыткой. Но я хочу поговорить о нескольких вещах, когда дело доходит до анализа алгоритмов, которые могут быть немного тонкими.

Какой у вас алгоритм?

Прежде чем вы сможете начать анализ алгоритма, вам нужно точно сказать, что вы делаете. «QuickSort», например, может означать ряд разных вещей. Основной шаблон:

  • Выберите вращаться элемент
  • Профила Вход вокруг стержня
  • Рекурсивно сортировать кусочки
  • Комбинировать Подпроблемы

Даже на этом уровне есть некоторая двусмысленность, так как я на самом деле не описал, как выбрать опорку и как разделить. В современную эпоху, что, вероятно, означает около 20 лет, люди думают, что вы:

  • Выберите стержень в случайном порядке
  • Пари в «меньше, чем», «равное» и «больше, чем» пьесы

В этом случае количество сравнений составляет $ o (n log n) $ в ожидании и близко к информационным теоретическим границам.

Но! Обратите внимание, что вы и некоторые комментаторы хотели бы выбирать ключ и другие способы, поэтому все еще важно сказать, что вы действительно имеете в виду. Выбор поворота детерминированно означает, что есть случаи (в зависимости от вашего правила), которые будут намного хуже.

Какие у вас примитивы?

Даже как вы решили, что вы В самом деле Хотите сделать ваш алгоритм, вам нужно подумать о «основных шагах». Для QuickSort нам нужно:

  • Способ выбрать стержень
  • Способ сравнить элементы
  • Способ раздела
  • Способ объединить

Обратите внимание, что большинство анализа сортировки направлены на подсчет сравнений. Мы поговорим о том, почему это дальше.

Сколько стоят ваши примитивы?

Наконец, в любом подробном анализе времени работы вам нужна модель вычислений, в которой вы можете считать «операции». Наиболее популярной моделью для алгоритмов является «ОЗУ», которая имеет массивы с чтением/записи постоянного времени, обычными арифметическими операциями и целочисленными сравнениями. (Но есть много других.)

Для обычного анализа QuickSort, при входе в длину $ n $, вы захотите:

  • Выбор олова, чтобы быть $ O (n) $
  • Разделение, чтобы быть $ O (n) $
  • Объединение суб-маячников, чтобы быть $ O (n) $

Вы можете сделать это с связанными списками (как во второй попытке) или (более обычно) массивов, но фактические реализации будут Очень разные. Анкет Проблема в том, что в вашей первой попытке (в соответствии с другими ответами) вы тратили $ omega (n^2) $ на разбиение, что меняет сложность много.

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

Причина, по которой я все это записал, заключается в том, что даже в вашей плохой реализации вы не делали больше сравнения. Анкет Большая часть усилий по анализу алгоритмов сортировки на основе количества сравнений Только Сравнения по нескольким причинам:

  • Это очень общее (машинный независимый)
  • Для большинства алгоритмов в этом классе разумная реализация может «заряжать» любую другую операцию с сравнением таким образом, чтобы каждое сравнение получило операции $ O (1) $

Эта вторая часть - то, где ваша первая попытка упала. Надеюсь это поможет.

Даже больше

До сих пор все еще было теорией. Практические алгоритмы сортировки на самом деле должны быть опробованы на реальных машинах. Это целая область, и я понимаю, что нынешний чемпион не является одним из стандартных алгоритмов, а то, что называется «Тимскорт», который вы можете найти здесь http://svn.python.org/projects/python/trunk/objects/listsort.txt

Другие советы

Проблема заключается в том, что анализ QuickSort, как вы его реализовали, предполагает, что доступ к любому элементу может быть выполнен по постоянной стоимости, то есть в $ MathCal O (1) $. Это не тот случай с связанными списками.

Обратите внимание, что на вершине while (right > left) { цикл в вашем коде, вы прокатитесь по всем элементам до тех пор, пока left а затем неоднократно прокатится через все элементы, регулирующие right. Анкет В то время как в QuickSort это должно стоить всего лишь матча $ mathcal o (n) $, в вашем случае он стоит дороже $ mathcal o (n^2) $, где $ n $ - текущий уровень рекурсии и $ n $ это общее количество элементов.

В качестве Луис В комментариях ниже указано, что есть связанный список аналогов QuickSort, но он должен быть реализован совершенно иначе, чем то, что вы сделали.

Суть: связанные списки не являются массивами, а алгоритмы, которые будут хорошо работать на массивах, не обязательно будут хорошо работать в связанных списках. Есть несколько хороших книг по алгоритмам, которые укажут вам на хорошие алгоритмы для каждого случая.

Обновлять

Код в вопросе был изменен для отражения реализации, описанной Луис ниже. Однако в выборе Pivot все еще существует потенциальная неэффективность. По сути, любая отдельная операция внутри основной петли, которая нет $ mathcal o (1) $ испортит асимптотическое поведение.

О, и создание новых списков на каждом уровне рекурсии, вероятно, также не чрезвычайно эффективно.

Самый простой способ сортировки списков - это Mergesort: разделите список на половины (просто застегивается вниз, один элемент слева, один справа), рекурсивно сортируйте влево и правое, затем слияйте (возьмите меньшие из первых элементов левого и правого списка)) Анкет Хорошо подходит для списков (только линейных попереков, в основном жонглирования указателями) и $ theta (n log n) $.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с cs.stackexchange
scroll top