Ryfujk

Сортування гребінцем

Клас	Алгоритм сортування
Структура даних	масив
Найгірша швидкодія	Ω(n2){displaystyle Omega (n^{2})}[1]
Найкраща швидкодія	O(n){displaystyle O(n)}
Середня швидкодія	Ω(nlogn){displaystyle Omega (nlogn)}
Просторова складність у найгіршому випадку	О(n) загальний, O(1) допоміжний
Оптимальний	Так

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

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

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

Фактор зменшення |

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

Текст описує процес вдосконалення алгоритму використовуючи значення 1/(1−1eφ)≈1.247330950103979{displaystyle 1/left(1-{frac {1}{e^{varphi }}}right)approx 1.247330950103979} як фактор зменшення. Вона також мість приклад використання алгоритму на псевдокоді.

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

Псевдокод |

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

Див. також |

• Сортування бульбашкою


• Сортування змішуванням

Примітки |

п о р Алгоритми сортування Теорія Обчислювальна складність | Нотація великого О | Відношення порядку | Список | Стабільність | Сортування порівняннями Сортування обміном Сортування бульбашкою | Сортування змішуванням | Odd-even sort | Сортування гребінцем | Сортування гнома | Швидке сортування Сортування вибором Сортування вибором | Пірамідальне сортування Сортування включенням Сортування включенням | Сортування Шелла | Сортування бінарним деревом | Сортування вставкою з проміжками | Patience sorting Сортування злиттям Сортування злиттям | Ниткоподібне сортування Алгоритми без порівнянь Сортування за розрядами | Сортування комірками | Сортування підрахунком | Цифрове сортування | Burstsort | Bead sort Інші Топологічне сортування | Sorting network | Bitonic sorter Непрактичні алгоритми Випадкове сортування | Stooge sort