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 (nlogn) aðgerðir til að raða n stökum í fylki.

 Virkni reiknirits 

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

 Valið 1 stak, svokallað skiptistak (e. pivot)
 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.
 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 




  (bls. 338 – 346, kafli 12: Faster Sorting Methods)

Flokkur:Röðunarreiknirit

no:Sorteringsalgoritme#Quick sort