Быстрая сортировка медленнее, чем Mergesort?

Question

Вчера я работал над реализацией быстрой сортировки, а затем запустил ее, ожидая более быстрого выполнения, чем Mergesort (который я также реализовал). Я запустил два, и хотя быстрая сортировка была быстрее для небольших наборов данных <100 элементов (и я <i>проверил, что проверил, что это работает), сортировка слиянием стала более быстрым алгоритмом довольно быстро. Меня учили, что быстрая сортировка почти всегда «быстрее», чем сортировка слиянием, и я понимаю, что есть некоторые дебаты по этой теме, но я по крайней мере ожидал, что она будет ближе, чем эта. Для наборов данных> 10000 элементов сортировка слиянием была более чем в 4 раза быстрее. Это следовало ожидать, или в моем коде быстрой сортировки есть ошибка?

слияние:

public static void mergeSort(int[ ] e)
{
    if (e.length <= 1) return;
    int[] first = new int[e.length/2];
    int[] second = new int[e.length - first.length];
    System.arraycopy(e, 0, first, 0, first.length);
    System.arraycopy(e, first.length, second, 0, second.length);
    mergeSort(first);
    mergeSort(second);
    System.arraycopy(merge(first, second), 0, e, 0, e.length);
}

private static int[] merge(int[] first, int[] second) {
    int iFirst = 0;
    int iSecond = 0;
    int iCombined = 0;

    int[] combined = new int[first.length + second.length];
    while(iFirst < first.length && iSecond < second.length) {
        if (first[iFirst] > second[iSecond]) {
            combined[iCombined++] = second[iSecond++];
        }
        else combined[iCombined++] = first[iFirst++];
    }
    for(; iFirst < first.length; iFirst++) {
        combined[iCombined++] = first[iFirst];
    }
    for(; iSecond < second.length; iSecond++) {
        combined[iCombined++] = second[iSecond];
    }
    return combined;
}

быстрая сортировка:

public static void quicksort(int[] a, int first, int last) {
    if (first >= last) return;

    int partitionIndex = partition(a, first, last);
    quicksort(a, first, partitionIndex - 1);
    quicksort(a, partitionIndex + 1, last);
}

public static int partition(int[] x, int first, int last) {
    int left = first;
    int right = last;
    int pivot = x[first];
    int pivotIdx = first;

    while(left <= right) {
        while(left < x.length && x[left] <= pivot) left++;
        while(right >= 0 && x[right] > pivot) right--;
        if (left <= right) {
            int temp = x[left];
            x[left] = x[right];
            x[right] = temp;
        }
    }
    pivotIdx = right;
    x[first] = x[right];
    x[pivotIdx] = pivot;
    return pivotIdx;
}

Answer 1

Я на самом деле только что написал «демонстрационную программу сравнительного сортировки связанного списка» на C и пришел к аналогичному выводу (что сортировка слиянием превзойдет быструю сортировку для большинства применений), хотя мне сказали, что быстрая сортировка обычно не используется для связанных списков тем не мение. Я хотел бы отметить, что выбор значений сводки является фактором монстра - моя первоначальная версия использовала случайный узел в качестве стержня, и когда я немного уточнил его, чтобы взять среднее из двух (случайных) узлов, время обработки 1000000 записей увеличилось с 4 минут до менее 10 секунд, что соответствует уровню слияния.

Mergesort и quicksort имеют одинаковый большой O лучший случай (n * log (n)), и, несмотря на то, что люди могут пытаться утверждать, большая O на самом деле связана с количеством итераций, а не счетом сравнения. Самое большое различие , которое может быть получено между двумя из них, всегда будет в ущерб быстрой сортировке, и оно включает списки, которые уже в значительной степени отсортированы или содержат большое количество связей (когда быстрая сортировка работает лучше, чем сортировка слиянием, разница не будет почти такой большой). Это связано с тем, что связи или уже отсортированные сегменты упрощаются прямо через сортировку слиянием; когда два разделенных списка возвращаются для объединения, если один список уже содержит все меньшие значения, все значения слева будут сравниваться по одному с первым элементом справа, а затем (так как возвращенные списки имеют внутренний порядок) дальнейших сравнений не требуется, и право просто повторяется до конца. Это означает, что число итераций останется постоянным, но количество сравнений будет сокращено вдвое. Если вы говорите о реальном времени и сортируете строки, то сравнения стоят дорого.

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

Если вам интересно, демонстрационная программа выдаст вывод примерно так:

[root~/C] ./a.out -1 3 
Using "", 0 records
Primary Criteria offset=128

Command (h for help, Q to quit): N
How many records? 4000000
New list is 562500.00 kb

Command (h for help, Q to quit): m

Mergesorting..............3999999 function calls
123539969 Iterations     Comparison calls: 82696100
Elapsed time: 0 min 9 sec


Command (h for help, Q to quit): S
Shuffled.

Command (h for help, Q to quit): q

Quicksorting..............4000000 function calls
190179315 Iterations     Comparison calls: 100817020
Elapsed time: 0 min 23 sec

Альт без крейзи колорс. Есть еще кое-что обо мне, примерно на полпути вниз эта страница .

пс. для сортировки не требуется дополнительная память со связанным списком.

Answer 2

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

• qsort сначала самый короткий подмассив.
• переключиться на вставку сортировки ниже 5-25 элементов
• сделать нормальный круговой выбор

Ваш qsort очень медленный, потому что он пытается разбить и qsort массивы длины 2 и 3.

Answer 3

Ранее обсуждалось на SO: " Почему быстрая сортировка лучше, чем mergesort? "

~

Answer 4

Одним из преимуществ быстрой сортировки для сравнительно небольших размеров массивов является просто артефакт аппаратной реализации.

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

