Comb sort - urejanje s česanjem

Comb sort - urejanje s česanjem

Avtor: Tomaž Kušar

Urejanje s česanjem in urejanje z mehurčki

Kaj je urejanje s česanjem? 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.

Kaj pa je urejanje z mehurčki? 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 naslednjo tabelo števil.

(http://www2.nauk.si/files/128/tabela1.PNG)
Primer urejanja z mehurčki - Bubble sort

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.

Kaj je prednost urejanja s česanjem?

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.
(http://www2.nauk.si/files/128/glavnik_s.jpg)
Urejanje s česanjem....

Primer urejanja

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

[33 | 98 | 74 | 13 | 55 | 20 | 77 | 45 | 64 | 83 ]

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.

[ 33 | 98 | 74 | 13 | 55 | 20 | 77 | 45 | 64 | 83 ]

Ker je 33 manjše od 45, zamenjava ni potrebna. Števili zamenjamo v primeru, da je število z manjšim indeksom večje od števila z večjim indeksom. Torej, ker sta števili v pravem zaporedju, nadaljujemo - premaknemo se za en korak naprej in primerjamo 2. in 9. število v tabeli.

[ 33 | 98 | 74 | 13 | 55 | 20 | 77 | 45 | 64 | 83 ]

Ja, 98 je večje od 64, zato števili zamenjamo. Število 64 bi lahko imenovali želva, saj bi v primeru urejanja z mehurčki, precej počasneje prišlo v ospredje. Torej, lahko bi rekli, da smo ubili želvo (želva je v tem primeru število 64).

[33 | 64 | 74 | 13 | 55 | 20 | 77 | 45 | 98 | 83 ]

Nadaljujemo s primerjanjem tretjega in desetega števila, torej zadnjega.

[ 33 | 64 | 74 | 13 | 55 | 20 | 77 | 45 | 98 | 83]

Zamenjava ni potrebna, saj je 74 pred 83, oziroma sta razporejeni v pravilnem vrstnem redu. Tako, prvič smo prišli na konec tabele in to je prvi krog izvajanja programa. Izvajanje programa moramo ponavljati vse dokler vrednost vrzeli ni enaka 1. Zato moramo izračunati novo vrednost vrzeli – 7 deliti z 1,3. Dobimo vrednost 5.

Tako, sedaj ponovno zaženemo metodo Comb sort, kjer primerjamo 1. in pa 6. (1+5) število. Torej primerjamo števili 33 in 20.

[ 33 | 64 | 74 | 13 | 55 | 20 | 77 | 45 | 98 | 83 ]

vrzel; na tem koraku je vrednost vrzeli enaka 5. Vrzel je razlika med ideksoma števil ki ju primerjamo.

0%
0%