Цомб сорт

"Цомб сорт" је релативно једноставан алгоритам за сортирање. Написао га је Włодзимиерз Добосиеwицз, 1980. Касније је поново откривен од стране Степхен Лацеy-а и Рицхард Боx-а, 1991. Цомб сорт је унапређени буббле сорт.

Алгоритам

Основна идеја је да се елиминишу "корњаче" (туртлес), тј. мале вредности близу краја листе, које су у буббле сорт-у значајно успоравале распоређивање. "Зечеви" (раббитс), велике вредности на почетку низа, нису представљале никакав проблем у буббле сорт-у.

Када се било која два елемента упореде у 'буббле сорт'-у разлика између њихових индекса је увек 1. Основна идеја цомб сорт-а је та да та разлика може да буде много већа од 1 ('схелл сорт' се такође базира на овој идеји, али он је чешће модификација 'инсертион сорт'-а него 'буббле сорт'-а).

Другим речима, унутрашња петља 'буббле сорта', која је задужена за замену места, је модификована на тај начин да се разлика између замењених елемената спушта (за свако понављање спољашње петље) по корацима скупљајућег фактора, тј.[ уметнута величина / скупљајућег фактор, уметнута величина / скупљајућег фактор^2, уметнута величина / скупљајућег фактор^3, .....,1]. У 'буббле сорту' је, са друге стране, разлика увек константна, тј. 1.

Разлика између елемената се прво јавља као дужина листе, сортирано подељена помоћу скупљајућег фактора (генерално 1.3; погледај доле), и листа је сортирана помоћу те вредности (заокружена на цели број ако је потребно) као да је она разлика. Потом се разлика (између елемената) поново дели на скупљајућег факторе, листа се сортира у односу на ову нову разлику, и процес се понавља док разлика не буде 1. Када се то деси, 'цомб сорт' наставља да користи разлику вредности 1 док комплетно не сортира листу. Последња фаза распоређивања је дакле еквивалентна 'буббле сорту', и досад је проблем 'туртлеова' већ углавном решен, тако да ће 'буббле сорт' бити ефикасан.

Скупљајући фактор има велики утицај на ефикасност 'цомб сорта'. У оригиналном чланку, аутор је предложио вредност од 4/3 (четири трећине). Премала вредност успорава алгоритам зато што је потребно да се направи више поређења, док превелика вредност значи да никаква поређења неће ни бити направљена. Лацеy и Боx су искуством (тестирајући 'цомб-сорт' на преко 200,000 насумично одабраних листа) дошли до закључка да је скупљајући фактор велицине 1.3 најбољи.

Имплементација

Псеудокод

   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;
            }
        }
    }
}

Погледајте такође

• Буббле сорт, генерално спорији алгоритам, је основа цомб сорт.
• Цоцктаил сорт, или двосмерни буббле сорт, је варијента буббле сорт који такође говори о проблему 'туртлеова', мада мање ефикасно.