Главная страница Случайная лекция
Мы поможем в написании ваших работ!
Порталы:
БиологияВойнаГеографияИнформатикаИскусствоИсторияКультураЛингвистикаМатематикаМедицинаОхрана трудаПолитикаПравоПсихологияРелигияТехникаФизикаФилософияЭкономика
Мы поможем в написании ваших работ!
Сортировка Шелла
|
Читайте также: |
Begin
Фрагмент программы, реализующий сортировку вставкой.
К – текущая длина массива, b - переменная для обмена элементов.
for i:=2 to k do
b:=a[i]; {взятие неотсортированного элемента}
J:=1;
while (b>a[j])and(j<i) do j:=j+1; {поиск позиции вставки}
{цикл для сдвига элементов для освобождения позиции вставки}
for l:=i-1 downto j doa[l+1]:=a[l];
a[j]:=b; {вставка элемента на найденную позицию}
end;
Иллюстрация работы алгоритма. Пусть N=6 – длина массива, i – длина отсортированной части массива, которая постепенно увеличивается.
| (N=6) | (N=6) | ||||||||||||||
| Проход 1 |  11
| Проход 2 |  9
| ||||||||||||
| i=1 | i=2 | ||||||||||||||
| неотсортированный | неотсортированный | ||||||||||||||
| элемент | элемент | ||||||||||||||
| Рез-т | Рез-т |
| (N=6) | (N=6) | ||||||||||||||
| Проход 3 | Проход 4 | ||||||||||||||
| I=3 | 
| i=4 | 
| ||||||||||||
| неотсортированный | неотсортированный | ||||||||||||||
| элемент | элемент | ||||||||||||||
| Рез-т | Рез-т | ||||||||||||||
| Проход 5 | |||||||||||||||
| I=5 | 
| ||||||||||||||
| неотсортированный | |||||||||||||||
| элемент | |||||||||||||||
| Рез-т |
Принцип метода. Метод назван в честь его изобретателя (D.L.Shell). Он построен на основе метода вставки с минимизацией промежуточных шагов. Рассмотрим иллюстрацию на рис.
| № | ||||||
| Проход 1 | f | d | a | c | b | e |
| c | d | a | f | b | e | |
| c | b | a | f | d | e | |
| Рез-т | c | b | a | f | d | e |
| Проход 2 | c | b | a | f | d | e |
| a | b | c | f | d | e | |
| a | b | c | f | d | e | |
| a | b | c | f | d | e | |
| Рез-т | a | b | c | e | d | f |
| Проход 3 | a | b | c | e | d | f |
| a | b | c | e | d | f | |
| a | b | c | e | d | f | |
| a | b | c | e | d | f | |
| a | b | c | d | e | f | |
| Рез-т | a | b | c | d | e | f |
Сначала выполняется сортировка элементов, отстоящих друг от друга на 3 позиции. После этого сортируются элементы, отстоящие друг от друга на 2 позиции. Наконец выполняется сортировка соседних элементов. На первый взгляд непонятно, почему этот кажущийся столь сложным метод дает столь хорошие результаты. Непонятно даже, как от вообще работает. Но метод работает. Каждый промежуточный шаг задействует относительно небольшое количество элементов, которые к тому же могут находиться в правильном порядке. Поэтому метод Шелла эффективен и упорядоченность массива возрастает на каждом шаге.
Последовательность изменений приращений может меняться. Единственное требование – это равенство последнего приращения 1. Например, хорошо себя зарекомендовала последовательность 9,5,3,2,1, которая использовалась в примере. Наихудшим вариантом является последовательность степеней двойки (это строго математически доказано).
Время выполнения сортировки пропорциональной n1,2 при сортировке n элементов.
| <== предыдущая страница | | | следующая страница ==> |
| Сортировка вставкой | | | Описание матрицы |
Дата добавления: 2014-03-11; просмотров: 342; Нарушение авторских прав
Мы поможем в написании ваших работ!