Quicksort против heapsort

Ответы:

61

В этой статье есть некоторый анализ.

Также из Википедии:

Самый прямой конкурент быстрой сортировки - это heapsort. Heapsort обычно несколько медленнее, чем quicksort, но в худшем случае время работы всегда Θ (nlogn). Быстрая сортировка обычно быстрее, хотя остается шанс на худший случай производительности, за исключением варианта внутренней сортировки, который переключается на heapsort при обнаружении плохого случая. Если заранее известно, что потребуется heapsort, использовать его напрямую будет быстрее, чем ждать, пока интросорт переключится на него.

ДВК
источник
12
Возможно, важно отметить, что в типичных реализациях ни быстрая сортировка, ни куча не являются стабильными сортировками.
MjrKusanagi
@DVK, согласно вашей ссылке cs.auckland.ac.nz/~jmor159/PLDS210/qsort3.html , сортировка кучи занимает 2842 сравнения для n = 100, но для n = 500 требуется 53113 сравнений. Это означает, что соотношение между n = 500 и n = 100 равно 18 раз, и это НЕ соответствует алгоритму сортировки кучи со сложностью O (N logN). Думаю, вполне вероятно, что в их реализации сортировки кучи есть какие-то ошибки внутри.
DU Jiaen
@DUJiaen - помните, что O () касается асимптотического поведения при больших N и имеет возможный множитель
DVK
Это НЕ связано с множителем. Если алгоритм имеет сложность O (N log N), он должен следовать тенденции Time (N) = C1 * N * log (N). И если вы возьмете Time (500) / Time (100), очевидно, что C1 исчезнет, ​​и результат должен быть близок к (500 log500) / (100 log100) = 6.7 Но из вашей ссылки это 18, что является слишком много зашкаливает.
DU Jiaen
2
Ссылка мертва
PlsWork 04
127

Heapsort гарантирован O (N log N), что намного лучше, чем худший случай в Quicksort. Heapsort не требуется больше памяти для другого массива для размещения упорядоченных данных, как это необходимо для Mergesort. Так почему же коммерческие приложения используют Quicksort? Что такого особенного в Quicksort по сравнению с другими реализациями?

Я сам протестировал алгоритмы и убедился, что Quicksort действительно имеет что-то особенное. Он работает быстро, намного быстрее, чем алгоритмы Heap и Merge.

Секрет быстрой сортировки в том, что она почти не меняет ненужные элементы. Своп требует времени.

С помощью Heapsort, даже если все ваши данные уже упорядочены, вы собираетесь поменять местами 100% элементов, чтобы упорядочить массив.

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

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

То, что лучше в Quicksort, не худший случай, а лучший случай! В лучшем случае вы делаете такое же количество сравнений, хорошо, но вы почти ничего не меняете местами. В среднем вы меняете местами часть элементов, но не все элементы, как в Heapsort и Mergesort. Это то, что дает Quicksort лучшее время. Меньше подкачки, больше скорости.

Приведенная ниже реализация на C # на моем компьютере, работающая в режиме выпуска, превосходит Array.Sort на 3 секунды со средней точкой поворота и на 2 секунды с улучшенной точкой поворота (да, есть накладные расходы для получения хорошей точки поворота).

