Skeljaröðun

**Skeljaröðun** (e. Shellsort, eftir höfundinum) er röðunaraðferð sem er afbrigði af innsetningarröðun, með eftirfarandi hluti til hliðsjónar:
* Innsetningarröðun er afkastamikil ef intakið er „nánast raðað“ og
* Innsetningarröðun er yfirleit dýr aðgerð þar sem innsetningarröðun færir aðeins eitt gildi í einu.

## Saga
Skeljaröðun er nefnd eftir Donald Shell sem bjó hana til árið 1959. Sumar eldri kennslubækur kala Skeljaröðun „Shell-Metzner“ röðun eftir Marlene Metzner Norton, en samkvæmt Metzner segist hann ekkert hafa komið nálægt henni og nafn hanns ætti ekki að vera bendlað við hana.

## Útfærsla
Upprunalega útfærslan er O(*n*2) samanburður en eftir smávægilega breytingu sem kemur bók V. Pratts endurbætti röðunina í O(*n* log2 *n*). Þetta er samt sem áður vera en eðlileg sameiningarröðuns, sem er O(*n* log *n*).

Skeljaröðun bætir innsetningarröðun með því að bera saman tvö tilvik sem eru aðskilin með bili upp á nokkrar staðsetningar. Þetta gerir það að verkum að tilvikið tekur „stærri skref“ í röðun. Margar ferðir yfir gögnin eru teknar með minni og minni bilum í staðsetningarstærð. Síðasta skrefið í skeljaröðun er bara venjuleg innsetningarröðun, en þegar komið er á það stig er nánast búið að full tryggja að gögnin eru „nánast röðuð“.

Tökum sem dæmi látt gildi sem er upphaflega raðað á röngum enda á fylki. Með því að nota O(*n*2) röðun eins og bóluröðun eða innsetningarröðun, þá mun það taka gróflega *n* samanburði og skiptingar til að færa gildið all leið á hin endan á fylkinu. Skeljaröðun byrjar á því að færa gildið í stóru skrefi svo að lágt gildi muni færast langleiðina á áætlunarstað, með aðeins fáum samanburðum og skiptingum.

Hægt er að sjá fyrir sér skeljaröðun á eftirfarandi hátt: raða listanum upp í töflu og sortera dálkana (með innsetningarröðun). Endurtaka ferlið hvert skipti með færi langa dálka. Í lokin hefur taflan aðeins einn dálk. Þegar verið er að framkvæma skerfa stærð, t.d. með `i += skref_staerd` í stað `i++`).

Til dæmis, skoðum eftir farandi lista af tölum `[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]`.Ef við byrjum með skref_staerd 5, þá gætum við séð þetta fyrir okkur sem töflu með fimm dálkum, sem myndi líta svona út:


```
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
```


Svo röðum við dálkunum, sem gefur okkur


```
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
```


þegar lesið er sem einn röð af númerum fáum við `[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]`. Hérna er 10 sem var á hinum endanum komið á byrjun. þessi listi er síðan aftur raðaður með skref_staerd 3 og síðan með skref_staerd 1.

## Skeljaröðun í C/C++
Eftir farandi útfærsla af skeljaröðun er skrifuð í C/C++ til að raða fylki af heiltölum. þessu útfærsla gefur O(n2) í versta tilfelli.


```c
void shell_sort(int A[], int size) {
  int i, j, increment, temp;
  increment = size / 2;
      
  while (increment > 0) {
    for (i = increment; i < size; i++) {
      j = i;
      temp = A[i];
      while ((j >= increment) && (A[j-increment] > temp)) {
        A[j] = A[j - increment];
        j = j - increment;
      }
      A[j] = temp;
    }
    
    if (increment == 2)
       increment = 1;
    else 
       increment = (int) (increment / 2.2);
  }
}
```


## Skeljaröðun í Java
Java útfærsla af skeljaröðun:

```java
public static void shellSort(int[] a) {
    for (int increment = a.length / 2; increment > 0;
          increment = (increment == 2 ? 1 : (int) Math.round(increment / 2.2))) {
        for (int i = increment; i < a.length; i++) {
            int temp = a[i];
            for (int j = i; j >= increment && a[j - increment] > temp; j -= increment){
                a[j] = a[j - increment];
                a[j - increment] = temp;
            }
        }
    }
}
```


## Skeljaröðun í Python

```python
def shellsort(a):
      def increment_generator(a):
          h = len(a)
          while h != 1:
              if h == 2:
                  h = 1
              else: 
                  h = 5*h//11
              yield h

      for increment in increment_generator(a):
          for i in xrange(increment, len(a)):
              for j in xrange(i, increment-1, -increment):
                  if a[j - increment] < a[j]:
                      break
                  a[j], a[j - increment] = a[j - increment], a[j]
      return a
```


## Heimildir