Сортировка кучи имеет сложность наихудшего случая O(nlogn)
, в то время как Quicksort имеет O(n^2)
. Но эмпирические свидетельства говорят, что быстрая сортировка лучше. Это почему?
Превосходство быстрой сортировки над сортировкой в куче
Ответы (6)
Одним из основных факторов является то, что быстрая сортировка имеет лучшую локальность ссылки - следующая вещь, к которой нужно получить доступ, обычно находится в памяти близко к тому, на что вы только что посмотрели. В отличие от этого, heapsort прыгает значительно больше. Поскольку вещи, которые находятся близко друг к другу, скорее всего, будут кэшироваться вместе, быстрая сортировка, как правило, выполняется быстрее.
Однако производительность быстрой сортировки в худшем случае значительно хуже, чем у heapsort. Поскольку для некоторых критически важных приложений требуются гарантии быстродействия, heapsort - правильный путь для таких случаев.
Heapsort гарантирован O (N log N), что намного лучше, чем наихудший случай в Quicksort. Heapsort не требуется больше памяти для другого массива для размещения упорядоченных данных, как это необходимо для Mergesort. Так почему же коммерческие приложения используют Quicksort? Что такого особенного в Quicksort по сравнению с другими реализациями?
Я сам протестировал алгоритмы и убедился, что в Quicksort действительно есть что-то особенное. Он работает быстро, намного быстрее, чем алгоритмы кучи и слияния.
Секрет быстрой сортировки: она почти не меняет ненужные элементы. Своп требует времени.
С помощью 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);
}
Вот пара объяснений:
http://www.cs.auckland.ac.nz/software/AlgAnim/qsort3.html
http://users.aims.ac.za/~mackay/sorting/sorting.html
По сути, даже если наихудший случай быстрой сортировки - O (n ^ 2), в среднем он будет работать лучше. :-)
Обозначение большого O означает, что время, необходимое для сортировки n элементов, ограничено выше функцией c*n*log(n)
, где c
- некоторый неопределенный постоянный коэффициент. Нет причин, по которым константа c
должна быть одинаковой для quicksort
и heapsort
. Итак, настоящий вопрос: почему вы ожидаете, что они будут одинаково быстрыми?
На практике Quicksort
всегда был несколько быстрее, чем heapsort
, но в последнее время разница стала больше, поскольку, как упоминалось ранее, локальность доступа к памяти стала настолько важной для скорости выполнения.
Сложность в среднем случае и тот факт, что вы можете предпринять простые шаги, чтобы минимизировать риск наихудшей сложности в Quicksort (например, выберите точку поворота как медианное значение трех элементов, а не одну выбранную позицию).
Как уже было сказано, быстрая сортировка имеет гораздо лучшую локальность ссылок по сравнению с heapsort, но в худшем случае сложность O (n ^ 2).
std :: sort реализуется с использованием сортировки самоанализом: большую часть времени он запускает быструю сортировку, но в случае, если он обнаруживает, что среда выполнения будет плохой из-за неправильного выбора точки поворота, она переключается на сортировку по куче. В этом случае вы получаете гарантированную сложность O (nlog (n)) вместе со скоростью быстрой сортировки, которая выбирается почти каждый раз.