53463

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

Доклад

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

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

Русский

2014-04-01

26.29 KB

0 чел.

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

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

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

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

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

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

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

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

 


 

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

54968. Великая Отечественная война. Сталинградская битва 70.5 KB
  Путина от 1 февраля 2013 года 215 мин Сталинград 3 мин. Капитуляция Паулюса под Сталинградом 3 мин. документы карточки аудио-материалы Левитан о победе под Сталинградом Понятийный минимум: Коренной перелом операция €œУран. 1 мин.
54969. Мелірування волосся способом «Трикутник» 540 KB
  Другий рівень репродукції Формування умінь якісно виконувати мелірування волосся способом трикутник з дотриманням правильної технологічної послідовності і всіх технічних умов. Навчально-матеріальна база уроку...
54970. Совокупный спрос и совокупное предложение. Факторы, определяющие их величину и динамику 23.49 KB
  Совокупный спрос — это спрос на общий объем товаров и услуг, который может быть реализован при соответствующем уровне цен в рамках национальной экономики.
54971. My favourite animal 51.5 KB
  Do you know anything about an owl? Let’s read the text and find out more information about it. Look at the blackboard. Here are some words from the text. Repeat them after me: a beak – beaks (дзьоб), soft (м’який, ніжний), centimeter, especially (особливо), mice, one mouse – two mice, insects (комахи), in silence (у тиші), total darkness (цілковита темрява). Read the text and be ready to translate it. (Учні читають текст вголос і перекладають його).
54972. Олесь Гончар — майстер малих літературних жанрів. Життя і творчість митця. Детальний аналіз новел «За мить до щастя», «Пізнє прозріння» 65.5 KB
  Мета: навчити учнів аналізувати епічний твір визначати новелістичний жанр виділяти провідні ідеї образи розкривати їх спираючись на текст; розвивати вміння використовувати деталі кольорову гаму для розкриття стильової палітри твору; виховувати усвідомлення філософської сутності щастя людини його відносності й короткочасності; навчити учнів пізнавати...
54973. Легка атлетика 56 KB
  Мета: Розвиток основних фізичних якостей та рухових здібностей, підвищення рівня фізичної підготовності учнів.
54974. Макроэкономическое равновесие. Модель «изъятия – издержки» 17.67 KB
  Важным инструментом прогнозирования является разработанный В.Леонтьевым межотраслевой равновесный баланс, позволяющий анализировать экономику, как национальную, так и отдельных регионов и на основе этого вырабатывать адекватные меры.
54975. Полтавская битва 64.5 KB
  Карл XII вторгся в Польшу занял Варшаву и посадил на трон своего ставленника Станислава Лещинского. После того как Карл XII занял Саксонию Август II вынужден был заключить с ним мир. Что таким образом произошло с Северным союзом Петр I прекрасно осознавал что теперь все силы Карл XII обрушит на Россию. Карл XII подошел к русской границе.