Counting sort

Counting sort, soms ook count-sort genoemd, is een extreem simpel sorteeralgoritme, dat alleen kan worden gebruikt voor gehele getallen en daarmee vergelijkbare objecten. Juist door de beperkte toepassingsmogelijkheden, kan het een zeer efficiënte manier van sorteren zijn. Een voorwaarde daarvoor is dat de kleinste en de grootste voorkomende waarde bekend zijn, en dat de te sorteren getallen in een relatief klein bereik liggen.

Werking

Als de kleinste en grootste waarden niet bekend zijn, zullen deze vooraf aan het sorteren bepaald moeten worden. De complexiteitsgraad van dit algoritme is O(n+k), waarbij k de grootste voorkomende waarde is. Een nadeel van dit algoritme is dat het erg geheugenintensief is.

Een voorbeeld: De ongesorteerde reeks gehele getallen is 6, 4, 6, 8, 9, 6, 4, 9, 5, 7, 5, 5, 8, 5. Het kleinste getal is 4 en het grootste is 9. Op basis daarvan wordt van elk element tussen 4 en 9 geteld hoe vaak het in de rij voorkomt. Geturfd resultaat:

4: ||
5: ||||
6: |||
7: |
8: ||
9: ||

De resultaten van de telling worden weer achter elkaar geplaatst en het sorteren is voltooid: 4, 4, 5, 5, 5, 5, 6, 6, 6, 7, 8, 8, 9, 9.

Voorbeeldimplementaties

C++

Een implementatie in C++: de functie countingsort sorteert de lijst met gehele getallen aiIn met aantal elementen nInItems volgens het counting-sort-algoritme:

void countingsort(int aiIn[], int nInItems){
  /* bepaal de hoogste en de laagste */
  int iLo= MAXINT;
  int iHi= -MAXINT;
  for (int i= 0; i < nInItems; i++){
    iLo= min(aiIn[i], iLo);
    iHi= max(aiIn[i], iHi);
  }
  /* maak een precies passende turflijst, begin met 0 voor elk getal */
  int nTurfItems= 1 + iHi - iLo;
  int aiTurf[nTurfItems];
  for (int j= 0; j < nTurfItems; j++){
    aiTurf[j]= 0;
  }
  /* turven */
  for (int i= 0; i < nInItems; i++){
    aiTurf[aiIn[i] - iLo]++; // 1 erbij voor het getal op positie i
  }
  /* turflijst langslopen en aftellen,
     we hergebruiken de gegeven lijst voor het antwoord */
  int i= 0;
  for (int j= 0; j < nTurfItems; j++){
    while (aiTurf[j] > 0){
      aiIn[i++]= iLo + j;
      aiTurf[j]--;
    }
  }
  /* aiIn bevat nu de getallen op de juiste volgorde */
}

Java

Een implementatie in Java: de functie countingsort sorteert de array "data" met "lengte" aantal elementen volgens het counting-sort-algoritme:

  // "data" is de array die gesorteerd wordt, deze array bevat "lengte" aantal elementen
  public void countingsort(int data[], int lengte)
  {
    int i,j,k=0,kleinste, grootste;
    // zoek kleinste en grootste
    kleinste = grootste = data[0];
    for(i=1;i<lengte;i++) 
      if (data[i]<kleinste) 
        kleinste=data[i];
      else if (data[i]>grootste)
        grootste=data[i];
    int[] turven = new int[grootste-kleinste+1]; // maak telarray<br>
    for(i=0;i<(grootste-kleinste+1);i++)
      turven[i]=0; // laat alle turven op nul beginnen
    for(i=0;i<lengte;i++)
      turven[data[i]-kleinste]++; // zet turven
    // sorteer data (zet turf "i" "j"x op plaats "k")
    for(i=kleinste;i<=grootste;i++)
      for(j=turven[i-kleinste];j>0;j--)
      {
         data[k] = i;
         k++;
      }
  }

C#

Een console-applicatie als voorbeeld. Er wordt gebruikgemaakt van een frequentietabel om de waarden te sorteren. (de index van de frequentietabel = de waarde van het getal dat je wil sorteren, deze verhoog je dan met 1).
Wanneer het gesorteerd is, geef je de indexen van de frequentietabel weer (naargelang de hoeveelheid keer het voorkwam)

using system;
class Program 
{
  static void Main(string[] args)
  {
    Berekeningen Ber = new Berekeningen();                                                // verwijzing naar Berekeningen klasse leggen
    int[] tabelMetGetallen = { 2, 1, 3, 22, 8, 5, 6, 7, 84, 2, 4, 5, 6, 9, 8, 5, 9, 60 }; // de getallen die moeten worden gesorteerd (random gekozen hier)

    int Max = Ber.LengteVanDeFrequentieTabel(tabelMetGetallen) + 1;                       // de grootte bepalen van de frequentietabel (kan ook manueel gekozen worden)
    int[] frequentieTabel = new int[Max];                                                 // aanmaken ftab (= frequentietabel)

    Ber.FrequentietabelVullen(tabelMetGetallen, frequentieTabel);                         // uitvoeren van de method (zie lager)

    for (int I = 0 ; I < Max ; I++)                                                       // de getallen weergeven
    {		                                                                          // de waarde van de index, is het aantal keer het indexnummer zelf voorkomt
      for (int J = frequentieTabel[I] ; J > 0 ; J--)
      {
	Console.Write(I + " ");
      }
    }
     Console.ReadKey();
  }/*Main*/
}/*Program*/

class Berekeningen
{
  public int LengteVanDeFrequentieTabel(int[] getallen)                                    // hoogste getal berekenen in tabelMetGetallen (= lengte van ftab)
  {
    int Max = getallen[0];
    for (int Z = 0 ; Z < getallen.Length ; Z++)
    {
      if (getallen[Z] > Max)
      {
        Max = getallen[Z];
      }
    }
    return Max;
  }/*lengteVanX*/

  public void FrequentietabelVullen(int[] tabelMetGetallen, int[] frequentieTabel)         // per keer een getal voorkomt in tabelMetGetallen
  {                                                                                        // wordt de index met hetzelfde getal van ftab verhoogt
    for (int i = 0 ; i < tabelMetGetallen.Length ; i++)                                    // bv: als getal 3 voorkomt in tabelMetGetallen
    {                                                                                      // dan zal index 3 in ftab verhogen met 1
      frequentieTabel[tabelMetGetallen[i]] += 1;
    }
  }/*FtabVullen*/
}/*Berekeningen*/