Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


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




Сортировка Шелла – это улучшенный метод сортировки вставками. Был предложен Д.Л. Шеллом в 1959 г. Рассмотрим этот метод на примере.

Пример:

Первичный массив ключей X1   X2   X3   X4   X5   X6   X7  
Просмотр 1 Шаг 5 Проходов 5
Просмотр 2 Шаг 3 Проходов 3
Просмотр 3 Шаг 1 Проходов 1  
Отсортированный массив ключей

При первом просмотре группируются и сортируются элементы, отстоящие друг от друга на 5 позиций: (Х16), (Х2,Х7), (Х3), (Х4), (Х5); при втором проходе — элементы, отстоящие друг от друга на три позиции: (Х14,Х7), (Х2,Х5), (Х3,Х6); при третьем — на 1 позицию.

Поскольку первый в сортировке Шелла используемый шаг является большим, отдельные подмассивы достаточно малы по отношению к исходному. Таким образом, сортировка включением над этими подмассивами работает достаточно быстро – O(N2) (эффективно при малом N). Сортировка каждого подмассива приводит к тому, что весь массив становиться ближе к отсортированному виду, что также делает эффективным использование сортировки включением. Так как массив становится более упорядоченным, то O(N) < порядок ФBC <O(N2).

Если некоторый массив частично отсортирован с использованием шага k, а затем сортируется частично с использованием шага j, то данный массив остается частично отсортированным по шагу k, т.е. последующие частичные сортировки не нарушают результата предыдущих сортировок. Следующий шаг отличается от предыдущего следующим образом: ht=1, hi+1<hi.


Поделиться:

Дата добавления: 2015-04-18; просмотров: 59; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты