Comb sort

"Comb sort" je relativno jednostavan algoritam za sortiranje. Napisao ga je Włodzimierz Dobosiewicz, 1980. Kasnije je ponovo otkriven od strane Stephen Lacey-a i Richard Box-a, 1991. Comb sort je unapređeni bubble sort.

Algoritam

Osnovna ideja je da se eliminišu "kornjače" (turtles), tj. male vrednosti blizu kraja liste, koje su u bubble sort-u značajno usporavale raspoređivanje. "Zečevi" (rabbits), velike vrednosti na početku niza, nisu predstavljale nikakav problem u bubble sort-u.

Kada se bilo koja dva elementa uporede u 'bubble sort'-u razlika između njihovih indeksa je uvek 1. Osnovna ideja comb sort-a je ta da ta razlika može da bude mnogo veća od 1 ('shell sort' se takođe bazira na ovoj ideji, ali on je češće modifikacija 'insertion sort'-a nego 'bubble sort'-a).

Drugim rečima, unutrašnja petlja 'bubble sorta', koja je zadužena za zamenu mesta, je modifikovana na taj način da se razlika između zamenjenih elemenata spušta (za svako ponavljanje spoljašnje petlje) po koracima skupljajućeg faktora, tj.[ umetnuta veličina / skupljajućeg faktor, umetnuta veličina / skupljajućeg faktor^2, umetnuta veličina / skupljajućeg faktor^3, .....,1]. U 'bubble sortu' je, sa druge strane, razlika uvek konstantna, tj. 1.

Razlika između elemenata se prvo javlja kao dužina liste, sortirano podeljena pomoću skupljajućeg faktora (generalno 1.3; pogledaj dole), i lista je sortirana pomoću te vrednosti (zaokružena na celi broj ako je potrebno) kao da je ona razlika. Potom se razlika (između elemenata) ponovo deli na skupljajućeg faktore, lista se sortira u odnosu na ovu novu razliku, i proces se ponavlja dok razlika ne bude 1. Kada se to desi, 'comb sort' nastavlja da koristi razliku vrednosti 1 dok kompletno ne sortira listu. Poslednja faza raspoređivanja je dakle ekvivalentna 'bubble sortu', i dosad je problem 'turtleova' već uglavnom rešen, tako da će 'bubble sort' biti efikasan.

Skupljajući faktor ima veliki uticaj na efikasnost 'comb sorta'. U originalnom članku, autor je predložio vrednost od 4/3 (četiri trećine). Premala vrednost usporava algoritam zato što je potrebno da se napravi više poređenja, dok prevelika vrednost znači da nikakva poređenja neće ni biti napravljena. Lacey i Box su iskustvom (testirajući 'comb-sort' na preko 200,000 nasumično odabranih lista) došli do zaključka da je skupljajući faktor velicine 1.3 najbolji.

Implementacija

Pseudokod

   function combsort(array input)
    gap := input.size //inicijalizovati gap 
    shrink := 1.3 //podesite gap skupljajućek faktora

    loop until gap = 1 and swapped = false
        //podesite gap za sledeći comb. Ispod je primer
        gap := int(gap / shrink)
        if gap < 1
          //minimalna razlika je 1
          gap := 1
        end if
        

        i := 0
        swapped := false 
        

        //jedan "comb" preko ulazne liste
        loop until i + gap >= input.size //pogledajte shellsort za slične ideje
            if input[i] > input[i+gap]
                swap(input[i], input[i+gap])
                swapped := true 
                                 
            end if
            i := i + 1
        end loop
       

    end loop
end function

C

void comb_sort(int *input, size_t size) {
    const float shrink = 1.3f;
    int swap;
    size_t i, gap = size;
    bool swapped = false;

    while ((gap > 1) || swapped) {
        if (gap > 1) {
            gap = (size_t)((float)gap / shrink);
        }

        swapped = false;

        for (i = 0; gap + i < size; ++i) {
            if (input[i] - input[i + gap] > 0) {
                swap = input[i];
                input[i] = input[i + gap];
                input[i + gap] = swap;
                swapped = true;
            }
        }
    }
}

Pogledajte takođe

• Bubble sort, generalno sporiji algoritam, je osnova comb sort.
• Cocktail sort, ili dvosmerni bubble sort, je varijenta bubble sort koji takođe govori o problemu 'turtleova', mada manje efikasno.