Snarröðun

Snarröðun (e. quicksort) er einfalt röðunarreiknirit sem var hannað af C.A.R. Hoare. Snarröðun er svokallað deili- og drottnunarreiknirit (e. divide and conquer algorithm), sem oftast þarf formula_1("n"log"n") aðgerðir til að raða "n" stökum í fylki.

Virkni reiknirits.

Snarröðun þarf formula_1("n"log"n") aðgerðir í besta tilfelli til að klára að raða öllum stökum í fylki, í versta tilfelli þarf reiknirit hins vegar formula_3 aðgerðir til að raða stökum í fylki. Vinnsla í reikniritinu fer þannig fram að fylkinu er skipt upp í 2 minni fylki.

Skrefin eru:

Reikniritið er mun hraðvirkara en önnur Θ("n"log"n") samanburðar reiknirit, en hins vegar telst það ekki stöðugt. Helsti gallinn við reikniritið er eftir sem því fylkið er stærra, þarf meira minni til að raða stökunum sem eru í fylkinu. Þetta er hægt að forðast með því að nota svokallaða á-staðnum (e. in-place) aðferð.

Þegar að á-staðnum aðferðin er notuð, þá er vinnan við reikniritið svipuð og áður. Eftir að skiptistakið er fundið, er það sett tímabundið aftast ef þess þarf. Síðan eru öll lægri stök flutt í byrjun á undirfylkinu (e. sub-array), þannig að öll hærri stök lenda á eftir þeim. Að lokum er fundinn staðsetning fyrir skiptistakið og það er flutt á sinn stað. Hafa ber í huga að útkomann inniheldur sömu stök eins og þegar var byrjað, einnig getur sama stak verið víxlað oft áður en það kemst á endanlega staðsetningu.

Sauðakóði fyrir snarröðun.

Einfaldur sauðakóði (e. pseudocode) fyrir reikniritið:

function quicksort(array)

var "list" less, equal, greater

if length(array) ≤ 1

return array

select a pivot value "pivot" from array

for each x in array

if x &lt; pivot then append x to less

if x = pivot then append x to equal

if x &gt; pivot then append x to greater

return concatenate(quicksort(less), equal, quicksort(greater))

Sauðakóði sem notast við á-staðnum (e. in-place) aðferð:

function partition(array, left, right, pivotIndex)

pivotValue := array[pivotIndex]

swap array[pivotIndex] and array[right] "// Move pivot to end"

storeIndex := left

for i from left to right "// left ≤ i &lt; right"

if array[i] ≤ pivotValue

swap array[i] and array[storeIndex]

storeIndex := storeIndex + 1

swap array[storeIndex] and array[right] "// Move pivot to its final place"

return storeIndex

Java kóði fyrir snarröðun.

public class QuickSort

public static void quicksort (int[] a)

quicksort(a, 0, a.length-1);

private static void quicksort (int[] a, int l, int r)

//grunn dæmi: fylkið er tómt

if (l&gt;=r) return;

//endurkvæmni: skipti fylki og raða með endurkvæmni

int m = partition(a, l, r);

quicksort(a,l,m-1);

quicksort(a,m+1,r);

//Skipti fylki í l+1 til r með skiptistak a[l]

private static int partition (int[] a, int l, int r)

int i=l+1; //bendir fyrir lægri stök

int j=r; //bendir fyrir hærri stök

int p = a[l]; //skiptistak

//færi bendir til miðju eða víxla ef hann er röngum meginn

while (i&lt;=j)

if (a[i]&lt;=p) i++;

else if (a[j]&gt;p) j--;

else swap(a,i,j);

//færi skiptistakið og sett það á miðju

swap(a,l,j);

//skila stöðu skiptistaks

return j;

//Víxla 2 stökum í fylki

private static void swap (int[] a, int i, int j)

int h = a[i]; a[i] = a[j]; a[j] = h;