53463

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

Доклад

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

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

Русский

2014-04-01

26.29 KB

0 чел.

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

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

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

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

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

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

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

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

 


 

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

51361. Красноярский территориальный центр фирменного транспортного обслуживания 61.42 KB
  Сокращенное наименование Подразделения: Красноярский ТЦФТО ОАО РЖД. Подразделение для организации и осуществления своей деятельности открывает расчетный счет ОАО РЖД в банках и иных кредитных организациях в порядке установленном законодательством Российской Федерации внутренними документами ОАО РЖД Филиала. Подразделение имеет круглую печать содержащую его сокращенное наименование указание на его место нахождения а также полное фирменное наименование ОАО РЖД. Подразделение может иметь штампы и бланки со своим наименованием...
51362. Визуализация графика математической функции 1.04 MB
  Получение значения объекта step сохранение его в переменную s; получение значения объекта xmin с последующим преобразованием в формат flot и сохранением в переменную x0; получение значения объекта xmx с последующим преобразованием в формат flot и сохранением в переменную x1; получение значения объекта osx сохранение его в переменную sx; получение значения объекта osy сохранение его в переменную sy; получение значения объекта oscle сохранение его в переменную sc; создание сигнала chnge c передачей параметров...
51365. Демультиплексоры 48.24 KB
  Техническое задание Требуется спроектировать четырехразрядный демультиплексор на языке VHDL составить таблицу истинности спроектированного устройства показать логическую и техническую схемы и привести временную диаграмму с полученными результатами. Спроектировать четырехразрядный демультиплексор имеющий два входа адресный и информационный и один выход на языке VHDL. ДеМультиплексор позволяет передавать сигнал с одного входа на...
51366. Экономический анализ финансово-хозяйственной деятельности ООО «Адидас» 329 KB
  Организационная характеристика предприятия Экономический анализ финансово-хозяйственной деятельности предприятия Основные цели преддипломной практики: закрепление расширение углубление и систематизацию знаний полученных при изучении общепрофессиональных и специальных дисциплин на основе изучения деятельности предприятия отрасли; проведение системного анализа организации с целью выявления проблем управления и разработки мероприятий по их устранению; более глубоко освоить методы и приемы системного анализа; сбор и...
51368. Исследование начальной остойчивости плавучей полупогружной буровой установки 155 KB
  Ознакомление студентов с особенностями остойчивости плавучих полупогружных буровых установок (ППБУ) и их поведения на взволнованной поверхности моря, изучение основных положений теории и расчета, а также ознакомление с методикой постановки эксперимента по определению параметров начальной остойчивости плавучих технических средств для освоения шельфа.
51369. Двухфазная СМО с отказами 95.5 KB
  Для упрощения расчёта представим данную СМО как совокупность 2ух одноканальных. Т.к. в данной системе очередь не бесконечной длинны, то все расчёты будут не очень точны. Но главная цель проведения данных расчётов – это сравнение их результатов с результатами имитационной модели (программой). Для оценки соответствия результатов такой точности будет достаточно.