Quicksort против heapsort

И quicksort, и heapsort выполняют сортировку на месте. Что лучше? Какие приложения и случаи предпочтительнее?

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

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

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

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

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

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

Гибриды 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 выбрано в качестве точной медианы, рекурсии нет вообще).

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

Так что

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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. Куча может быть легко реализована на месте в исходном массиве, поэтому она не требует дополнительной памяти и является итеративной, поэтому не нужно беспокоиться о переполнении стека при рекурсии. Огромный недостаток кучи сортировки является то , что она не является стабильной рода, а это значит , что это правильно, если вам нужно.