53463

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

Доклад

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

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

Русский

2014-04-01

26.29 KB

0 чел.

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

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

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

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

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

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

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

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

 


 

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

70114. ОЗНАЙОМЛЕННЯ З КОЛОРИТОМ І ТЕХНІКОЮ ВИКОНАННЯ ВИШИВОК, ВИКОРИСТАННЯ ЇХ У ПОБУТІ ТА ОДЯЗІ. РОБОТИ НАРОДНИХ МАЙСТРІВ 68 KB
  Використання домотканого полотна що має перпендикулярне переплетення ниток обумовлювало і загальний характер полтавської вишивки геометричні або геометризовані орнаментальні форми вирішені великими рельєфними масами.
70115. Текстовий процесор Microsoft Word. Робота з таблицями, графічними зображеннями та редактором формул 1010 KB
  Мета роботи:Ознайомитись з основними поняттями та принципами роботи з текстовим процесором Microsoft Word. Навчитись налаштовувати робоче середовище процесора, форматувати текст, працювати з графічними зображеннями, таблицями та підпрограмою Microsoft Equation.
70116. Формирование и развитие организаций 553.5 KB
  Факторы влияющие на развитие организаций № Факторы Способствуют Затрудняют 1 Природные ресурсы России 2 Трудовые ресурсы России 3 Территория страны 4 Национальный менталитет 5 Международные отношения 6 Государственно-политическое устройство страны...
70117. Подсчет суммы элементов квадратной матрицы, полученной из клавиатуры 55.5 KB
  Написать одну программу, с помощью которой можно задать размер квадратной матрицы. При этом размер должен быть нечётным числом и больше 7. При помощи генератора случайных чисел инициализировать матрицу целыми числами в диапазоне от -20 до +5.
70118. Изучение оператора цикла For 53 KB
  Это условие проверяется перед началом выполнения цикла, а затем—после каждого прибавления шага к счётчику цикла в операторе Next. Если оно выполнено, управление передается на оператор, следующий за Next, нет—выполняются операторы из тела цикла.
70119. Применение текстовых и календарных функций 40.5 KB
  Дан список сотрудников фирмы, содержащий паспортные данные (фамилию, имя, отчество, дату рождения, дату зачисления в состав фирмы). По этому списку составить список, содержащй следующие данные (фамилию и инициалы, возраст, рабочий стаж в фирме).
70121. ЭЛЕКТРОННАЯ ТАБЛИЦА EXCEL. ДИАГРАММЫ. ЗАДАЧА О ТРАЕКТОРИИ ДВИЖЕНИЯ ТЕЛА 2.07 MB
  Перед вызовом Мастера диаграмм предпочтительно выделить диапазоны ячеек содержащих информацию которая должна использоваться при создании диаграммы.2 Мастер диаграмм осуществляет пошаговое руководство процессом создания диаграммы.