Відкрити головне меню

Сортування гребінцем (англ. Comb sort) — спрощений алгоритм сортування, розроблений Влодеком Добошєвічем (Wlodek Dobosiewicz) у 1980 році, і пізніше заново слідженим та популяризованим Стефаном Лакеєм (Stephen Lacey) та Річардом Боксом (Richard Box), котрі написали про нього в журналі Byte Magazine у квітні 1991 р. Сортування гребінцем є поліпшенням алгоритму сортування бульбашкою, і конкурує у швидкодії з алгоритмом Швидке сортування. Основна його ідея полягає в тому, щоб усунути так званих «черепах», або малих значень ближче до кінця списку, оскільки у сортування бульбашкою вони сильно уповільнюють процес сортування. (Кролики та великі сортування на початку списку у сортуванні бульбашкою не являють собою проблеми).

Сортування гребінцем
Visualisation of comb sort
Клас Алгоритм сортування
Структура даних масив
Найгірша швидкодія [1]
Найкраща швидкодія
Середня швидкодія
Просторова складність у найгіршому випадку О(n) загальний, O(1) допоміжний
Оптимальний Так

У сортуванні бульбашкою, коли два елементи порівнюються, вони завжди мають розрив (відстань один від одного) рівну 1. Основна ідея сортування гребінцем полягає у тому, що цей розрив може бути більший одиниці. (Алгоритм Сортування Шелла також базується на даній ідеї, однак, він є модифікацією алгоритму сортування включенням, а не сортування бульбашкою).

Розрив починається зі значення, що рівне довжині списку, поділеного на фактор зменшення (зазвичай, 1.3; див. нижче), і список сортується з урахуванням цього значення (при необхідності воно заокруглюється до цілого). Потім розрив знову ділиться на фактор розриву, і список продовжує сортуватись з новим значенням, процес продовжується доти, доки розрив рівний 1. Далі список сортується з розривом рівним 1 доти, доки не буде повністю відсортований. Таким чином, фінальний етап сортування аналогічний такому ж у сортуванні бульбашкою, однак, до цього «черепах» усувається.

Фактор зменшенняРедагувати

Фактор зменшення справляє великий ефект на швидкість алгоритму сортування гребінцем. В оригінальній статті, автор пропонує значення 1.3 після багатьох експериментів з іншими значеннями.

Текст описує процес вдосконалення алгоритму використовуючи значення   як фактор зменшення. Вона також мість приклад використання алгоритму на псевдокоді.

Приклади реалізації на різних мовах програмуванняРедагувати

ПсевдокодРедагувати

function combsort11(array input)
    gap := input.size
    loop until gap <= 1 and swaps = 0
        if gap > 1
            gap := gap / 1.3
            if gap = 10 or gap = 9
                gap := 11
            end if
        end if
        
i := 0 swaps := 0
loop until i + gap <= input.size if input[i] > input[i+gap] swap(input[i], input[i+gap]) swaps := 1 end if i := i + 1 end loop
end loop end function

CРедагувати

int newGap(int gap)
{
    gap /= 1.3;

    if (gap == 9 || gap == 10)
        gap = 11;
    if (gap < 1)
        return 1;

    return gap;
}

void combSort(int* a, int len)
{
    int gap = len;
    bool swapped = true;

    while (gap > 1 || swapped)
    {
        swapped = false;
        gap = newGap(gap);

        for (int i = 0; i < len - gap; ++i)
        {
            if (a[i] > a[i + gap])
            {
                swap(a[i], a[i + gap]);
                swapped = true;
            }
        }
    }
}

JavaРедагувати

private static int newGap(int gap)
{
        gap = gap * 10 / 13;

        if(gap == 9 || gap == 10)
                gap = 11;
        if(gap < 1)
                return 1;

        return gap;
}

private static void sort(int a[])
{       int gap = a.length;
        boolean swapped;

        do {
                swapped = false;
                gap = newGap(gap);

		for(int i = 0; i < (a.length - gap); i++) {
			if(a[i] > a[i + gap]){
		        	swapped = true;
                                int temp = a[i];
                                a[i] = a[i + gap];
                                a[i + gap] = temp;
                        }
                }
        } while(gap > 1 || swapped);
}

PythonРедагувати

def update_gap(gap):
    gap = (gap * 10) / 13
    if gap == 9 or gap == 10:
        gap = 11
    return max(1, gap)

def combsort(x):
    gap = len(x)
    swapped = True
    if gap < 2:
        return
    while gap > 1 or swapped:
        gap = update_gap(gap)
        swapped = False
        for i in range(0, len(x) - gap, gap):
            if x[i] > x[i + gap]:
                x[i], x[i + gap] = x[i + gap], x[i]
                swapped = True

Див. такожРедагувати

ПриміткиРедагувати