Студопедия

Главная страница Случайная лекция


Мы поможем в написании ваших работ!

Порталы:

БиологияВойнаГеографияИнформатикаИскусствоИсторияКультураЛингвистикаМатематикаМедицинаОхрана трудаПолитикаПравоПсихологияРелигияТехникаФизикаФилософияЭкономика



Мы поможем в написании ваших работ!




Сортировка Шелла

Читайте также:
  1. Быстрая сортировка
  2. Дефектация и сортировка деталей
  3. Маркировка и сортировка яиц.
  4. Медицинская сортировка и этапное лечение.
  5. Медицинская сортировка на этапах эвакуации
  6. Просмотр информации. Сортировка и фильтрация
  7. Сортировка
  8. Сортировка вставкой
  9. Сортировка зерна.

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; Нарушение авторских прав




Мы поможем в написании ваших работ!
lektsiopedia.org - Лекциопедия - 2013 год. | Страница сгенерирована за: 0.003 сек.