53463

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

Доклад

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

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

Русский

2014-04-01

26.29 KB

0 чел.

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

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

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

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

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

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

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

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

 


 

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

83310. Технико-экономические расчеты при проектировании участка механической обработки детали типа крышка в условиях серийного типа производства. Режим работы двусменный 226.57 KB
  Для предприятий серийного производства характерны значительно меньшие, чем в единичном, трудоемкость и себестоимость изготовления изделий. В серийном производстве, по сравнению с единичным, изделия обрабатываются с меньшими перерывами, что снижает объемы незавершенного производства.
83311. УЧЕТ, ОЦЕНКА И ПЕРЕОЦЕНКА ОСНОВНЫХ ФОНДОВ 773.5 KB
  Это вызвано тем что доля основных фондов в общем объеме средств находящихся в распоряжении предприятия достигает 70 и более. Для более полной характеристики состояния средств труда следует проводить аттестацию каждого рабочего места которая представляет собой комплексную....
83313. Журналистское мастерство Василия Пескова 154 KB
  Каждый из нас имеет свою судьбу. Все события в нашей жизни складываются не просто так, а в связи с какими-либо обстоятельствами; при которых мы ведем себя по-разному. В нашей жизни столько всего случается: хорошего и не очень, но за всё, что бы, ни произошло, мы должны благодарить судьбу...
83314. Проект и разработка новой продукции для кафе «Муза» 82.31 KB
  Исходя из важности появления все новых предприятий общественного питания, на рынке актуальность исследуемой темы заключается в расширении ранка предприятий общественного питания Богородска, проектировании и разработке новой продукции, для кафе, создание новой концепции предприятия...
83315. Финансовое управление деятельностью корпорации 114.04 KB
  Знание и понимание происходящих процессов позволяют своевременно отвечать на возникающие вопросы и принимать решения о соотношении денежных ресурсов и товарно–материальных ценностей, дивидендной и инвестиционной политики, структуры капитала и его активов.
83316. Анализ эффективности использования оборотных средств 112.52 KB
  Предприятие, начинающее свою деятельность, должно располагать определённой денежной суммой. Оборотные средства предприятий призваны обеспечивать постоянное непрерывное их движение на всех стадиях кругооборота с тем, чтобы удовлетворять потребности производства в денежных и материальных ресурсах...
83317. ТЕНДЕНЦИИ И НАПРАВЛЕНИЯ СОВЕРШЕНСТВОВАНИЯ СОЦИАЛЬНОЙ ЗАЩИТЫ В РЕСПУБЛИКЕ БЕЛАРУСЬ 108.04 KB
  Для Республики Беларусь вопрос социальной политики, политики социальных гарантий и защиты, политики регулирования доходов населения является как никогда актуальным. Согласно Конституции, Республика Беларусь имеет статус социального, что подразумевает высокие социальные расходы государства на нужды общества.
83318. Расчет характеристик систем передачи информации и разработка их схемных решений 492 KB
  В ходе выполнения курсового проекта необходимо рассчитать характеристики системы передачи информации, разработать структурную и функциональную схемы рассчитанной системы для заданного варианта. Анализ существующих методов передачи информации в ИТС Анализ сообщений различной физической природы...