53463

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

Доклад

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

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

Русский

2014-04-01

26.29 KB

0 чел.

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

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

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

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

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

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

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

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

 


 

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

45933. Приводы зажимных устройств 1.73 MB
  Недостатки: незначительная плавность перемещения рабочих органов особенно при переменой нагрузке; низкое давление воздуха 04 мПа обуславливающие большие размеры приводов для приложения значительных усилий. на всех производственных участках подаётся воздушная среда давлением до 1МПа. Пневмоприводы рассчитываются на прочность при Р=06мПа а исходное усилие определяется при р=04МПа. Испытания их осуществляют при р не менее 09МПа.
45934. Цели, принципы, функции и основные задачи стандартизации 16.4 KB
  В соответствии с Федеральным Законом О техническом регулировании стандартизация осуществляется в целях: повышения уровня безопасности жизни или здоровья граждан имущества физических или юридических лиц государственного или муниципального имущества экологической безопасности безопасности жизни или здоровья животных и растений и содействия соблюдению требований технических регламентов; повышения уровня безопасности объектов с учетом риска возникновения чрезвычайных ситуаций природного и техногенного характера; обеспечения...
45935. Основные понятия в области метрологии. Метрология. Измерение. Погрешности измерения. Средство измерения. Единство измерений. Проверка средств измерений 18.03 KB
  Единство измерений. Проверка средств измерений.Рассматривает общие теоретические проблемы разработка теории и проблем измерений физических величин их единиц методов измерений.Устанавливает обязательные технические и юридические требования по применению единиц физической величины методов и средств измерений.
45936. Погрешности средств измерений. Систематическая погрешность средств измерений. Случайная погрешность средств измерений. Абсолютная, относительная погрешность. Точность средств измерений. Класс точности средств измерений 12.85 KB
  Погрешности средств измерений. Систематическая погрешность средств измерений. Случайная погрешность средств измерений. Точность средств измерений.
45937. Эталоны единиц физической величины. Эталон еденицы физической величины. Поверочная схема для средств измерений. Рабочий эталон. Вторичный эталон. Международный эталон 12.86 KB
  Эталоны единиц физической величины. Эталон еденицы физической величины. Рабочий эталон. Вторичный эталон.
45938. Средства измерительной техники. Средство измерений. Автоматичесое средство измерений. Автоматизированное средство измерений 12.24 KB
  Средство измерений. Автоматичесое средство измерений. Автоматизированное средство измерений. Средства измерительной техники измерительная техника обобщающее понятие охватывающее технические средства специально предназначенные для измерений.
45939. Классификация размерных цепей. Основные термины и определения. Метод расчета размерных цепей, обеспечивающие полную взаимозаменяемость 35.97 KB
  Размерные цепи отражают объективные размерные связи в конструкции машины технологических процессах изготовления ее детали и сборки при измерении возникающие в соответствии с условиями решаемых задач. Обозначаются размерные цепи прописными буквами русского алфавита и строчными буквами греческого алфавита кроме . Размеры образующие размерную цепь называют звеньями размерной цепи. Одно звено в размерной цепи замыкающее исходное а остальные составляющие.
45941. Назначение и виды валов и осей. Типы соединения вала с установленными на нем деталями. Технические требования к рабочим поверхностям вала. Расчет вала на прочность по напряжению изгиба и кручения 28.5 KB
  Валы в отличие от осей предназначены для передачи вращающих моментов и в большинстве случаев для поддержания вращающихся вместе с ними относительно подшипников различных деталей машин. Валы несущие на себе детали через которые передается вращающий момент воспринимают от этих деталей нагрузки и следовательно работают одновременно на изгиб и кручение. При действии на установленные на валах детали осевых нагрузок валы дополнительно работают на растяжение или сжатие. Прямые валы в зависимости от...