ShellSort
Iz E-študij, proste zakladnice študentskega znanja
ShellSort je sortirni algoritem.
Izboljša algoritem za navadno vstavljanje tako, da:
- sortiramo v več etapah z različnimi koraki (med seboj sortiramo samo elemente, ki so oddaljeni i×korak)
- korak se postopoma zmanjšuje do vrednosti 1
Namen spremembe je v tem, da bi tabela težila k vse večji urejenosti še pred končnim korakom z vrednostjo 1.
Najpomembnejše pri izbiru korakov je, da koraki niso večkratniki naslednjih korakov. Drugače je sortiranje neučinkovito.
Vsebina |
Opis algoritma
for (int m=0; m<T;++m)
{
določi korak k za to etapo;
for (int i=k;i<a.length;++i)
{
x=a[i];
upoštevajoč korak k vstavi x na pravo mesto;
}
}
Izbiranje korakov
Koraki se morajo izračunati iz veliosti tabele.
Obnašanje algoritma je odvisno od pravilne izbire korakov:
- koraki naj zagotavljajo prepletanje verig (ko so elementi, ki so bili v isti množici prej, tudi ob naslednjem koraku spet v isti množici)
- primer slabe izbire: 16, 8, 4, 2, 1
Koraki: h1,h2,h3,...,ht
- ht = 1
- hi + 1 < hi
1. možnost
- t = (int)[log3n] − 1
- ht = 1
- hi − 1 = 3 * hi + 1
Koraki: 1, 4, 13, 40, 121, 364, ...
*(int) = typecast, ki zaokroži realno število na celo število (odreže decimalke)
2. možnost
- t = (int)[log2n] − 1
- ht = 1
- hi − 1 = 2 * hi + 1
Koraki: 1, 3, 7, 15, 31, 63, 127, 255, ...
Izračun števila korakov
1 3 7 15 31 63 127 255 511
Primer sortiranja
Najprej razdelimo množico na več množic
- k
- vsak k-ti element spada v isto množico
35 12 46 3 85 19 11 33 67 15 41 62
k=9
35 15
12 41
46 62
3
85
19
11
33
67
Množice urejamo s principom navadnega vstavljanja
35 15 15 35
15 35
12 41 12 41
12 41
46 62 46 62
46 62
Torej dobimo:
15 12 46 3 85 19 11 33 67 35 41 62
Sedaj zmanjšamo korak (npr. na 5):
15 19 41
12 11 62
46 33
3 67
85 35
Zopet sortiramo množice z navadnim vstavljanjem:
15------------19-------------------- ---11------------12----------------- ------33------------46-------------- ---------3-------------67----------- -----------35-------------85-------- 15------------19-------------41----- ---11------------12-------------62--
15 11 33 3 35 19 12 46 67 85 41 62
Korak k se zmanjša na 3:
15 3 12 85
11 35 46 41
33 19 67 62
Ko posortiramo z navadnim vstavljanjem:
3 12 15 85
11 35 41 46
19 33 62 67
3 11 19 12 35 33 15 41 62 85 46 67
Zadeva teži k vedno večji urejenosti s tem, ko se k manjša.
Na koncu je potrebno zadevo izvesti z navadnim korakom k=1 kar pomeni uporabo Navadnega vstavljanja nad celim seznamom, ki nam da rezultat:
3 11 12 15 19 33 35 41 46 62 67 85
Bistvena razlika je, da so skoraj vsi elementi pred koncem že skoraj na pravem mestu oz. blizu pravega mesta.
Algoritem v Javi
public static void shellsort(Element[] a) { final int T=4; int i,j,k,m; int[] h={9,5,3,1}; Element x; for(m=0;m<T;++m) { k=h[m]; System.out.println("Korak = "+k); for (i=k; i<a.length;++i) { x=a[i]; j=i-k; while (j>=0 && x.manjsi(a[j])) { a[j+k]=a[j]; j-=k; } a[j+k]=x; } a[0].izpisiTabelo(a); } }
Algoritem lahko izboljšamo:
public static void shellsort1(Element[] a) { int i,j,k=1; Element x; // izracun koraka za 1. etapo while (9*k<a.length) k=3*k+1; // zanka za etape while (k>0) { System.out.println("Korak = "+k); for (i=k; i<a.length;++i) { x=a[i]; j=i-k; while (j>=0 && x.manjsi(a[j])) { a[j+k]=a[j]; j-=k; } a[j+k]=x; } k/=3; a[0].izpisiTabelo(a); } }
Analiza časovne kompleksnosti
T = O(n1.2) – Wirth
T = O(n1.5) – Hubbard
