Rešitev: hitro urejanje (Mathematica)

Iz MaFiRaWiki

Naloga: hitro urejanje


Vsebina

Program hitroUrejanje


In[143]:= Clear[HitroUrejanje]
HitroUrejanje[list_] :=  Block[{list2,pivot,pivotindex}, If[Length[list] > 1, \
 (pivotindex = Random[Integer,{1,Length[list]}];  pivot = 
      list[[pivotindex]]; list2 = Delete[
          list,pivotindex]; Join[HitroUrejanje[
            Select[list2, # < pivot &]],  
              List[pivot],  HitroUrejanje[Select[list2, # >= pivot &]]]),   \
list]]; 

In[145]:=Clear[l]
l=Table[Random[Integer,{1,10}],{i,1,10}]
HitroUrejanje[l]

Out[146]={9,5,10,6,9,2,7,4,3,1}

Out[147]={1,2,3,4,5,6,7,9,9,10}

Opazimo, da pri tem algoritmu porabimo veliko več prostora kot bi bilo morda potrebno. Zato preoblikujemo algoritem tako, da namesto da ustvarjamo nove sezname, menjamo elemente na seznamu, ki ga urejamo.

Clear[hitroUrejanje,deli]

deli[l_List,pivot_Integer,v_Integer,r_Integer]/;v<pivot:={Take[l,pivot-1],Drop[l,pivot-1]}<br/>
deli[l_List,pivot_Integer,v_Integer,r_Integer]/;l[[pivot]]>r:=deli[l,pivot+1,v,r]<br/>
deli[l_List,pivot_Integer,v_Integer,r_Integer]/;l[[v]]<r:=deli[l,pivot,v-1,r]<br/>
deli[l_List,pivot_Integer,v_Integer,r_Integer]:=deli[ReplacePart[l,l,{{pivot},{v}},{{v},{pivot}}],pivot+1,v-1,r]<br/>

hitroUrejanje[l_List]/;Length[l]≤1:=l<br/>
hitroUrejanje[l_List]:=Module[{x,a,b,d,t,r},<br/>
:d=Length[l];<br/>
:t=Random[Integer,{1,d}];<br/>
:r=l[[t]];<br/>
:x=deli[l,1,d,r];<br/>
:a=x[[1]];<br/>
:b=x[[2]];<br/>
:Join[hitroUrejanje[a],hitroUrejanje[b]]<br/>
]

Kljub temu, da je algoritem za hitro urejanje med najbolj učinkoviti algoritmi se zelo slabo izkaže pri urejanju skoraj urejene tabele. Njegova povprečna časovna zahtevnost je O(n \cdot \log(n)), vendar pa se lahko zgodi da teče tudi v O(n2). Da bi omejili najslabši čas delamo hibridni algoritem, pri čemer združimo algoritem za hitro urejanje in urejanje s kopico (Heapsort), ki ima najslabšo časovno zahtevnost O(n \cdot \log(n)).

Tu je zgled preprostejšega hibridnega algoritma za hitro urejanje, pri čemer preklopimo na Insertion sort(urejanje z vstavljanjem).

Program hitroUrejanje, ki ustavi rekurzijo pri velikosti podproblema 50

Clear[hitroUrejanje50]

deli[l_List,pivot_Integer,v_Integer,r_Integer]/;v<pivot:={Take[l,pivot-1],Drop[l,pivot-1]}<br/>
deli[l_List,pivot_Integer,v_Integer,r_Integer]/;l[[pivot]]>r:=deli[l,pivot+1,v,r]<br/>
deli[l_List,pivot_Integer,v_Integer,r_Integer]/;l[[v]]<r:=deli[l,pivot,v-1,r]<br/>
deli[l_List,pivot_Integer,v_Integer,r_Integer]:=deli[ReplacePart[l,l,{{pivot},{v}},{{v},{pivot}}],pivot+1,v-1,r]<br/> 

hitroUrejanje50[l_List]/;Length[l]≤50:=Module[{b,j,t},<br/>
:b=l;<br/>
:For[i=1,i<=Length[b],i=i+1,<br/>
::j=i;<br/>
::t=b[[j]];<br/>
::While[(j>0)&&(b[[j-1]]<t),<br/>
:::b[[j]]=b[[j-1]];<br/>
:::j=j-1;<br/>
:::b[[j]]=t<br/>
::]

:];

:Return[b]

]


hitroUrejanje50[l_List]:=Module[{x,a,b,d,t,r},<br/>
:d=Length[l];<br/>
:t=Random[Integer,{1,d}];<br/>
:r=l[[t]];<br/>
:x=deli[l,1,d,r];<br/>
:a=x[[1]];<br/>
:b=x[[2]];<br/>
:Join[hitroUrejanje50[a],hitroUrejanje50[b]]<br/>
]


Časovna zahtevnost

Spodnja tabela prikazuje časovno zahtevnost postopka v odvisnosti od dolžine tabele in tega, kdaj končamo z rekurzijo:

dolžina tabele konec rekurzije čas
500 nikoli 0.062s
500 25 0.063s
500 50 0.063s
500 75 0.078s
500 100 0.11s
500 250 0.266s
3000 nikoli 0.172s
3000 25 0.609s
3000 50 0.484s
3000 75 0.078s
3000 100 0.531s
3000 250 0.484s

Iz tabele se vidi, da je pri velikih tabelah (dolžine cca. 3000) rekurzijo najbolje ustaviti pri velikosti podproblema okrog 75. Pri manjših tabelah (dolžine cca. 500) ni bistvenih razlik, če rekurzije ne ustavimo ali jo ustavimo nekje do velikosti podproblema 50, kasneje se jo pa splača ustaviti vedno manj.


Prikaz s tabelo

Radi bi uredili naslednjo tabelo.

8 3 5 2 11 4 1

Naključno izberemo delilni element.

8 3 5 2 11 4 1

Gremo po tabeli od roba proti sredini in uredimo tabelo tako, da se vsi elementi ki so večji od delilnega pojavijo na desni, vsi manjši pa na levi.

8 3 5 2 11 4 1

8 11 5 2 3 4 1

Nato rekurzivno uredimo obe podtabeli in dobimo:

11 8 5 4 3 2 1

Osebna orodja