53463

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

Доклад

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

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

Русский

2014-04-01

26.29 KB

0 чел.

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

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

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

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

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

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

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

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

 


 

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

34613. Америка в XVIII веке: Просвещение, иммиграция, предпосылки Войны за независимость 16.84 KB
  Основным проводником просветительских идей в колониальной Америке XVIII в. в Америке возникают университеты. Предпосылки войны за независимость Война североамериканских колоний за независимость 1775 1783 явилась закономерным результатом тех сложных процессов которые происходили как в Америке так и в самой Англии. когда английский главнокомандующий в Америке генерал Гейдж распорядился захватить склад оружия устроенный патриотами недалеко от Бостона и арестовать лидеров заговорщиков.
34614. Война за независимость 24.47 KB
  Ход войны 17 апреля 1775 года произошло первое вооруженное столкновение между британскими войсками и американскими сепаратистами. Британские войска заперлись в Бостоне. Однако британские войска отразили вторжение. Британские войска перешли в наступление.
34615. Образование Демократической и Республиканской партий в США 21.76 KB
  Республиканская политическая партия является более консервативной чем демократическая не имеет постоянного членства 23 избирателей США считают себя республиканцами. После победы северян и их лидера Авраама Линкольна в классовой борьбе республиканцы почти 40 лет непрерывно правили США. Люди из команды Рональда Рейгана правили США до 2009года.
34616. Реформистское движение при президентах Т. Рузвельте и В. Вильсоне. Американский империализм 18.72 KB
  В своей политике Рузвельт исходил из необходимости увеличения роли государства считая что огромной власти корпораций необходимо противопоставить еще большую власть правительства. Реформаторская деятельность Рузвельта была начата шумной кампанией против злоупотреблений трестов. За ним пришла очередь судебных процессов против треста скотобоен Чикаго табачного и сахарного трестов и других крупных монополистических объединений. Рузвельт добился ускорения судопроизводства по делам о нарушении антитрестовского законодательства и открытие дел...
34617. Ревущие двадцатые 19.76 KB
  Экономика: фермеры и горнорудная промышленность переживали трудные времена после войны но экономика США быстро перестроилась на мирное производство Америка стала самой богатой страной мира промышленность обеспечивала массовое производство общество привыкло к потребительству солдаты после войны получили жалованье за службу прекращение заказов поначалу вызвало в экономике депрессию но по мере возвращения демобилизованных солдат в мирную жизнь она прекратилась предложение превышало спрос низкие цены на товары стимуляция продаж...
34618. «Новый курс» Ф.Рузвельта 18.18 KB
  В принятом Чрезвычайном законе о банках предусматривалось возобновление функций и получение правительственных кредитов займов из федеральной резервной системы хотя это разрешалось только наиболее крупным банкам. был принят один из двух наиболее важных законов закон о восстановлении национальной промышленности НИРА. Закон о восстановлении промышленности вводил систему государственного регулирования этого подразделения экономики. Во втором и третьем разделах закона...
34619. Историко-литературная концепция Белинского и ее эволюция 32.5 KB
  Вся литература до Пушкина – пересаженное иноземное растение. В слово натуральная он вкладывал понятие литература для народа а так же литература философствующая. Он понимал что есть литература как зеркало общества Гоголь НШ и литература как зеркало человека бытийственность.
34620. Мастерство полемического стиля Белинского 23 KB
  Приемы полемики: каждая статья носит прямой или скрытый полемический характер. прием интеллектуальной бури. прием иронической ремарки независимо от того о ком он пишет. прием притворного простодушия.
34621. Историко-литературная концепция Белинского и ее эволюция 45.5 KB
  Вся литература до Пушкина – пересаженное иноземное растение. Сочинения Пушкина периоды: Ломоносовский карамзинский державинский пушкинский. Русская литра развивалась по двум направлениям которые слились в творчестве Пушкина. НШ как понимал ее Белинский никак не связана с творчеством Пушкина.