Shellsort

Shellsort (of Shell sort) is een sorteer-algoritme dat in 1959 uitgevonden is door Donald L. Shell.

Het is een snel algoritme dat ook makkelijk te implementeren is.

Werking

Shell sort is eigenlijk een gevorderde versie van insertion sort. Als we insertion sort 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 2de 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.

Voorbeeld

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

Hier volgt een voorbeeld van een implementatie in C, de functie "shellsort" sorteer 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;
  }
}