static void Main(string[] args)
{
    int[] arrToSort = new int[100000000];
    var r = new Random();
    for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);

    Console.WriteLine("Press q to quick sort, s to Array.Sort");
    while (true)
    {
        var k = Console.ReadKey(true);
        if (k.KeyChar == 'q')
        {
            // quick sort
            Console.WriteLine("Beg quick sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            QuickSort(arrToSort, 0, arrToSort.Length - 1);
            Console.WriteLine("End quick sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);
        }
        else if (k.KeyChar == 's')
        {
            Console.WriteLine("Beg Array.Sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            Array.Sort(arrToSort);
            Console.WriteLine("End Array.Sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);
        }
    }
}

static public void QuickSort(int[] arr, int left, int right)
{
    int begin = left
        , end = right
        , pivot
        // get middle element pivot
        //= arr[(left + right) / 2]
        ;

    //improved pivot
    int middle = (left + right) / 2;
    int
        LM = arr[left].CompareTo(arr[middle])
        , MR = arr[middle].CompareTo(arr[right])
        , LR = arr[left].CompareTo(arr[right])
        ;
    if (-1 * LM == LR)
        pivot = arr[left];
    else
        if (MR == -1 * LR)
            pivot = arr[right];
        else
            pivot = arr[middle];
    do
    {
        while (arr[left] < pivot) left++;
        while (arr[right] > pivot) right--;

        if(left <= right)
        {
            int temp = arr[right];
            arr[right] = arr[left];
            arr[left] = temp;

            left++;
            right--;
        }
    } while (left <= right);

    if (left < end) QuickSort(arr, left, end);
    if (begin < right) QuickSort(arr, begin, right);
}
Маркиньо Пели
источник
10
+1 за соображения по нет. операций подкачки, чтения / записи, необходимых для различных алгоритмов сортировки
ycy
2
Для любой детерминированной стратегии выбора поворота с постоянным временем вы можете найти массив, который дает наихудший случай O (n ^ 2). Недостаточно исключить минимум. Вы должны надежно выбирать точки опоры, которые находятся в пределах определенной грудной полосы.
Antimony
1
Мне любопытно, является ли это точным кодом, который вы использовали для моделирования между вашей ручной быстрой сортировкой и встроенным в C # Array.sort? Я тестировал этот код, и во всех моих тестах быстрая сортировка вручную была в лучшем случае такой же, как Array.sort. Одна вещь, которую я контролировал в своем тестировании, - это создание двух идентичных копий случайного массива. В конце концов, данная рандомизация потенциально может быть более благоприятной (склоняясь к лучшему случаю), чем другая рандомизация. Поэтому я прогнал одинаковые наборы через каждый из них. Array.sort каждый раз привязывают или бьют (релизная сборка кстати).
Крис
1
Сортировка слиянием не обязательно должна копировать 100% элементов, если только это не очень наивная реализация из учебника. Это просто реализовать, так что вам нужно скопировать только 50% из них (левая часть двух объединенных массивов). Также тривиально откладывать копирование до тех пор, пока вам действительно не придется «поменять местами» два элемента, поэтому с уже отсортированными данными у вас не будет никаких накладных расходов на память. Так что даже 50% на самом деле наихудший случай, и вы можете получить что-то между этим и 0%.
ddekany
1
@MarquinhoPeli Я хотел сказать, что вам нужно только на 50% больше доступной памяти по сравнению с размером отсортированного списка, а не на 100%, что, по-видимому, является распространенным заблуждением. Итак, я говорил о пиковом использовании памяти. Я не могу дать ссылку, но это легко увидеть, если вы попытаетесь объединить две уже отсортированные половины массива на месте (только левая половина имеет проблему, когда вы перезаписываете элементы, которые вы еще не использовали). Другой вопрос, сколько копий памяти вам нужно сделать в течение всего процесса сортировки, но очевидно, что худший случай не может быть ниже 100% для любого алгоритма сортировки.
ddekany
15

В большинстве ситуаций сравнение «быстрое» против «немного более быстрого» не имеет значения ... вы просто никогда не хотите, чтобы он иногда становился очень медленным. Хотя вы можете настроить QuickSort, чтобы избежать медленных ситуаций, вы теряете элегантность базовой QuickSort. Итак, для большинства вещей я предпочитаю HeapSort ... вы можете реализовать его во всей его простой элегантности и никогда не получить медленную сортировку.

В ситуациях, когда в большинстве случаев вам ДЕЙСТВИТЕЛЬНО нужна максимальная скорость, QuickSort может быть предпочтительнее HeapSort, но ни то, ни другое не может быть правильным ответом. Для ситуаций, критических по скорости, стоит внимательно изучить детали ситуации. Например, в некоторых моих кодах, критичных к скорости, очень часто данные уже отсортированы или почти отсортированы (это индексирование нескольких связанных полей, которые часто либо перемещаются вверх и вниз вместе, либо перемещаются вверх и вниз друг напротив друга, поэтому, как только вы отсортируете по одному, остальные будут либо отсортированы, либо отсортированы обратным образом, либо закрыты ... любой из которых может убить QuickSort). В этом случае я не реализовал ни ... вместо этого я реализовал SmoothSort Дейкстры ... вариант HeapSort, который равен O (N), когда он уже отсортирован или почти отсортирован ... это не так элегантно, не слишком легко понять, но быстро ... читатьhttp://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF, если вы хотите написать что-то более сложное.

Брайан Кеннеди
источник
6

Гибриды Quicksort-Heapsort на месте тоже действительно интересны, поскольку большинству из них требуется только n * log n сравнений в худшем случае (они оптимальны по отношению к первому члену асимптотики, поэтому они избегают сценариев наихудшего случая. of Quicksort), O (log n) extra-space, и они сохраняют как минимум «половину» хорошего поведения Quicksort в отношении уже упорядоченного набора данных. Чрезвычайно интересный алгоритм представлен Дикертом и Вайссом в http://arxiv.org/pdf/1209.4214v1.pdf :

  • Выберите опорную точку p в качестве медианы случайной выборки элементов sqrt (n) (это можно сделать максимум за 24 сравнения sqrt (n) с помощью алгоритма Tarjan & co, или за 5 сравнений sqrt (n) с помощью гораздо более запутанного паука -заводской алгоритм Шёнхаге);
  • Разделите массив на две части, как в первом шаге быстрой сортировки;
  • Заполните самую маленькую часть и используйте O (log n) дополнительных битов для кодирования кучи, в которой каждый левый дочерний элемент имеет значение больше, чем его брат;
  • Рекурсивно извлечь корень кучи, просеять лакуну, оставленную корнем, пока не достигнет листа кучи, затем заполнить лакуну соответствующим элементом, взятым из другой части массива;
  • Повторяется по оставшейся неупорядоченной части массива (если p выбрано в качестве точной медианы, рекурсии нет вообще).
Джек Д'Аурицио
источник
2

Комп. между quick sortи, merge sortпоскольку оба являются типом сортировки по месту, существует разница между временем выполнения случая wrost и временем выполнения случая wrost для быстрой сортировки O(n^2)и для сортировки кучи, O(n*log(n))и для среднего объема данных быстрая сортировка будет более полезной. Поскольку это рандомизированный алгоритм, вероятность получения правильного ответа. за меньшее время будет зависеть от выбранного вами положения поворотного элемента.

Так что

Хорошее решение : размеры L и G меньше 3 с / 4 каждый.

Плохой ответ: один из L и G имеет размер больше 3s / 4

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

Вики Гарг
источник
Хотя сортировка слиянием может быть реализована с сортировкой на месте, реализация является сложной. AFAIK, большинство реализаций сортировки слиянием не на месте, но они стабильны.
MjrKusanagi
2

У Heapsort есть преимущество в худшем случае O (n * log (n)), поэтому в случаях, когда быстрая сортировка, вероятно, будет работать плохо (в основном, сортированные наборы данных), heapsort является более предпочтительным.

Zellio
источник
4
Быстрая сортировка плохо работает с в основном отсортированным набором данных только в том случае, если выбран плохой метод выбора точки поворота. А именно, плохой метод выбора точки поворота - всегда выбирать первый или последний элемент в качестве точки поворота. Если каждый раз выбирается случайная точка поворота и используется хороший метод обработки повторяющихся элементов, вероятность быстрой сортировки в худшем случае очень мала.
Джастин Пил,
1
@Justin - Это правда, я говорил о наивной реализации.
zellio
1
@Justin: Верно, но шанс серьезного спада всегда есть, пусть даже небольшой. Для некоторых приложений мне может потребоваться обеспечить поведение O (n log n), даже если оно медленнее.
Дэвид Торнли
2

Что ж, если вы перейдете на уровень архитектуры ... мы используем структуру данных очереди в кеш-памяти. Поэтому все, что когда-либо доступно в очереди, будет отсортировано. Как и в быстрой сортировке, у нас нет проблем с разделением массива на любую длину ... но в куче sort (с использованием массива) может случиться так, что родительский элемент может отсутствовать в подмассиве, доступном в кеше, и затем он должен будет перенести его в кеш-память ... что отнимает много времени. Лучше всего быстрая сортировка !!

Манав Джайн
источник
1

Heapsort создает кучу, а затем многократно извлекает максимальный элемент. Наихудший случай - O (n log n).

Но если бы вы увидели наихудший случай быстрой сортировки , а именно O (n2), вы бы поняли, что быстрая сортировка была бы не очень хорошим выбором для больших данных.

Таким образом, сортировка становится интересной вещью; Я считаю, что причина, по которой сегодня существует так много алгоритмов сортировки, заключается в том, что все они «лучшие» в своих лучших местах. Например, пузырьковая сортировка может выполнять быструю сортировку, если данные отсортированы. Или, если мы знаем что-то об элементах, которые нужно отсортировать, возможно, мы сможем добиться большего.

Это может не отвечать на ваш вопрос напрямую, подумал, что добавлю свои два цента.

KMån
источник
1
Никогда не используйте пузырьковую сортировку. Если вы разумно думаете, что ваши данные будут отсортированы, вы можете использовать сортировку вставкой или даже проверить данные, чтобы увидеть, отсортированы ли они. Не используйте пузырьковую сортировку.
vy32
если у вас очень большой набор СЛУЧАЙНЫХ данных, лучше всего использовать быструю сортировку. Если заказан частично, то нет, но если вы начнете работать с огромными наборами данных, вы должны знать о них хотя бы столько же.
Kobor42 03
1

Сортировка кучи - это беспроигрышный вариант при работе с очень большими входными данными. Асимптотический анализ показывает порядок роста Heapsort в худшем случае Big-O(n logn), который лучше, чем Quicksort Big-O(n^2)в худшем случае. Однако Heapsort на практике на большинстве машин несколько медленнее, чем хорошо реализованная быстрая сортировка. Heapsort также не является стабильным алгоритмом сортировки.

Причина, по которой heapsort на практике работает медленнее, чем quicksort, связана с лучшей локальностью ссылок (« https://en.wikipedia.org/wiki/Locality_of_reference ») в быстрой сортировке, где элементы данных находятся в относительно близких местах хранения. Системы, которые демонстрируют сильную локальность ссылок, являются отличными кандидатами для оптимизации производительности. Сортировка кучи, однако, имеет дело с большими скачками. Это делает быструю сортировку более подходящей для небольших входных данных.

Бенн
источник
2
Быстрая сортировка тоже нестабильна.
Antimony
1

Для меня есть очень фундаментальное различие между heapsort и quicksort: последняя использует рекурсию. В рекурсивных алгоритмах куча растет с количеством рекурсий. Это не имеет значения, если n мало, но сейчас я сортирую две матрицы с n = 10 ^ 9 !!. Программа занимает почти 10 ГБ оперативной памяти, и любая дополнительная память заставит мой компьютер начать переключение на виртуальную дисковую память. Мой диск - это RAM-диск, но все же переключение на него имеет огромное значение в скорости . Таким образом, в статистическом пакете, закодированном на C ++, который включает в себя настраиваемые матрицы измерений, размер которых неизвестен программисту заранее, и непараметрический статистический вид сортировки, я предпочитаю динамическую сортировку, чтобы избежать задержек при использовании с очень большими матрицами данных.

Csevcik
источник
2
В среднем вам нужно всего O (logn) памяти. Накладные расходы на рекурсию тривиальны, если предположить, что вам не повезло с поворотами, и в этом случае у вас есть более серьезные проблемы, о которых нужно беспокоиться.
Antimony
0

Проще говоря >> HeapSort гарантировал ~ наихудшее время работы "O (n log n)" в отличие от ~ среднего ~ времени работы QuickSort "O (n log n)". QuickSort обычно используется на практике, потому что обычно он быстрее, но HeapSort используется для внешней сортировки, когда вам нужно отсортировать огромные файлы, которые не помещаются в памяти вашего компьютера.

Натрий Юнайтед
источник
-1

Чтобы ответить на исходный вопрос и ответить на некоторые другие комментарии здесь:

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

TL; DR: Quick - лучшая сортировка общего назначения (достаточно быстрая, стабильная и в основном на месте). Лично я предпочитаю сортировку кучи, если мне не нужна стабильная сортировка.

Выделение - N ^ 2 - Это действительно хорошо только для менее чем 20 элементов или около того, тогда оно превосходит по производительности. Если ваши данные уже не отсортированы или почти не отсортированы. N ^ 2 становится очень медленно, очень быстро.

Быстро, по моему опыту, это не на самом деле , что быстро все время. Бонусы за использование быстрой сортировки в качестве общей сортировки заключаются в том, что она достаточно быстрая и стабильная. Это также локальный алгоритм, но, поскольку он обычно реализуется рекурсивно, он занимает дополнительное место в стеке. Он также находится где-то между O (n log n) и O (n ^ 2). Время для некоторых сортов, кажется, подтверждает это, особенно когда значения попадают в узкий диапазон. Это намного быстрее, чем сортировка по выбору для 10 000 000 элементов, но медленнее, чем слияние или кучу.

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

Сортировка кучи - это max O (n log n), но во многих случаях быстрее, в зависимости от того, насколько далеко вам нужно переместить свои значения вверх по глубокой куче log n. Куча может быть легко реализована на месте в исходном массиве, поэтому она не требует дополнительной памяти и является итеративной, поэтому не нужно беспокоиться о переполнении стека при рекурсии. Огромный недостаток кучи сортировки является то , что она не является стабильной рода, а это значит , что это правильно, если вам нужно.

Тимоти Реннер
источник
Быстрая сортировка не является стабильной. Кроме того, вопросы такого рода побуждают к ответам, основанным на мнении, и могут привести к войнам и спорам редакторов. Вопросы, требующие ответов, основанных на мнении, явно не одобряются руководящими принципами SO. Автоответчики должны избегать соблазна ответить им, даже если у них есть значительный опыт и мудрость в данной сфере. Либо отметьте их для закрытия, либо дождитесь, пока кто-нибудь с достаточной репутацией отметит и закроет их. Этот комментарий не является отражением ваших знаний или обоснованности вашего ответа.
MikeC