Сортировка гребней - Comb sort

Сортировка гребней

Сортировка гребней с коэффициентом усадки k=1.24733
Класс	Алгоритм сортировки
Структура данных	Массив
Худший случай спектакль	${\displaystyle O(n^{2})}$[1]
Лучший случай спектакль	${\displaystyle \Theta (n\log n)}$
Средний спектакль	${\displaystyle \Omega (n^{2}/2^{p})}$, где п это количество приращений[1]
Худший случай космическая сложность	${\displaystyle O(1)}$

Сортировка гребней относительно простой алгоритм сортировки первоначально спроектированный Влодзимежем Добосевичем и Артуром Боровым в 1980 году.^[1][2] позже вновь обнаружен Стивеном Лейси и Ричардом Боксом в 1991 году.^[3] Сортировка гребней улучшается пузырьковая сортировка.

Алгоритм

Основная идея - устранить черепахи, или небольшие значения в конце списка, так как при пузырьковой сортировке они значительно замедляют сортировку. Кролики, большие значения в начале списка не создают проблем при пузырьковой сортировке.

В пузырьковая сортировка, когда сравниваются любые два элемента, у них всегда есть разрыв (расстояние друг от друга) 1. Основная идея гребенчатой ​​сортировки заключается в том, что зазор может быть намного больше, чем 1. Внутренний цикл пузырьковой сортировки, который фактически выполняет своп, модифицируется так, что промежуток между заменяемыми элементами уменьшается (для каждой итерации внешнего цикла) с шагом «коэффициента сжатия» k: [ п/k, п/k², п/k³, ..., 1 ].

Разрыв начинается с длины списка п сортировка деленная на коэффициент усадки k (обычно 1,3; см. ниже), и с этим промежутком применяется один проход вышеупомянутой модифицированной пузырьковой сортировки. Затем промежуток снова делится на коэффициент сжатия, список сортируется с этим новым промежутком, и процесс повторяется до тех пор, пока промежуток не станет 1. На этом этапе сортировка гребенок продолжается с промежутком, равным 1, до тех пор, пока список не будет полностью отсортирован. Таким образом, заключительный этап сортировки эквивалентен сортировке по пузырькам, но к этому времени с большинством черепах уже справились, поэтому сортировка по пузырькам будет эффективной.

Фактор усадки имеет большое влияние на эффективность гребенчатой ​​сортировки. k = 1,3 был предложен в качестве идеального коэффициента сжатия авторами оригинальной статьи после эмпирического тестирования более 200 000 случайных списков. Слишком маленькое значение замедляет алгоритм, делая ненужное много сравнений, в то время как слишком большое значение не позволяет эффективно работать с черепахами, требуя много проходов с 1 размером промежутка.

Схема повторных проходов сортировки с уменьшающимися зазорами аналогична Shellsort, но в Shellsort массив полностью сортируется на каждом проходе перед переходом к следующему наименьшему промежутку. Проходы гребенчатой ​​сортировки не полностью сортируют элементы. Это причина того, что Последовательности пробелов Shellsort имеют больший оптимальный коэффициент усадки около 2,2.

Псевдокод

функция combsort (массив ввод) является    пробел: = input.size // Инициализируем размер зазора    усадка: = 1,3 // Устанавливаем коэффициент сжатия зазора    отсортировано: = ложь цикл пока отсортировано = ложь // Обновляем значение зазора для следующего гребня        зазор: = пол (зазор / усадка) если разрыв ≤ 1 тогда            пробел: = 1 отсортировано: = верно // Если на этом проходе нет свопов, мы закончили        конец, если        // Одиночный "гребень" над входным списком        я: = 0 цикл пока я + пробел  // Увидеть Сортировка оболочки за аналогичную идею            если input [i]> input [i + пробел] тогда                своп (input [i], input [i + gap]) sorted: = false // Если это присвоение никогда не происходит в цикле, // значит, свопы не производились и список сортируется.             конец, если                 я: = я + 1 конец цикла     конец циклаконечная функция

Код Python

Плюс две быстрые реализации Python: одна работает со списком (или массивом, или другим изменяемым типом, где операции, используемые с ним, имеют смысл для языка) на месте, другая создает список с теми же значениями, что и заданные данные, и возвращает это после сортировки (аналогично встроенной функции `sorted`).

def combsort_inplace(данные):    длина = len(данные)    сокращаться = 1.3    _gap = длина    отсортированный = Ложь    в то время как не отсортированный:        # Python не имеет встроенной функции пола, поэтому у нас / меня есть только одна переменная (_gap), которую нужно сжать,        # и целочисленную переменную (пробел) для хранения усечения (другой переменной) в и        # использовать для вещей, относящихся к индексации        _gap /= сокращаться        # gap = np.floor (_gap)        разрыв = int(разрыв)        если разрыв <= 1:            отсортированный = Правда            разрыв = 1        # эквивалентно `i = 0; while (i + gap)         для я в ассортимент(длина - разрыв):            см = разрыв + я            если данные[я] > данные[см]:                # поскольку Python очень хорош, это выполняет замену                данные[я], данные[см] = данные[см], данные[я]                отсортированный = Ложьdef расчесывать(данные):    длина = len(данные)    сокращаться = 1.3    _gap = длина    вне = список(данные)    отсортированный = Ложь    в то время как не отсортированный:        _gap /= сокращаться        разрыв = int(_gap)        если разрыв <= 1:            отсортированный = Правда            разрыв = 1        для я в ассортимент(длина - разрыв):            см = разрыв + я            если вне[я] > вне[см]:                вне[я], вне[см] = вне[см], вне[я]                отсортированный = Ложь    вернуть вне

Смотрите также

• Пузырьковая сортировка, обычно более медленный алгоритм, является основой сортировки гребенок.
• Сорт коктейлей, или двунаправленная пузырьковая сортировка, представляет собой разновидность пузырьковой сортировки, которая также решает проблему черепах, хотя и менее эффективно.

использованная литература

1. Брейова, Б. (15 сентября 2001 г.). «Анализ вариантов Shellsort». Инф. Обработать. Lett. 79 (5): 223–227. Дои:10.1016 / S0020-0190 (00) 00223-4.
2. Влодзимеж Добосевич (1980). «Эффективный вариант пузырьковой сортировки». Письма об обработке информации. 11: 5–6. Дои:10.1016/0020-0190(80)90022-8.
3. «Быстрая легкая сортировка», Байт Журнал, Апрель 1991 г.