Algoritem Comb sort je algoritem, ki se uporablja za urejanje podatkov. V samem algoritmu gre za zamenjave in primerjanja podatkov - kot v večini urejevalnih algoritmov. Algoritem je podoben algoritmu Bubble sort (Urejanje z mehurčki) oziroma je nadgradnja ali izboljšana različica omenjenega programa.

Urejanje z mehurčki ali Bubble sort

Da bomo kasneje lažje razumeli urejanje Comb sort, na hitro preletimo osnove urejanja z mehurčki. Poglejmo si delovanje algoritma kar na konkretnem primeru. Imejmo neurejeno tabelo naključnih števil, ki bi jo radi uredili, tako da bodo števila v tabeli razvrščena po velikosti. Najmanjše število bo na prvem mestu, največje na zadnjem – na koncu tabele. Opazujmo le, kaj se dogaja s števili.

primer: Imejmo tabelo števil:

Zgrabimo prva dva elementa in ju primerjamo. V kolikor je prvi večji od drugega ju zamenjamo. Ker je 33 manjši od 98, zamenjava ni potrebna.

Nato zgrabimo drugega in tretjega, torej števili 98 in 74 in jih primerjamo.

Ker je število z manjšim indeksom večje od števila z večjim indeksom, števili zamenjamo.

Nato zgrabimo tretje in četrto število, torej števili 98 in 13 in ju primerjamo.

Ker je 13 manjše od 98, števili zamenjamo.

Tako nadaljujemo do konca, torej, dokler ne primerjamo zadnji dve števili v tabeli. Nato se vrnemo na začetek tabele in zopet primerjamo prvi in drugi podatek. Večkrat se sprehodimo skozi celotno tabelo. Najmanjši element tako splava na začetek tabele, največji pa na konec. Velika števila se zelo hitro pomaknejo na konec tabele, lahko že ob prvem prehodu čez tabelo. Majhna števila pa splavajo na začetek tabele zelo počasi. V najslabšem primeru v zadnjem koraku, torej čisto na koncu. Potrebujemo kar precej sprehodov čez celotno tabelo, preden so elementi urejeni po velikosti. Urejanje je končano, ko pri prehodu čez celo tabelo ni potrebna nobena zamenjava.

Algoritem urejanja s česanjem se je razvil ravno z namenom izboljšanja algoritma urejanja z mehurčki (Bubble sort) in sicer z vpeljavo tako imenovane metode ubijanja želve. Želva namreč poimenujemo majhna števila, ki se pojavljajo na koncu tabele. Pri ubijanju želve gre za to, da ta majhna števila na koncu tabele ravno s pomočjo te omenjene metode precej hitreje priplavajo na začetek tabele. Med tem, ko pri urejanju z mehurčki vedno primerjamo dve sosednji števili, pri urejanju s česanjem primerjamo nesosednja števila. Takšna primerjanja optimizirajo algoritem.

Osnovni princip urejanja s česanjem

Princip urejanja s česanjem si bomo ogledali na konkretnem primeru, a še prej si poglejmo nekaj osnovnih pojmov, ki jih uporabljamo v tem algoritmu. Tako bomo tudi lažje razumeli princip urejanja.

• podatki: lahko so to števila, lahko pa tudi različni predmeti, ki jih lahko primerjamo oziroma urejamo. V prvem primeru bomo imeli neurejeno tabelo števil.
• N– število elementov
• želva– s tem imenom označujemo majhna števila, ki se pojavljajo na koncu tabele. Pri urejanju z mehurčki ta števila zelo počasi priplavajo na vrh tabele (začetek) in od tod ime želve - ker potujejo počasi.
• zajec– s tem imenom označujemo velika števila, ki se pojavljajo na začetku tabele. Pri urejanju z mehurčki ta števila hitro priplavajo na konec tabele, od tod ime zajec.
• ubitiželvo – izraz, s katerim označimo hiter prehod želve na začetek tabele.
• vrzel– je praktično razlika med indeksoma dveh števil, ki ju trenutno primerjamo. Z angleškim izrazom jo imenujemo gap. To je pravzaprav razdalja med položajema dveh števil v tabeli.
• zožitveni faktor ali shrink factor - faktor, ki ga uporabimo v enačbi, oziroma s katerim zmanjšujemo vrzel.

Kako poteka urejanje s česanjem si poglejmo kar na primeru na naslednji prosojnici...

Vzemimo za primer tabelo naključnih števil, ki jih želimo urediti po velikosti.

Najprej začnemo z izračunom vrzeli, ki ima na začetku vrednost 10 / 1,3 – torej velikost tabele delimo z 1,3. Dobimo število 7, če zaokrožimo navzdol. Od kod dobimo faktor 1,3? Ja, načeloma bi lahko vzeli drugačen faktor, a izkaže se, da je to optimalen faktor, ki maksimalno optimizira delovanje algoritma – program izvede najmanj primerjanj števil. Nekaj podrobnosti o tem faktorju je razloženih v nadaljevanju.

Nadaljujemo torej s primerjanjem 1. števila in pa 1+7, torej 8. števila v tabeli.