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

Материал из Викиконспекты
Версия от 22:16, 18 мая 2014; AlexeyL (обсуждение | вклад) (Сортировка с вычисление адреса)
Перейти к: навигация, поиск

Оптимизации

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

Так как в среднем количество сравнений для [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^{3/2}) [/math].

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

При этой сортировке мы используем односвязной список вместо упорядоченной части массива. Теперь на не потребуется времени на сдвиг, а понадобиться всего лишь изменить родстве6ые связи. Что касается константы [math]C[/math], то [math]C \cdot N \cdot (N/4+2) \approx N^2/4[/math], следовательно [math]C=1/4[/math].

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

Сортировку с вычисление адревса выгодно использовать когда ключи распределены равномерно и не скапливаются хаотично в отдельных диапазонах значений. Вместо левой отсортированной части массива мы будем использовать [math] M [/math] односвязных списков, в каждом из которых будут храниться значения из определённого диапазона. С каждым списком работаем как при простых выставках в список. Вероятность того что элемент попадёт в какой-либо список [math]1/M[/math], следовательно для каждого элемента происходит примерно <tex> N