Расческа сортировка

Расческа сортировка

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

Гребень рода является относительно простой алгоритм сортировки , первоначально разработанный Влодзимежем Dobosiewicz и Артура Borowy в 1980 году ^{[1] [2]} позже вновь (и получил название «Combsort») Стивен Лейси и Ричард Box в 1991 году ^[3] Comb рода улучшает пузырьковую сортировку так же, как Shellsort улучшает сортировку вставкой .

nist.gov ' s „уменьшение приростарода“ определение упоминает термин „гребенку рода“как визуализируя итерационный проходят данные „ где зубы гребенки прикосновения;“ первый термин связан с Доном Кнутом . ^[4]

Алгоритм [ править ]

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

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

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

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

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

Псевдокод [ править ]

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

Код Python [ править ]

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

Защиту  combsort_inplace ( данные ):  длина  =  LEN ( данные )  термоусадочная  =  1,3  _gap  =  длина  отсортирован  =  Ложные  пока  не  отсортирован :  # Python не имеет встроенной команды «пол» функция, так что мы / я просто одну переменную (_gap) быть усадке,  # и целочисленную переменную (пробел) для хранения усечения (другой переменной) в и  # для использования при индексации  _gap  / =  shrink  # gap = np.floor (_gap)  gap  =  int ( _gap )  if gap  <=  1 :  sorted  =  True  gap  =  1  # эквивалентно `i = 0; while (i + gap) <length: ... {тело цикла} ... i + = 1`  для  i  в  диапазоне ( длина  -  пробел ):  sm  =  gap  +  i  if  data [ i ]  >  data [ sm ]:  # поскольку Python очень хорош, он выполняет обмен  данными [ i ],  data [ sm ]  =  data [ sm],  data [ i ]  sorted  =  Falsedef  combsort ( data ):  length  =  len ( data )  shrink  =  1.3  _gap  =  length  out  =  list ( data )  is_sorted  =  False,  пока  не  is_sorted :  _gap  / =  shrink  gap  =  int ( _gap )  if  gap  <=  1 :  is_sorted  =  True  разрыв  =  1  для  я  в диапазон ( длина  -  пробел ):  sm  =  пробел  +  i  if  out [ i ]  >  out [ sm ]:  out [ i ],  out [ sm ]  =  out [ sm ],  out [ i ]  is_sorted  =  false  return  out

См. Также [ править ]

Реализация алгоритма Викибука имеет страницу по теме: Сортировка гребенок

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

Ссылки [ править ]