Urejanje Shell sort

Iz MaFiRaWiki

Vsebina


Urejanje z vstavljanjem s padajočim prirastkom ali Shell sort je algoritem za urejanje podatkov v tabeli, in sicer izboljšana različica urejanja z vstavljanjem. Prvi ga je leta 1959 uporabil Donald Shell. Ideja algoritma je enostavna: množico elementov posebej sortiramo po skupinah, pri čemer v isto skupino spadajo elementi, ki so določeno število mest narazen.

Sam algoritem ne ureja podatkov samostojno, ampak si pomaga z drugimi algoritmi, najpogosteje z navadnim vstavljanjem. Izboljšan je tako, da pri urejanju ne primerja vseh elementov po vrsti, ampak v začetku ureja na "daleč", torej z večjimi koraki (prirastki). Takemu urejanju rečemo k - urejanje. S pravilno izbiro korakov najprej ločeno uredimo elemente, ki so med seboj oddaljeni k - korakov, potem zmanjšamo korak in urejamo te elemente … nazadnje urejamo s korakom 1. Zadnjemu koraku rečemo 1 - urejanje in predstavlja kar navadno vstavljanje. Je pomemben, ker na ta način dosežemo, da so vsi elementi pravilno urejeni.

Algoritem je zanimiv zgolj zaradi tega, ker poveča učinkovitost drugih algoritmov. Z grupiranjem podatkov se na nek način zmanjša čas, ki bi bil drugače potreben pri procesu urejanja podatkov. Največ menjav opravimo na začetku, kasneje so skupine večinoma urejene in je potrebno le manjše število korakov. Je tudi prvi algoritem, ki je dosegel časovno zahtevnost boljšo od (n2), vendar se v praksi redko uporablja. Časovna zahtevnost je v najbolšem primeru O(n1.2).

Zdi se, da imamo z več skupinami, v katerih moramo urediti vse elemente, več dela. Vendar pa je v vsaki skupini majhno število elementov ali pa so že kar dobro urejeni, zato ni potrebno veliko število korakov. Nazadnje uporabimo navadno vstavljanje, ki v najslabšem primeru postori celotno delo in nas pripelje do urejene tabele. Izboljšanje je v tem, da vsaka predhodno urejena skupina koristi naslednji, saj vsako i-urejanje združuje dve skupini, ki sta že urejeni glede predhodno urejanje. Uporabimo lahko poljubno zaporedje prirastkov, seveda s pogojem, da je zadnji prirastek enak 1.

Algoritem

Izboljšan algoritem navadnega vstavljanja:

  • določimo prirastek (korak) velikosti k, ki je manjši od števila vseh elementov in večji od 1
  • začetno množico elementov grupiramo v k skupin, kjer vsaka vsebuje elemente, ki so k - korakov oddaljeni med seboj
  • v vsaki skupini posebej uredimo elemente, uporabimo postopek navadnega vstavljanja
  • korake postopoma zmanjšujemo; zadnji korak mora biti enak 1

Namen izboljšave je v tem, da bi skupine elementov težile k vse večji urejenosti še pred končnim korakom z vrednostjo 1.

Algoritem v psevdokodi pri čemer je:

  • A ...... začetna neurejena tabela dolžine n
  • a[i] ... element v tabeli A, kjer je 0<=i<=n
  • T ...... število faz, ki so odvisne od števila elementov v tabeli
  • k ...... korak oziroma prirastek
SHELLSORT (tab A)
for(int m=0; m < T; ++m) // ponavljaj, dokler ne izvršiš vseh faz, število faz m je odvisno od števila elementov
   določi korak k za to fazo
for(int i=k; i<a.length; ++i) 
   x:=a[i]
   vstavi x s postopkom navadnega vstavljanja na pravo mesto, upoštevajoč korak

Algoritma vstavljanja s padajočim prirastkom ne moremo natančno analizirati, saj naletimo na več izredno težkih matematičnih problemov, ki so do danes ostali nerešeni. Tako na primer še ne poznamo optimalne izbire prirastkov. Vendar pa vemo, da ne smejo biti mnogokratniki eden drugega. Kajti če so prirastki mnogokratniki eden drugega, potem vsaka etapa sortiranja združuje dve skupini, ki se pred tem nista medsebojno prepletali. Mi pa si seveda želimo, da se skupine čim pogosteje prepletajo med seboj.

