![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Метод Шелла
Алгоритм Шелла, названный по имени его создателя Дональда Л. Шелла (Donald L. Shell), намного эффективнее, чем метод пузырьков. Здесь сначала сравниваются отдаленные, а затем – близкорасположенные элементы данных. Исходный набор данных на каждом просмотре разбивается на части. Части образуются из записей, отстоящих друг от друга на J позиций. Производится сортировка записей внутри этих частей обычными методами (обмен, вставка и др.). После каждого просмотра J сокращается. При этом число частей уменьшается, а их длина увеличивается. Сортировка заканчивается просмотром с J=1. В методе Шелла первоначально J устанавливается равным INT(N/2), а затем сокращается вдвое. Переменная J содержит интервал, разделяющий сравниваемые элементы данных. Сначала J равен половине количества элементов. В процессе сортировки J уменьшается на каждом шаге в два раза, пока не начнет выполняться сравнение соседних элементов, как в методе пузырька.
Пример. Исходная последовательность К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8) K(9) 12 5 4 3 1 9 8 6 7
N=9
Первоначально J принимается равным 4. Исходная последователь- ность разбивается на следующие четыре части K(1) K(5) K(9) 12 1 7 K(2) K(6) 5 9 K(3) K(7) 4 8 K(4) K(8) 3 6 После упорядочения элементов внутри каждой последовательности набор данных будет иметь следующий вид: К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8) K(9) 1 5 4 3 7 9 8 6 12. Затем шаг J сокращается вдвое и становится равным 2. Образуются следующие 2 последовательности элементов, отстоящих друг от друга на 2 элемента K(1) K(3) K(5) K(7) K(9) 1 4 7 8 12
|