Обсуждение:PSRS-сортировка

Материал из Викиконспекты
Перейти к: навигация, поиск

Оптимизации

Бинарные вставки

Так как в среднем количество сравнений для [math]j[/math]-го элемента равно [math]j/2[/math], следовательно общее количество сравнений приблизительно [math]\frac {(1+2+3+...+N)}{2} \approx N^2/4[/math], но это очень много даже при малых [math]N[/math]. Суть этого заключается в том, что поиск позиции для вставки [math]j[/math]-го элемента осуществляется бинарным поиском, вследствие чего количество сравнений для [math]N[/math] элементов [math]N \cdot \log_{2} N[/math].Количество сравнений заметно уменьшилось, но для того, чтобы поставить [math]R_j[/math] элемент на [math]i[/math]-тое место, всё ещё необходимо переместить [math]j-i[/math] элементов.Что касается константы [math]C[/math], то [math]C \cdot N \cdot (N/4+log_{2} N) \approx N^2/4[/math], следовательно [math]C=1/4[/math].

Двухпутевые вставки

Суть этого метода в том, что вместо отсортированной части массива мы используем область вывода. Первый элемент помещается в середину области вывода, а место для последующих элементов освобождается потём сдвига элементов влево или вправо туда, куда выгоднее. Пример для набора элементов 5 7 3 4 6

     5
     5 7
   3 5 7
 3 4 5 7
 3 4 5 6 7 

Как мы видим в этом примере понадобилось сдвинуть всего 3 элемента. Что касается константы [math]C[/math], то [math]C \cdot N \cdot (N/8+log_{2} N) \approx N^2/8[/math], следовательно [math]C=1/8[/math].

Метод Шелла

Метод Шелла основан на том, что сортировка вставками более эффективна на маленьких или на частичной отсортированных входных данных. Устройство метода Шелла более понятно если рассматривать его на фиксированном наборе данных. Например мы имеем набор из 16 элементов [math]R_1...R_{16}[/math] разобьём их на пары [math](R_1,R_9),...,(R_8,R_{16})[/math]. Каждое разделение называется проходом. Отсортируем каждую из пар. Разобьем на группы по 4 элемента [math](R_1,R_5,R_9,R_{13}),...,(R_4,R_8,R_{12},R_{16})[/math]. Отсортируем каждую из пар.Разобьём на 2 группы [math](R_1,R_3,R_5,R_7,R_9,R_{11},R_{13},R_{15}),(R_2,R_4,R_6,R_8,R_{10},R_{12},R_{14},R_{16})[/math]. Отсортируем каждую из пар. При четвёртоми последнем проходе сортируются все 16 элементов. В итоге получится отсортированный массив. Последовательность смещений 1 2 4 8 может меняться в зависимости от неё меняется и асимптотика. Например предложенная Хиббардом последовательность [math]2^i-1 \le N, i \in N [/math] приводит к алгоритму с асимптотиткой [math] O(N^2) [/math].

Вставка в список

Сортировка с вычисление адреса