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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Оптимизации)
(Оптимизации)
Строка 2: Строка 2:
 
== Оптимизации ==
 
== Оптимизации ==
 
=== Бинарные вставки ===
 
=== Бинарные вставки ===
Так как в среднем количество сравнений для <tex>j</tex>-го элемента равно <tex>j/2</tex>, следовательно общее количество сравнений приблизительно <tex>\frac {(1+2+3+...+N)}{2} \approx N^2/4</tex>, но это очень много даже при малых <tex>N</tex>. Суть этого заключается в том, что поиск позиции для вставки <tex>j</tex>-го элемента осуществляется бинарным поиском, вследствие чего количество сравнений для <tex>N</tex> элементов <tex>N \cdot \log_{2} N</tex>. Количество сравнений заметно уменьшилось, но для того, чтобы поставить <tex>R_j</tex> элемент на <tex>i</tex>-тое место, всё ещё необходимо переместить <tex>j-i</tex> элементов. Что касается константы <tex>C</tex>, то <tex>C \cdot N \cdot (N/4+log_{2} N) \approx N^2/4</tex>, следовательно <tex>C=1/4</tex>.     
+
Так как в среднем количество сравнений для <tex>j</tex>-го элемента равно <tex>j/2</tex>, следовательно общее количество сравнений приблизительно <tex>\frac {(1+2+3+...+N)}{2} \approx N^2/4</tex>, но это очень много даже при малых <tex>N</tex>. Суть этого заключается в том, что поиск позиции для вставки <tex>j</tex>-го элемента осуществляется бинарным поиском, вследствие чего количество сравнений для <tex>N</tex> элементов <tex>N \cdot \log_{2} N</tex>. Количество сравнений заметно уменьшилось, но для того, чтобы поставить <tex>R_j</tex> элемент на <tex>i</tex>-тое место, всё ещё необходимо переместить <tex>j-i</tex> элементов. В итоге время выполнения алгоритма уменьшилось в среднем в четыре раза : <tex>C \cdot N \cdot (N/4+log_{2} N) \approx N^2/4</tex>, следовательно <tex>C=1/4</tex>.     
 
=== Двухпутевые вставки ===
 
=== Двухпутевые вставки ===
 
Суть этого метода в том, что вместо отсортированной части массива мы используем область вывода. Первый элемент помещается в середину области вывода, а место для последующих элементов освобождается потём сдвига элементов влево или вправо туда, куда выгоднее.
 
Суть этого метода в том, что вместо отсортированной части массива мы используем область вывода. Первый элемент помещается в середину области вывода, а место для последующих элементов освобождается потём сдвига элементов влево или вправо туда, куда выгоднее.
Строка 11: Строка 11:
 
   3 4 5 7
 
   3 4 5 7
 
   3 4 5 6 7  
 
   3 4 5 6 7  
Как мы видим в этом примере понадобилось сдвинуть всего 3 элемента. Что касается константы <tex>C</tex>, то <tex>C \cdot N \cdot (N/8+log_{2} N) \approx N^2/8</tex>, следовательно <tex>C=1/8</tex>.   
+
Как мы видим в этом примере понадобилось сдвинуть всего 3 элемента. Время выполнения алгоритма сократилось в восемь раз : <tex>C \cdot N \cdot (N/8+log_{2} N) \approx N^2/8</tex>, следовательно <tex>C=1/8</tex>.   
 
=== Метод Шелла ===
 
=== Метод Шелла ===
 
Метод Шелла основан на том, что сортировка вставками более эффективна на маленьких или на частичной отсортированных входных данных. Устройство метода Шелла более понятно если рассматривать его на фиксированном наборе данных. Например мы имеем набор из 16 элементов <tex>R_1...R_{16}</tex> разобьём их на пары <tex>(R_1,R_9),...,(R_8,R_{16})</tex>. Каждое разделение называется проходом. Отсортируем каждую из пар. Разобьем на группы по 4 элемента <tex>(R_1,R_5,R_9,R_{13}),...,(R_4,R_8,R_{12},R_{16})</tex>. Отсортируем каждую из пар. Разобьём на 2 группы по восемь элементов <tex>(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})</tex>. Отсортируем каждую из пар. При четвёртоми последнем проходе сортируются все 16 элементов. В итоге получится отсортированный массив.
 
