Skeljaröðun

Skeljaröðun reiknirit lit bars

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²) samanburður en eftir smávægilega breytingu sem kemur bók V. Pratts endurbætti röðunina í O(n log² 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²) 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(n²) í versta tilfelli.

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:

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

  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