Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Алгоритм Шелла



Подобен пузырьку, в котором сравнение и обмены происходят на некоторой дистанции в зависимости от значения переменной A, называемой шагом сортировки. Метод Шелла относится к классу вставок, в котором происходит обмен записи.

Устойчивой называется сортировка, в которой записи с одинаковым значением ключа сохраняют свою относительную исходную последовательность и после сортировки.

7 5 13 6 7 10 4 7 2 (R1;R6);(R2;R7);(R3;R8)…(Ri;Ri+L)

 
 


7 4 7 2 7 10 5 13 6 (R1;R4;R7);(R2;R5;R8);(R3;R6;R9)

2 4 6 5 7 7 7 13 10

послед. Шаг h=1

В алгоритме Шелла неявно образуются группы из элементов, которые отстоят друг от друга на h позиций, каждая такая группа сортируется простой вставкой, после чего значение шага надо изменить.

Теорема: K-упорядоченная последовательность после h сортировки будет одновременно kh упорядочена

Самая простая последовательность шагов образуется

h={ ½; N/2 * ½; N/8; N/16;....; 1 }, где i номер итерации

hi=(Hi-1)/2

h={16,8,4,2,1}

Что приводит к тому, что элементы в четных и нечетных позициях не взаимодействуют друг с другом, вплоть до последней итерации на которую придется максимальное количество обменов – наихудший случай выбора шагов. А наилучший – когда происходит наибольшее перемешивание групп от раза к разу.

Это достигается, если шаги взаимно простые h={13,11,7,5,3,1}. Вообще, последовательность может быть любая, главное чтоб h=1.

Например у Кнута: hi=3h-1+1

При этом I максимально i – max: Himax+2 > N

h>N

Трудоемкость Шелла О(N1,667)

Причем это достигается всего лишь при двух шагах сортировки относительно простых вставок.





Дата публикования: 2015-01-10; Прочитано: 335 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.008 с)...