53463

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

Доклад

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

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

Русский

2014-04-01

26.29 KB

0 чел.

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

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

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

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

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

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

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

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

 


 

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

75042. Широкая масленица 93 KB
  Тему для своего исследования мы выбрали не случайно, поскольку решили ставить коллекцию на тему «Масленица». Ведь для того, чтобы наиболее полно и достоверно отобразить народные обычаи в праздновании Масленицы на сцене, их нужно всесторонне изучить.
75043. Солнечная система и ее загадки 41 KB
  Происхождение Солнечной системы Современные методы исследования позволяют узнавать все новые и новые факты о Вселенной. Так до сих пор ведутся споры о происхождении Солнечной системы. Образование Солнечной системы из облака пыли и газа.
75044. Исторические личности периода Отечественной войны 1812 года 26.5 KB
  Задачи: Закрепить представления детей о том кто такие защитники Отечества полководцы. Познакомить детей с подвигами русских полководцев и с Бородинским сражением. Развивать речь детей обогащать словарь. Воспитывать у детей чувство гордости и уважение к защитникам Отечества.
75046. Жизнь зайца в домашних условиях 260 KB
  В июне месяце, окашивая дачу, папа выкосил трех маленьких зайчат, двое из которых шустро убежали в траву, а вот самый маленький стал новым членом нашей семьи, чтобы он не погиб от лап своих врагов решили: маленького зайчонка спасти от гибели и, выкормив его, понаблюдать за процессом его роста в домашних условиях.
75047. Немецкие автомобили 934.5 KB
  Ich heiße Eshow Wlad. Ich lerne in der Klasse 6. Unser Thema heißt „Das Deutsche Auto“. Im Jahre 2011 (zwanzighundertelf) feierte das Auto sein Jubiläum. Es ist 125 (hundertfünfundzwanzig) Jahre alt. Der vorige Sommer von 7 (siebenten) Mai bis zum 10 (zehnten) September hieß „der Autosommer“.
75048. Русская и немецкая школы. Какие они? 984.5 KB
  Ich heiße Antonowa Anna. Ich lerne in der Klasse 6 «А». Ab 2. Klasse lerne ich Deutsch. Das ist mein Lieblingsfach. Besonders gefiel mir das Thema “Deutsche Schülen. Wie sind sie?” Darüber diskutieren wir viel mit unseren Mitschülern.
75049. ВОЗНИКНОВЕНИЕ ЧИСЕЛ 695.5 KB
  В современном мире человек постоянно пользуется числами, даже не задумываясь об их происхождении. Без знания прошлого нельзя понять настоящее. Поэтому целью данной работы является исследование истории возникновения чисел, связанной с необходимостью выражения всех чисел знаками.
75050. Основные направления поэтического творчества Ф. Достоевского 111.5 KB
  Цель моей исследовательской работы: выявить основные направления поэтического творчества Ф. Достоевского. Объект исследования: произведения поэта, литература о жизни и творчестве поэта после выхода из острога в 1854 году. Задачи исследования я бы сформулировала так: «Каково поэтическое наследие Ф.М.Достоевского?»