53463

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

Доклад

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

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

Русский

2014-04-01

26.29 KB

0 чел.

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

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

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

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

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

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

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

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

 


 

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

50592. Прибор регистрирующий ДИСК 250М 75.5 KB
  ДИСК 250М прибор построенный на микропроцессорной элементной базе предназначен для измерения регистрации сигнализации и регулирования параметров технологических процессов представленных унифицированными сигналами и сигналами от термопар термопреобразователей сопротивления дифференциальнотрансформаторных датчиков и пирометров. ДИСК 250М объединяет в одном исполнении все функциональное разнообразие многочисленных исполнений прибора ДИСК 250. Исключение составляют приборы для измерения температуры жидких металлов ДИСК 250С и сигналов...
50595. ИССЛЕДОВАНИЕ ЭРГОНОМИЧЕСКИХ СВОЙСТВ ИНТЕРФЕЙСА ПРИЛОЖЕНИЯ 144 KB
  Чаще всего термин применяется по отношению к компьютерным программам, однако под ним может подразумеваться любая система взаимодействия с устройствами, способными к интерактивному общению с пользователем. Несколько широко распространённых примеров...
50596. КОМПЕНСАЦИЯ РЕАКТИВНОЙ МОЩНОСТИ В ЭЛЕКТРИЧЕСКИХ СЕТЯХ 344 KB
  Цель работы: исследование влияния продольной и поперечной компенсации реактивной мощности на параметры электрической сети. Принципиальная электрическая схема лабораторного стенда Рис. 1 Результаты экспериментальных исследований (без компенсации и с поперечной компенсацией)
50598. АНАЛИЗ РЕЖИМОВ КОЛЬЦЕВЫХ СЕТЕЙ 57.5 KB
  Проделав лабораторную работу, мы исследовали режимы работы кольцевых сетей. Выяснили, что при одинаковых напряжения питающих пунктов, вследствие естественного перераспределения мощностей в замкнутой однородной сети, потери мощности получаются минимальными.
50599. АНАЛИЗ РЕЖИМОВ РАЗОМКНУТЫХ СЕТЕЙ 52.5 KB
  Проделав лабораторную работу, мы исследовали режимы работы разомкнутых сетей. Анализируя графики можно сделать вывод, что ток в линии прямо пропорционален мощности, поэтому увеличение мощности потребителя ведёт к увеличению тока, в связи с этим увеличиваются потери в линии и возникает просадка (снижение) уровня напряжения, что так же хорошо видно на графиках.
50600. Импульсные стабилизаторы напряжения 143 KB
  Цель работы Изучить назначение принцип действия свойства и возможные схемотехнические решения импульсных стабилизаторов напряжения. Задание Ознакомиться с принципами построения характеристиками и свойствами импульсных стабилизаторов напряжения. Исследовать свойства импульсных стабилизаторов напряжения построенного на биполярных транзисторах.