Метод Шелла основан на том, что сортировка вставками более эффективна на маленьких или на частичной отсортированных входных данных. Устройство метода Шелла более понятно если рассматривать его на фиксированном наборе данных. Например мы имеем набор из 16 элементов <tex>R_1...R_{16}</tex> разобьём их на пары <tex>(R_1,R_9),...,(R_8,R_{16})</tex>. Каждое разделение называется проходом. Отсортируем каждую из пар. Разобьем на группы по 4 элемента <tex>(R_1,R_5,R_9,R_{13}),...,(R_4,R_8,R_{12},R_{16})</tex>. Отсортируем каждую из пар. Разобьём на 2 группы по восемь элементов <tex>(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})</tex>. Отсортируем каждую из пар. При четвёртоми последнем проходе сортируются все 16 элементов. В итоге получится отсортированный массив.
Строка 19: Строка 19:
 
При этой сортировке мы используем односвязной список вместо упорядоченной части массива. Теперь на не потребуется времени на сдвиг, а понадобиться всего лишь изменить родстве6ые связи. Что касается константы <tex>C</tex>, то <tex>C \cdot N \cdot (N/4+2) \approx N^2/4</tex>, следовательно <tex>C=1/4</tex>.
 
При этой сортировке мы используем односвязной список вместо упорядоченной части массива. Теперь на не потребуется времени на сдвиг, а понадобиться всего лишь изменить родстве6ые связи. Что касается константы <tex>C</tex>, то <tex>C \cdot N \cdot (N/4+2) \approx N^2/4</tex>, следовательно <tex>C=1/4</tex>.
 
=== Сортировка с вычислением адреса ===
 
=== Сортировка с вычислением адреса ===
Сортировку с вычисление адревса выгодно использовать когда ключи распределены равномерно и не скапливаются хаотично в отдельных диапазонах значений. Вместо левой отсортированной части массива мы будем использовать <tex> M </tex> односвязных списков, в каждом из которых будут храниться значения из определённого диапазона. С каждым списком работаем как при простых выставках в список. Вероятность того что элемент попадёт в какой-либо список <tex>1/M</tex>, следовательно для каждого элемента происходит примерно <tex> \frac {N} {4 \cdot M} </tex> сравнений, следовательно общее количество сравнений <tex> \frac {N^2} {4 \cdot M} </tex>, а при <tex>M</tex> порядка <tex>N</tex> асимптотическая сложность уменьшается до <tex>O(N)</tex>. Что касается константы <tex>C</tex>, то она <tex> \frac {N} {4 \cdot M} </tex>. Рассмотрим на примере.
+
Сортировку с вычисление адревса выгодно использовать когда ключи распределены равномерно и не скапливаются хаотично в отдельных диапазонах значений. Вместо левой отсортированной части массива мы будем использовать <tex> M </tex> односвязных списков, в каждом из которых будут храниться значения из определённого диапазона. С каждым списком работаем как при простых выставках в список. Вероятность того что элемент попадёт в какой-либо список <tex>1/M</tex>, следовательно для каждого элемента происходит примерно <tex> \frac {N} {4 \cdot M} </tex> сравнений, следовательно общее количество сравнений <tex> \frac {N^2} {4 \cdot M} </tex>, а при <tex>M</tex> порядка <tex>N</tex> асимптотическая сложность уменьшается до <tex>O(N)</tex>. Рассмотрим на примере.
 
Входные данные : 867 345 984 245 123 743 550 490 300  
 
Входные данные : 867 345 984 245 123 743 550 490 300  
 
Будем использовать 4 списка с соответствующими диапазонами значений : 0 - 250, 251 - 500, 501 - 750, 751- 1000.
 
Будем использовать 4 списка с соответствующими диапазонами значений : 0 - 250, 251 - 500, 501 - 750, 751- 1000.

Версия 17:08, 3 июня 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 \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 \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], следовательно для каждого элемента происходит примерно [math] \frac {N} {4 \cdot M} [/math] сравнений, следовательно общее количество сравнений [math] \frac {N^2} {4 \cdot M} [/math], а при [math]M[/math] порядка [math]N[/math] асимптотическая сложность уменьшается до [math]O(N)[/math]. Рассмотрим на примере. Входные данные : 867 345 984 245 123 743 550 490 300 Будем использовать 4 списка с соответствующими диапазонами значений : 0 - 250, 251 - 500, 501 - 750, 751- 1000.

3 элемента 6 элементов 9 элементов
0 - 250 123 245 123 245
251 - 500 345 345 300 345 490
501 - 750 743 550 743
751 - 1000 867 984 867 984