„Röðunarreiknirit“: Munur á milli breytinga

Efni eytt Efni bætt við
→‎Bóluröðun: smátiltekt
Lína 277:
 
===Snarröðun ===
'''[[Snarröðun]]''' (e. ''quicksort'') er svokallað [[deili- og drottnunarreiknirit]] (e. divide and conquer algorithm), það sem húnþað brýtur verkefnið niður í sífellt smærri parta, allt þar til verkefnin verða svo smá í sniðum að auðvelt er að leysa þau. Til að raða [[fylki]] skiptir snarröðun því í tvo hluta með sérstakri [[aðgreiningaraðferð]] (e. partition operation).
 
Til að skipta fylki er valið svokallað [[skiptistak]] (e. pivot). Öll stök sem eru minni en skiptistakið eru sett framan við það, og öll stök sem eru stærri en skiptistakið eru sett aftan við það. Skiptistakið er þá komið á sinn rétta stað í fylkinu. Síðan er [[endurkvæmni]] notuð til að raða þessum tveimur undirfylkjum með nákvæmlega sömu aðferð. Þetta er endurtekið allt þar til undirfylkin eru orðin svo lítil að þau innihalda aðeins eitt stak. Að sjálfsögðu má þá líta á þau sem röðuð.