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:

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ð codice_1 í stað codice_2).

Til dæmis, skoðum eftir farandi lista af tölum codice_3.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:

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

þegar lesið er sem einn röð af númerum fáum við codice_4. 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.

void shell_sort(int A[], int size) {

int i, j, increment, temp;

increment = size / 2;

while (increment &gt; 0) {

for (i = increment; i &lt; size; i++) {

j = i;

temp = A[i];

while ((j &gt;= increment) &amp;&amp; (A[j-increment] &gt; 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 &gt; 0;

increment = (increment == 2 ? 1 : (int) Math.round(increment / 2.2))) {

for (int i = increment; i &lt; a.length; i++) {

int temp = a[i];

for (int j = i; j &gt;= increment &amp;&amp; a[j - increment] &gt; 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] &lt; a[j]:

break

a[j], a[j - increment] = a[j - increment], a[j]

return a