Snarröðun

Snarröðun (e. quicksort) er einfalt röðunarreiknirit sem var hannað af C.A.R. Hoare[1]^{[óvirkur tengill]}. Snarröðun er svokallað deili- og drottnunarreiknirit (e. divide and conquer algorithm), sem oftast þarf $\Theta$(nlogn) aðgerðir til að raða n stökum í fylki.

Hreyfimynd sem sýnir hvernig Quicksort-reikniritið virkar.

Virkni reiknirits

Snarröðun þarf $\Theta$(nlogn) aðgerðir í besta tilfelli til að klára að raða öllum stökum í fylki, í versta tilfelli þarf reiknirit hins vegar $\Theta (n^{2})$ 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:

1. Valið 1 stak, svokallað skiptistak (e. pivot)
2. Fylki endurraðað þannig að öll stök sem eru hærri en skiptistakið lenda fyrir ofan það, öll stök sem eru minni lenda fyrir neðan skiptistak. Öll stök sem eru jöfn skiptistaki lenda fyrir ofan eða neðan.
3. Síðan er endurkvæmni notuð til að raða báðum undirfylkjunum.

Reikniritið er mun hraðvirkara en önnur Θ(nlogn) 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 < pivot then append x to less
         if x = pivot then append x to equal
         if x > 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 < 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>=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<=j)
        {
            if (a[i]<=p) i++;
            else if (a[j]>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;
    }
}

Heimildir

• „Java applet og enskur texti um virkni snarröðun (e. quicksort)“. Sótt 21. mars 2008.
• „Javascript sem sýnir bæði kóða og virkni“. Sótt 21. mars 2008.
• „Vísindavefurinn: Hvernig er stærðfræðileg skýring á quicksort algoritmanum“. Sótt 21. mars 2008.
• Fyrirmynd greinarinnar var „Quick sort“ á ensku útgáfu Wikipedia. Sótt 22. mars 2008.
• Frank M. Carrano (2007). Data Structures and Abstractions with Java, 2. útgáfa. Pearson Education Inc. ISBN 0-13-237045-X. (bls. 338 – 346, kafli 12: Faster Sorting Methods)