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

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

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

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

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

Алгоритм

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

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

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

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

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

Псевдокод

function combsort(array input) is

    gap := input.size // Initialize gap size
    shrink := 1.3 // Set the gap shrink factor
    sorted := false

    loop while sorted = false
        // Update the gap value for a next comb
        gap := floor(gap / shrink)
        if gap ≤ 1 then
            gap := 1
            sorted := true // If there are no swaps this pass, we are done
        end if

        // A single "comb" over the input list
        i := 0
        loop while i + gap < input.size // See Shell sort for a similar idea
            if input[i] > input[i+gap] then
                swap(input[i], input[i+gap])
                sorted := false
                // If this assignment never happens within the loop,
                // then there have been no swaps and the list is sorted.
             end if
    
             i := i + 1
         end loop
     end loop
end function

Код Python

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

def combsort_inplace(data):
    length = len(data)
    shrink = 1.3
    _gap = length
    sorted = False
    while not sorted:
        # Python has no builtin 'floor' function, so we/I just have one variable (_gap) to be shrunk,
        # and an integer variable (gap) to store the truncation (of the other variable) in and
        # to use for stuff pertaining to indexing
        _gap /= shrink
        # gap = np.floor(_gap)
        gap = int(_gap)
        if gap <= 1:
            sorted = True
            gap = 1
        # equivalent to `i = 0; while (i + gap) < length: ...{loop body}... i += 1`
        for i in range(length - gap):
            sm = gap + i
            if data[i] > data[sm]:
                # because Python is very nice, this accomplishes the swap
                data[i], data[sm] = data[sm], data[i]
                sorted = False


def combsort(data):
    length = len(data)
    shrink = 1.3
    _gap = length
    out = list(data)
    is_sorted = False
    while not is_sorted:
        _gap /= shrink
        gap = int(_gap)
        if gap <= 1:
            is_sorted = True
            gap = 1
        for i in range(length - gap):
            sm = gap + i
            if out[i] > out[sm]:
                out[i], out[sm] = out[sm], out[i]
                is_sorted = False
    return out

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

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

Рекомендации