Студопедия

КАТЕГОРИИ:

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



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




Читайте также:
  1. Билет № 43 Сортировка и фильтрация данных в БД Access. Виды фильтров
  2. МЕДИЦИНСКАЯ СОРТИРОВКА ПОРАЖЕННЫХ ПРИ КАТАСТРОФАХ.
  3. Медицинская сортировка: определение, цель, виды. Сортировочные признаки.
  4. Многофазная сортировка.
  5. Пирамидальная сортировка
  6. Поиск и сортировка данных, индексирование базы данных
  7. Поиск, сортировка и фильтрация данных.
  8. Сортировка двоичным деревом
  9. Сортировка методом турнира с выбыванием
  10. Сортировка одномерного массива.

Сортировка Шелла – это улучшенный метод сортировки вставками. Был предложен Д.Л. Шеллом в 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; просмотров: 6; Нарушение авторских прав





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