53463

Оптимизация процедуры Shell_sort, особенности

Доклад

Информатика, кибернетика и программирование

Сортировка Шелла — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга.

Русский

2014-04-01

26.29 KB

0 чел.

Оптимизация процедуры Shell_sort, особенности.

Сортировка Шелла — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами. Аналогичный метод усовершенствования пузырьковой сортировки называется сортировка расчёской.

При сортировке Шелла сначала сравниваются и сортируются между собой значения, отстоящие один от другого на некотором расстоянии . После этого процедура повторяется для некоторых меньших значений , а завершается сортировка Шелла упорядочиванием элементов при . Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, например, пузырьковой, каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла это число может быть больше).

Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:

  1. отсутствие потребности в памяти под стек;
  2. отсутствие деградации при неудачных наборах данных — быстрая сортировка легко деградирует до O(n²), что хуже, чем худшее гарантированное время для сортировки Шелла.

Сортировка Шелла была названа в честь её изобретателя — Дональда Шелла, который опубликовал этот алгоритм в 1959 году.

Среднее время работы алгоритма зависит от длин промежутков — , на которых будут находиться сортируемые элементы исходного массива ёмкостью на каждом шаге алгоритма. Существует несколько подходов к выбору этих значений:

  1. первоначально используемая Шеллом последовательность длин промежутков:  
  2.  значения
  3. последовательность: , если i четное и , если i нечетное
  4.  все значения

 


 

А также другие работы, которые могут Вас заинтересовать

68719. Акты толкования права 23.5 KB
  Акт толкования официальный юридически значимый документ направленный на установление действительного смысла нормы права Акты толкования делятся на письменные могут облекаться в форму НПА приказы инструкции и т. Они могут облекаться в ту же форму что и нормативно-правовые акты издаваемые соответствующими...
68722. ОРФОЭПИЧЕСКИЕ НОРМЫ РУССКОГО ЛИТЕРАТУРНОГО ЯЗЫКА 44.03 KB
  Орфоэпия (от греческих слов: orthos - прямой, правильный и epos - речь) - это совокупность правил, устанавливающих единообразное произношение. Орфоэпия указывает, как должны произноситься те или иные звуки в определенных фонетических положениях, в определенных сочетаниях с другими звуками, а также в определенных...
68723. Традиционалистский и техногенный типы цивилизационного развития 25.5 KB
  Понятие цивилизации впервые возникло в 18 веке во Франции для обозначения общества, в котором господствует свобода, равенство и братство. Позднее в исторической и философской литературе под цивилизацией стали понимать различные культурно-исторические типы обществ, объединявших несколько государств...
68724. Инновационный рынок 20.58 KB
  Классификация научных организаций по секторам науки Сектор Содержание Государственный Организации министерств и ведомств которые осуществляют управление государством и удовлетворение потребностей общества в целом: государственная оборона общественный порядок здравоохранение культура социального обеспечения и пр.
68725. Закономерности глобализации мировой экономики и ее воздействие на функционирование национально-государственных систем. Теоретическая проблема экономической безопасности 48 KB
  Одним из ключевых процессов развития мировой экономики на грани ХХ ХХI веков является прогрессирующая глобализация т. Интернационализация хозяйственной деятельности это усиление взаимосвязи и взаимозависимости экономик отдельных стран влияние международных экономических отношений...
68727. Эпоха Возрождения как канун становления классической науки 40 KB
  В городах стали возникать светские центры науки и искусства деятельность которых находилась вне контроля церкви. В формировании мышления этой эпохи огромное влияние сыграло наследие античной науки. Особенности науки эпохи Возрождения: 1 антисхоластическая направленность взглядов и сочинений...