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

## Virkni reiknirits

Snarröðun þarf \Theta(*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 \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:

# 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 Θ(*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  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

```java
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 &ndash; 346, kafli 12: *Faster Sorting Methods*)