53463

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

Доклад

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

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

Русский

2014-04-01

26.29 KB

0 чел.

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

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

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

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

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

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

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

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

 


 

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

70461. Конфликт как форма социального взаимодействия 30 KB
  Понятие конфликт характеризуется исключительной широтой содержания и употребляется в разнообразных значениях. Самым общим образом конфликт можно определить как предельное обострение противоречий. В специальной литературе конфликты рассматриваются на социальном...
70462. Основные модели конфликта 44.5 KB
  Любые организационные изменения противоречивые ситуации деловые и личностные отношения между людьми нередко порождают конфликтные ситуации которые субъективно сопровождаются серьезными психологическими переживаниями.
70463. Проблема оптимального и эффективного поведения в конфликт 48 KB
  Методы прекращения конфликта. Уклонение Такой стиль поведения обычно выбирают в тех случаях когда: проблема вызвавшая столкновение не представляется субъекту конфликта существенной; предмет расхождения по его мнению мелочный основан на вкусовых различиях не заслуживает траты времени и сил...
70465. Общение в единстве процессов обмена информации, восприятия и понимания людьми друг друга, воздействия и взаимодействия 50 KB
  Из определения общения вытекает что это сложный процесс в который входят три составляющие: коммуникативная сторона общения обмен информацией между людьми; интерактивная сторона организация взаимодействия между индивидами; перцептивная сторона процесс восприятия друг друга партнерами...
70466. Социально-психологические закономерности формирования первого впечатления о человеке 29.5 KB
  Среди факторов которые определяют характер формирующегося у нас впечатления о человеке которого мы встречаем в своей жизни впервые важнейшее значение имеют особенности внешнего облика и поведения человека о котором у нас формируется мнение.
70467. Механизмы межличностного восприятия 27.5 KB
  Значительное число исследований восприятия межличностного посвящено изучению формирования первого впечатления о человеке. В них выясняются закономерности достраивания образа другого человека на основе наличной обычно ограниченной информации о нем а также при выявлении...
70468. Психология воздействия как область социальной психологии 42.5 KB
  Психология воздействия одно из самых традиционных направлений социально-психологического знания. Однако несмотря на это проблематика психологического воздействия и сегодня продолжает оставаться пожалуй наиболее популярной и интегрирующей сферой исследовательских и практических интересов...
70469. Социально-психологические механизмы и факторы формирования убеждений 32 KB
  Во-первых образуя упорядоченную систему взглядов и представлений человека совокупность убеждений выступает как его мировоззрение; во-вторых под убеждением понимают процесс усвоения человеком внешнего мира что предполагает качественное изменение исходных установок под влиянием жизненного...