53463

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

Доклад

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

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

Русский

2014-04-01

26.29 KB

0 чел.

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

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

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

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

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

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

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

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

 


 

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

9916. Распространение объектно-ориентированного подхода на информационную безопасность 79 KB
  Распространение объектно-ориентированного подхода на информационную безопасность В этой лекции закладываются методические основы курса. Кратко формулируются необходимые понятия объектно-ориентированного подхода, в соответствии с ним выделяются уровн...
9917. Наиболее распространенные угрозы 92.5 KB
  Наиболее распространенные угрозы Знание возможных угроз, а также уязвимых мест защиты, которые эти угрозы обычно эксплуатируют, необходимо для того, чтобы выбирать наиболее экономичные средства обеспечения безопасности. Основные опреде...
9918. Законодательный уровень информационной безопасности 134.5 KB
  Законодательный уровень информационной безопасности Эта лекция посвящена российскому и зарубежному законодательству в области ИБ и проблемам, которые существуют в настоящее время в российском законодательстве. Что такое законодательный уровень инфор...
9919. Стандарты и спецификации в области информационной без-опасности 229.5 KB
  Стандарты и спецификации в области информационной безопасности Дается обзор международных и национальных стандартов и спецификаций в области ИБ - от Оранжевой книги до ISO 15408. Демонстрируются как сильные, так и слабые стороны этих документов. Оце...
9920. Административный уровень информационной безопасности 69.5 KB
  Административный уровень информационной безопасности Вводятся ключевые понятия - политика безопасности и программа безопасности. Описывается структура соответствующих документов, меры по их разработке и сопровождению. Меры безопасности увязываются с...
9921. Управление рисками в информационной безопасности 60 KB
  Управление рисками Информационная безопасность должна достигаться экономически оправданными мерами. В реферате описывается методика, позволяющая сопоставить возможные потери от нарушений ИБ со стоимостью защитных средств. Основные понятия Управление...
9922. Процедурный уровень информационной безопасности 84.5 KB
  Процедурный уровень информационной безопасности Описываются основные классы мер процедурного уровня. Формулируются принципы, позволяющие обеспечить надежную защиту. Основные классы мер процедурного уровня Мы приступаем к рассмотрению мер безопасност...
9923. Основные программно-технические меры 67 KB
  Основные программно-технические меры Вводится понятие сервиса безопасности. Рассматриваются вопросы архитектурной безопасности, предлагается классификация сервисов. Основные понятия программно-технического уровня информационной безопасности Программ...
9924. Идентификация и аутентификация, управление доступом 141.5 KB
  Идентификация и аутентификация, управление доступом В данной лекции кратко описываются традиционные сервисы безопасности - идентификация и аутентификация, управление доступом. Сервисы безопасности мы будем рассматривать применительно к распреде...