Wikipedia

„Röðunarreiknirit“: Munur á milli breytinga

Fletta í gegnum breytingarskrá
← Eldri breytingNýrri breyting →
Efni eytt Efni bætt við
MyndræntWiki-texti
JhsBot (spjall | framlög)
6.535 breytingar
m robot Bæti við: hu:Rendezés (programozás)
m Leiðréttingar, Replaced: annara → annarra (AWB)
Lína 4:
Röðunarreiknirit eru flokkuð eftir:
 
* [[Tímaflækja|Tímaflækju]] samanburða. Þá skipta [[Versta tilfelli|versta]], [[meðaltilfelli|meðaltals-]] og [[besta tilfelli|besta]] tilfelli máli, en þau lýsa hlutfallslegum fjölda samanburða sem gera þarf á stökunum, miðað við stærð listans (''n''). Fyrir dæmigerð röðunarreiknirit er góð hegðun [[Stóra O|O]](''n''&nbsp;log&nbsp;''n''), og slæm hegðun er O(''n''<sup>2</sup>). Ákjósanlegasta hegðun er O(''n'').
* Tímaflækju víxlana. Víxlanir geta verið seinlegar í sumum tilfellum.
* [[Vinnsluminni|Minnisnotkun]] (og notkun annaraannarra auðlinda). Þá er sérstaklega athugað að sum reiknirit raða „á staðnum“, þannig að þau þurfa lítið aukalegt minni umfram það sem verið er að nota undir listann sem verið er að raða, meðan önnur taka frá aukalegt minni fyrir gögnin þar sem að þau eru geymd tímabundið.
* [[Stöðugleiki röðunarreiknirita|Stöðugleika]]. Röðunarreiknirit kallast ''stöðugt'' ef að það varðveitir afstæða röðun gagna með sams konar lykla.
* Hvort að þau nota samanburðarröðun eða ekki. Samanburðarröðun ber saman gögnin eingöngu með samsemdarvirkja (ekki [[hlutröðunarvensl|hlutröðun]]).
Lína 14:
Í þessari töflu er ''n'' fjöldi færslna sem á að raða og ''k'' er fjöldi aðgreinanlegra færslna (þ.e., eftir að endurteknar færslur hafa verið fjarlægðar). Dálkarnir „best“, „meðaltal“ og „verst“ gefa tímaflækju hverju sinni. Þar sem að ''k'' er ekki notað er álitið að ''k'' sé fasti. „Minni“ gefur til kynna hversu mikið aukalegt minni þarf umfram það sem listinn tekur.
 
<!-- I use &middot;·s below to try to keep the column contents from wrapping in an undesirable way while still adjusting to different font sizes. -->
{|class="wikitable"
!Nafn !! Best !! Meðaltal !! Verst !! Minni !! Stöðugt !! Aðferð !! Athugasemdir
Lína 284:
 
===Hrúguröðun ===
'''[[Hrúguröðun]]''' (e. ''heapsort'') er eins konar [[valröðun]]. Þessi röðun ákvarðar stæsta (eða minnsta) stak og raðar því aftast (eða fremst) í lista. Önnur stök fylgja síðan þessu valda staki. [[Valröðun]] keyrir á O(n^2) hraða en [[hrúguröðun]] vinnur mun hraðar með því að nota [[gagnagrind]] sem kallast [[hrúga (tölvunarfræði) | hrúga]] sem er [[tvíundartré]] þar sem [[foreldri (tölvunarfræði) | foreldri]] er ávallt stærra en [[börn (tölvunarfræði) | börnin]].
 
Þegar gögn hafa verið gerð að [[hrúga (tölvunarfræði) | hrúgu]] þá er rótin í [[tré (tölvunarfræði) | trénu]] ávallt stærsta (eða minnsta) stakið af öllum.
 
===Innsetningarröðun===
Lína 304:
'''[[Valröðun]]''' (e. ''selection sort'') virkar þannig að fundið er minnsta stakið í lista (eða stærsta, allt eftir því hvort raða á frá minnsta til stærsta, eða frá stærsta til minnsta). Síðan er skipt á því og fyrsta staki listans. Þetta er svo endurtekið fyrir afganginn af listanum (fremsta stakinu, sem nú er raðað, er sleppt).
 
[[Hrúguröðun]] (sjá fyrir ofan) bætir valröðun umtalsvert með því að nota [[hrúga (tölvunarfræði)|hrúgu]] sem [[gagnagrind]]. Þannig verður auðveldara að finna og fjarlægja minnsta (eða stærsta) stakið.
 
[[Flokkur:Röðunarreiknirit|Röðunarreiknirit]]
 
Sótt frá „https://is.wikipedia.org/wiki/Röðunarreiknirit“