53463

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

Доклад

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

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

Русский

2014-04-01

26.29 KB

0 чел.

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

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

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

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

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

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

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

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

 


 

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

61103. ПОРЯДОК СЛІВ У РЕЧЕННІ. ЛОГІЧНИЙ НАГОЛОС 27.66 KB
  Мета: дати восьмикласникам поняття про прямий і зворотний порядок слів у реченні, навчати дотримуватися логічного наголосу при інтонуванні речень; розвивати організаційно-контрольні вміння виконувати спеціальні спостереження над мовним матеріалом; формувати загально-пізнавальні вміння правильно інтонувати різні за метою висловлювання речення...
61104. Утворення Єгипетської держави 59 KB
  Мета: на конкретному історичному матеріалі показати процес утворення Давньоєгипетської держави; розкрити суть понять: ном номарх держава фараон. Основні поняття: Єгипет Африка Ніл дельта Середземне море...
61105. КОНТРОЛЬНЕ АУДІЮВАННЯ ХУДОЖНЬОГО ТЕКСТУ 52 KB
  Мета: оцінити рівень орфографічної та пунктуаційної грамотності восьмикласників: правильно писати слова на вивчені орфографічні правила та слова визначені для запамятовування; ставити розділові знаки відповідно до опрацьованих правил пунктуації...
61106. Тематичне оцінювання з теми “Виникнення та розквіт Київської Русі” 66 KB
  Мета. Закріпити та поглибити знання учнів з історії виникнення та розквіту Київської Русі. Узагальнити основні поняття та події. Оцінити знання учнів з теми. Розвивати вміння ідентифікувати історичні явища за їх типовими ознаками.
61107. Господарське і повсякденне життя. Суспільство 52 KB
  Мета: ознайомити учнів із природними умови та розташуванням Давнього Єгипту, основними заняттями давніх єгиптян; простежити взаємозвязок між природними умовами і господарським розвитком Давнього Єгипту.
61108. ПІДМЕТ, СПОСОБИ ЙОГО ВИРАЖЕННЯ 867.65 KB
  Поглибити знання учнів про підмет як головний член речення; сформувати вміння виділяти підмети в двоскладному реченні, визначати способи їх вираження; удосконалити вміння конструювати речення з різними за способом вираження підметами; за допомогою мовленнєвокомунікативного дидактичного матеріалу поглибити світогляд восьмикласників щодо загальнолюдських цінностей.
61110. Розквіт Давньоєгипетської держави 47 KB
  Мета: Ознайомити учнів із основними періодами Давнього Єгипту; Простежити закономірності в зміні періодів розквіту й занепаду держави. Перетворення Єгипту на могутню державу в середині...
61111. Київська Русь за наступників Ярослава. Володимир Мономах 67.5 KB
  Мета. Проаналізувати становище Київської держави за наступників Ярослава, підкреслити складність історичного періоду. Визначити історичне значення Любецького з’їзду, роль Володимира Мономаха як державника.