В результате для сравнительно небольших наборов данных быстрая сортировка с большей вероятностью будет получать попадания в кэш и, следовательно, на большинстве аппаратных средств будет работать быстрее.

Mergesort все еще является довольно хорошим решением для больших наборов данных или других структур данных, таких как связанные списки, как подтверждают ваши эксперименты.

Answer 5

Худший случай сортировки слиянием - это средний случай быстрой сортировки, поэтому, если у вас нет хорошей реализации, сортировка слиянием будет быстрее в целом. Быстрое выполнение быстрой сортировки - это предотвращение случаев ниже среднего. Выберите лучшую опору (срединное-3 помогает), и вы увидите разницу.

Answer 6

На основании этой википедии статья ожидаются ваши результаты.

Answer 7

Я думаю, что до тех пор, пока данные помещаются в память, хорошая реализация сортировки слиянием работает лучше, чем хорошая реализация быстрой сортировки.

Одна из наиболее широко используемых реализаций qsort (), glibc qsort (), внутренне использует сортировку слиянием для большинства случаев, когда данные помещаются в память. Эта сортировка слиянием выделяет временное пространство памяти, используемое для слияния, что добавляет некоторую нагрузку на память, но в большинстве случаев она превосходит собственную реализацию внутренней быстрой сортировки с хорошим выбором и оптимизацией сводных данных. glibc использует быструю сортировку только тогда, когда данные и временная память для сортировки слиянием не могут поместиться в памяти.

Я измерил производительность этих двух реализаций на моей машине с 2,1 ГГц процессором и несколькими ГБ оперативной памяти. Входные данные генерируются с помощью псевдослучайного генератора, и каждый ключ представляет собой 32-разрядное целое число без знака, что означает немного больше циклов сравнения, чем целочисленное сравнение, благодаря интерфейсу функции сравнения.

Для сортировки слиянием:

2 MB, time_diff 165.156000 ms, 78.752518 ns per byte
4 MB, time_diff 344.298000 ms, 82.087040 ns per byte
8 MB, time_diff 730.926000 ms, 87.133169 ns per byte
16 MB, time_diff 1541.215000 ms, 91.863573 ns per byte
32 MB, time_diff 3088.924000 ms, 92.057109 ns per byte
64 MB, time_diff 6262.868000 ms, 93.324006 ns per byte
128 MB, time_diff 12887.018000 ms, 96.015766 ns per byte
256 MB, time_diff 26731.597000 ms, 99.582959 ns per byte

Для быстрой сортировки:

2 MB, time_diff 243.519000 ms, 116.118908 ns per byte
4 MB, time_diff 504.975000 ms, 120.395422 ns per byte
8 MB, time_diff 1075.276000 ms, 128.182888 ns per byte
16 MB, time_diff 2183.865000 ms, 130.168498 ns per byte
32 MB, time_diff 4343.993000 ms, 129.461080 ns per byte
64 MB, time_diff 8714.166000 ms, 129.851192 ns per byte
128 MB, time_diff 17881.344000 ms, 133.226395 ns per byte
256 MB, time_diff 36751.029000 ms, 136.908252 ns per byte

Вы можете видеть, что между этими двумя реализациями существуют четкие различия в производительности и почему в такой широко используемой реализации qsort сортировка слиянием предпочтительнее, чем быстрой сортировкой. Основная причина этого различия заключается в том, что быстрая сортировка имеет на 10-20% больше сравнений, чем сортировка слиянием, из-за неравномерного разделения на каждом шаге.

Answer 8

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

Выбор стержня как медиана первого, среднего и последнего элемент улучшена производительность быстро sort`s, но быстрая сортировка была еще определенно хуже, чем сортировка слияния на больших массивах (> 100000 элементов).

Я увидел большое улучшение, когда внедрил интросортировку, то есть быструю сортировку, которая возвращается к сортировке в куче, если глубина рекурсии превышает определенный порог. Моя реализация сортировки вступления был почти так же быстр, как моя реализация сортировки слиянием. Конечно, intro-sort больше не является чисто быстрой сортировкой , так как она использует сортировку кучи, чтобы вернуть сложность к n log (n), когда чистая быстрая сортировка обнаруживает плохие данные. Я могу опубликовать результаты, если вы заинтересованы.

Answer 9

Если вы реализуете сортировку кучи в качестве базового алгоритма сортировки в худшем случае быстрой сортировки, вы получите алгоритм тета (n log n).

Если вам не нужна стабильная сортировка и вы не сортируете связанный список, я думаю, это будет самый быстрый способ, которым вы сможете воспользоваться.

Сортировка слиянием

Answer 10

Это согласуется с анализом алгоритмов. Сортировка слиянием гарантируется O (nlogn) для любого ввода и для каждой среды выполнения. Быстрая сортировка - это лучший вариант O (nlogn) и средний случай O (nlogn), но худший случай O (n ^ 2), поэтому среднее выполнение будет между O (nlogn) и O (n ^ 2).

Быстрая сортировка - лучший алгоритм общего случая, потому что он имеет низкие издержки, поэтому он имеет хорошую скорость для значений n примерно до 10000 или около того и все еще хорошее время выполнения для произвольно астрономических значений n. Сортировка слиянием сопряжена с трудностями при записи фрейма стека, необходимого для каждого рекурсивного вызова. Таким образом, для низких значений n он имеет ужасно высокое значение c в RT = cnlogn и не является предпочтительным общим методом сортировки.

Редактировать: Программное обеспечение Monkey указало на противоречие: быстрая сортировка усредняет O (nlogn) для случайного ввода, но O (n ^ 2) в худшем случае. Так что на самом деле это в некоторой степени связано с энтропией ваших данных - или вы можете выбрать стержень случайным образом. Я все еще мог бы быть немного, хотя.