Shellsort
Shellsort (of Shell sort) is een sorteeralgoritme dat in 1959 uitgevonden is door Donald L. Shell.
Het is een snel algoritme dat ook makkelijk te implementeren is.
Werking bewerken
Shell sort is eigenlijk een gevorderde versie van insertion sort. Als we deze analyseren zien we dat het een algoritme is dat snel kan sorteren als de data al bijna gesorteerd is, maar dat het traag werkt op volledig ongesorteerde data. Daarom zorgt shell sort dat de data al gedeeltelijk gesorteerd is.
Shell sort verdeelt de data in kleine stukken, sorteert deze stukken met insertion sort en rangschikt alles zodat eerst de eerste elementen van alle stukken eerst komen, gevolgd door de elementen op de tweede plaats in alle stukken, enzovoort. Hierna begint shell sort opnieuw maar nu worden er grotere stukken genomen. Op het einde is er maar 1 stuk en als dit gesorteerd is alles klaar.
Indien men dit ter plaatse doet in één tabel, heeft men telkens een tabel waar alle elementen die zich op afstand k van elkaar bevinden gesorteerd zijn (zo'n tabel noemt men een k-gesorteerde tabel), waarbij k een reeks van dalende incrementen doorloopt. Om die reden werd Shell sort vroeger ook diminishing increment sort genoemd.
De keuze van de incrementen beïnvloedt de snelheid van het sorteren. Wat de optimale reeks is, is niet bekend. De analyse hiervan zou zeer moeilijk zijn.
Voorbeeld bewerken
Stel dat we de volgende cijfers van klein naar groot moeten sorteren:
5 2 9 8 2 3 3 8 5 8 5 1 0 1 7 3 0 6 1 6 8 4 7 7 2
We beginnen met de data opnieuw te schrijven maar om de 9 cijfers beginnen we op een nieuwe rij:
5 2 9 8 2 3 3 8 5 8 5 1 0 1 7 3 0 6 1 6 8 4 7 7 2
De 9 kolommen van 3 (of 2) elementen zijn de stukken die we gaan sorteren met insertion sort. Als dit gebeurd is, krijgen we dit als resultaat:
1 2 1 0 1 3 2 0 5 5 5 8 4 2 7 3 8 6 8 6 9 8 7 7 3
Als we nu de data gewoon terug achter elkaar plaatsen dan merken we dat de grote cijfers meestal achteraan zitten en dat de data dus al gedeeltelijk gesorteerd is:
1 2 1 0 1 3 2 0 5 5 5 8 4 2 7 3 8 6 8 6 9 8 7 7 3
Nu beginnen we opnieuw maar we nemen nu maar 4 kolommen in plaats van 9:
1 2 1 0 1 2 1 0 1 3 2 0 1 2 2 0 5 5 5 8 3 3 5 3 4 2 7 3 => 4 5 7 6 8 6 8 6 5 6 7 7 9 8 7 7 8 8 8 8 3 9
Als we nu de data achtereen plaatsen zien we dat het bijna perfect gesorteerd is:
1 2 1 0 1 2 2 0 3 3 5 3 4 5 7 6 5 6 7 7 8 8 8 8 9
Nu sorteren we de rest van de data gewoon met insertion sort en krijgen we:
0 0 1 1 1 2 2 2 3 3 3 4 5 5 5 6 6 7 7 7 8 8 8 8 9
Implementatie bewerken
Hier volgt een voorbeeld van een implementatie in C, de functie "shellsort" sorteert de array "invoer" met "lengte" aantal elementen volgens het shellsort algoritme, eerst wordt de data in "lengte/3" kolommen verdeeld en in de volgende stappen wordt telkens 1/3 van het aantal kolommen van de vorige stap gebruikt,
void shellsort(int invoer[],int lengte){
int i,j,t,kol;
//begin met te verdelen in lengte/3 kolommen en deel het aantal telkens door 3
for(kol=lengte/3;;kol/=3){
if(kol==0) kol=1;
//neem telkens een kolom
for(i=kol;i<lengte;i++){
j=0;
//sorteer de kolom met insertion sort
while(i-j>=kol && invoer[i-j]<invoer[i-kol-j]){
t=invoer[i-j];invoer[i-j]=invoer[i-kol-j];invoer[i-kol-j]=t;
j+=kol;
}
}
if(kol==1) return;
}
}
Deze implementatie is gemakkelijk, maar inefficiënt voor b.v.
lengte = 243, 729, 2187, ... , 3n
(complexiteitsgraad O(n2)).
De volgende implementatie in Java neemt de
aantal kolommen uit een welgekozen sequens (array kolommen) en
sorteert de kolommen met een efficiënter implementatie van insertion sort.
void shellsort(int[] invoer, int lengte)
{ int i,j,k,t,kol;
int[] kolommen = { 1,4,9,29,97,259,815,1968,4711,11969,27901,84801,
213331,543749,1355339,3501671,8810089,21521774,
58548857,157840433,410151271,1131376761,2147483647 };
// zoek de grootste aantal kolommen kleiner dan 'lengte'
for (k=0; kolommen[k]<lengte; k++);
while (--k >= 0)
{ kol=kolommen[k];
// sorteer de kolommen met insertion sort
for (i=kol; i<lengte; i++)
{ t=invoer[i];
j=i;
while (j>=kol && t<invoer[j-kol])
{ invoer[j]=invoer[j-kol];
j=j-kol;
}
invoer[j]=t;
}
}
}