Я читал, что на практике быстрая сортировка намного быстрее, чем сортировка слиянием, и причиной этого является скрытая константа.
Итак, решение для рандомизированной сложности быстрой сортировки: 2nlnn=1,39nlogn, что означает, что константа быстрой сортировки равна 1,39.
Но как насчет сортировки слиянием? Что такое константа в сортировке слиянием?
Посмотрим, сможем ли мы это решить!
В сортировке слиянием на каждом уровне рекурсии мы делаем следующее:
Итак, сколько сравнений выполняется на каждом шаге? Ну, шаг деления не делает никаких сравнений; он просто делит массив пополам. Шаг 2 (напрямую) не делает никаких сравнений; все сравнения выполняются рекурсивными вызовами. На шаге 3 у нас есть два массива размером n/2, и нам нужно их объединить. Для этого требуется не более n сравнений, поскольку каждый шаг алгоритма слияния выполняет сравнение, а затем потребляет некоторый элемент массива, поэтому мы не можем выполнить больше n сравнений.
Объединив это вместе, мы получим следующее повторение:
C(1) = 0
C(n) = 2C(n / 2) + n
(Как упоминалось в комментариях, линейный член точнее (n - 1), хотя это не меняет общего вывода. Мы будем использовать приведенное выше повторение в качестве верхней границы.)
Чтобы упростить это, давайте определим n = 2k и перепишем это повторение через k:
C'(0) = 0
C'(k) = 2C'(k - 1) + 2^k
Первые несколько членов здесь 0, 2, 8, 24, ... . Это выглядит примерно как k 2k, и мы можем доказать это по индукции. В качестве нашего базового случая, когда k = 0, первый член равен 0, и значение k 2k также равно 0. Для индуктивного шага предположим, что утверждение верно для некоторого k, и рассмотрим k + 1. Тогда значение равно 2(k 2k) + 2k + 1 = k 2k + 1 + 2k + 1 = (k + 1)2k + 1, поэтому утверждение верно для k + 1, что завершает индукцию. Таким образом, значение C'(k) равно k 2k. Поскольку n = 2k, это означает, что, предполагая, что n является полной степенью двойки, мы имеем, что количество сделанных сравнений равно
C(n) = n lg n
Впечатляет, но это лучше, чем быстрая сортировка! Так почему же быстрая сортировка работает быстрее, чем сортировка слиянием? Это связано с другими факторами, которые не имеют ничего общего с количеством сделанных сравнений. Прежде всего, поскольку быстрая сортировка работает на месте, а сортировка слиянием работает не на своем месте, локальность ссылок при сортировке слиянием не так хороша, как при быстрой сортировке. Это настолько важный фактор, что на практике быстрая сортировка оказывается намного лучше, чем сортировка слиянием, поскольку стоимость промаха кэша довольно высока. Кроме того, время, необходимое для сортировки массива, учитывает не только количество сравнений. Другие факторы, такие как количество перемещений каждого элемента массива, также могут иметь значение. Например, при сортировке слиянием нам нужно выделить место для буферизованных элементов, переместить элементы так, чтобы их можно было объединить, а затем снова объединить в массив. Эти ходы не учитываются в нашем анализе, но они определенно складываются. Сравните это с этапом секционирования быстрой сортировки, при котором каждый элемент массива перемещается ровно один раз и остается в пределах исходного массива. Эти дополнительные факторы, а не количество выполненных сравнений, определяют время выполнения алгоритма.
Этот анализ немного менее точен, чем оптимальный, но Википедия подтверждает, что анализ примерно n lg n и что это действительно меньше сравнений, чем в среднем случае быстрой сортировки.
Надеюсь это поможет!
В худшем случае и при прямой реализации количество сравнений для сортировки элементов n равно
где lg n указывает логарифм по основанию 2 п.
Этот результат можно найти в соответствующей статье Википедии или последних выпусках The Art of Computer Programming Дональда Кнута, и я только что записал доказательство для этот ответ.
Объединение двух отсортированных массивов (или списков) размером k соответственно. m принимает не более k+m-1 сравнений, в лучшем случае min{k,m}. (После каждого сравнения мы можем записать одно значение в цель, когда одно из двух исчерпано, больше никаких сравнений не требуется.)
Пусть C(n) будет наихудшим числом сравнений для сортировки слиянием массива (списка) из n элементов.
Затем у нас есть C(1) = 0, C(2) = 1, довольно очевидно. Далее имеем повторение
C(n) = C(floor(n/2)) + C(ceiling(n/2)) + (n-1)
Легкая индукция показывает
C(n) <= n*log_2 n
С другой стороны, легко видеть, что мы можем подойти к границе сколь угодно близко (для каждого ε > 0 мы можем построить случаи, требующие более (1-ε)*n*log_2 n сравнений), поэтому константа для сортировки слиянием равна 1.
Сортировка слиянием выполняется O(n log n) и на каждом шаге в «худшем» случае (по количеству сравнений) выполняет сравнение.
С другой стороны, быстрая сортировка в худшем случае составляет O (n ^ 2).
Программа C++ для подсчета количества сравнений при сортировке слиянием. Сначала программа отсортирует заданный массив, затем покажет количество сравнений.
#include<iostream>
using namespace std;
int count=0; /* to count the number of comparisions */
int merge( int arr [ ], int l, int m, int r)
{
int i=l; /* left subarray*/
int j=m+1; /* right subarray*/
int k=l; /* temporary array*/
int temp[r+1];
while( i<=m && j<=r)
{
if ( arr[i]<= arr[j])
{
temp[k]=arr[i];
i++;
}
else
{
temp[k]=arr[j];
j++;
}
k++;
count++;
}
while( i<=m)
{
temp[k]=arr[i];
i++;
k++;
}
while( j<=r)
{
temp[k]=arr[j];
j++;
k++;
}
for( int p=l; p<=r; p++)
{
arr[p]=temp[p];
}
return count;
}
int mergesort( int arr[ ], int l, int r)
{
int comparisons;
if(l<r)
{
int m= ( l+r)/2;
mergesort(arr,l,m);
mergesort(arr,m+1,r);
comparisions = merge(arr,l,m,r);
}
return comparisons;
}
int main ()
{
int size;
cout<<" Enter the size of an array "<< endl;
cin>>size;
int myarr[size];
cout<<" Enter the elements of array "<<endl;
for ( int i=0; i< size; i++)
{
cin>>myarr[i];
}
cout<<" Elements of array before sorting are "<<endl;
for ( int i=0; i< size; i++)
{
cout<<myarr[i]<<" " ;
}
cout<<endl;
int c=mergesort(myarr, 0, size-1);
cout<<" Elements of array after sorting are "<<endl;
for ( int i=0; i< size; i++)
{
cout<<myarr[i]<<" " ;
}
cout<<endl;
cout<<" Number of comaprisions while sorting the given array"<< c <<endl;
return 0;
}
Я предполагаю, что читатель знает сортировку слиянием. Сравнение происходит только при объединении двух отсортированных массивов. Для простоты примем n как степень 2. Чтобы объединить два массива размера (n/2) в худшем случае, нам нужно (n - 1) сравнений. Здесь появляется -1, так как последний элемент, оставшийся при слиянии, не требует никакого сравнения. Первое найденное число общего сравнения, приняв его за n на некоторое время, мы можем исправить его на (-1) часть. Количество уровней для слияния составляет log2 (n) (представьте себе древовидную структуру). В каждом слое будет n сравнений (нужно вычесть какое-то число из-за -1 части), поэтому общее сравнение равно nlog2(n) - (еще не найдено). Еще не найденная часть не дает константы nlog2(n), на самом деле это (1 + 2 + 4 + 8 + ... + (n/2) = n - 1). Число всех сравнений при сортировке слиянием = n*log2(n) - (n - 1). Итак, ваша константа равна 1.
