Обсуждение:PSRS-сортировка — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Метод Шелла)
(Вставка в список)
Строка 17: Строка 17:
  
 
===Вставка в список ===
 
===Вставка в список ===
 +
При этой сортировке мы используем односвязной список вместо упорядоченной части массива. Теперь на не потребуется времени на сдвиг, а понадобиться всего лишь изменить родстве6ые связи.
 +
 
=== Сортировка с вычисление адреса ===
 
=== Сортировка с вычисление адреса ===

Версия 20:15, 18 мая 2014

Оптимизации

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

Так как в среднем количество сравнений для [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].

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

При этой сортировке мы используем односвязной список вместо упорядоченной части массива. Теперь на не потребуется времени на сдвиг, а понадобиться всего лишь изменить родстве6ые связи.

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