Izbira korakov delitve je pomembna za ustrezno obnašanje algoritma. Velja, da naj bodo koraki izbrani tako, da omogočajo čim boljše prepletanje skupin, kar pomeni, da so elementi, ki so bili v isti množici prej, tudi ob naslednjem koraku v isti množici. Vzamemo lahko poljubno delilno zaporedje, pomembno je le, da koraki niso večkratniki naslednjih korakov, drugače je urejanje neučinkovito. Primer slabe izbire korakov: [18, 9, 6, 3, 1].

Za učinkoviti sta se izkazali dve izbiri zaporedja prirastkov.

  • Prvo zaporedje prirastkov (zapisano v nasprotnem vrstnem redu): [1, 4, 13, 40, 121, ...] pri čemer je km-1=3*km+1, kT=1 in T=|log3n|-1.
  • Prav tako je priporočljivo za prirastke vzeti zaporedje: [1, 3, 7, 15, 31, ...] pri km-1=2*km+1, kT=1 in T=log2n - 1.

Matematična analiza pokaže, da je pri tej izbiri parametrov obseg računanja za sortiranje n elementov z algoritmom Shellsort sorazmeren O (n1,2), kar je precejšne izboljšanje v primerjavi z O (n2).

Število faz izračunamo iz velikosti tabele. Izračun števila korakov za n = 1024 elementov.

N=1024, T=log21024-1, torej je število faz T=9 in je delilno zaporedje: [511, 255, 127, 63, 31, 15, 7, 3, 1].

Primer

Shellsort premika elemente na daleč. V isti skupini so elementi urejeni. Elementi težijo k vedno večji urejenosti (premiki so vse manjši).

Uredimo tabelo z metodo Shell sort, kjer uporabimo delilno zaporedje [1,3,5].

25 12 32 10 82 19 13 6 3 67 15 43

Najprej sortiramo skupino elementov, ki so za pet mest narazen, postopku rečemo 5-urejanje. V primeru dvanajstih elementov imamo 5 skupin z 3 ali 2 elementi, ki so za 5 mest narazen. Nato zmanjšamo korak na 3 in vzamemo elemente, ki so za tri mesta narazen, čemur rečemo 3-urejanje. V primeru dvanajstih elementov torej imamo 3 skupine s 4 elementi, ki so za 3 mesta narazen. V zadnji etapi pa vedno uporabimo navadno vstavljanje, ki mu rečemo 1-urejanje.

1. faza: 5 - urejanje

Za lažjo ponazoritev prepišemo tabelo v pet stolpcev, kjer vsak predstavlja skupino za 5 med sabo oddaljenih elementov.

25  12  32  10  82   uredimo elemente v stolpcih 	15  12   6   3  67
19  13   6   3  67			                19  13  32  10  82
15  43					                25  43

Najprej ločeno uredimo vse elemente, ki so med seboj oddaljeni za pet mest. Tako urejamo med seboj prvi, šesti, enajsti element; nato drugega, sedmega in dvanajstega; nato tretjega in osmega; nato četrtega in devetega in na koncu petega in desetega. Po zaključeni fazi dobimo tabelo:

15 12 6 3 67 19 13 32 10 82 25 43

2. faza: 3 - urejanje

Za lažjo ponazoritev prepišemo tabelo v tri stolpce, kjer vsak predstavlja skupino za 3 med sabo oddaljene elemente.

15  12   6    uredimo elemente v stolpcih 	 3  12   6  
 3  67  19				        13  25  10
13  32  10           			        15  32  19
82  25  43				        82  67  43

Ločeno uredimo vse elemente, ki so med seboj oddaljeni za tri mesta: najprej urejamo med seboj prvi, četrti, sedmi in deseti element; nato med seboj drugi, peti, osmi in enajsti; nato med seboj tretji, šesti, deveti in dvanajsti. Dobimo tabelo:

3 12 6 13 25 10 15 32 19 82 67 43

3. faza: 1 - urejanje

Na koncu primerjamo s korakom 1, torej po dve števili med seboj. Postopek je kar navadno vstavljanje. Vsi elementi pred koncem so že skoraj na pravem mestu. Dobimo urejeno tabelo:

3 6 12 10 13 15 19 25 32 43 67 82

Implementacija

Glej tudi

Viri

Osebna orodja