Het eerste algoritme dat we van naderbij bekijken, is een sorteeralgoritme: het zet de elementen van een array in volgorde, oplopend of aflopend. We gebruiken bubblesort, een eenvoudig algoritme dat werkt volgens de techniek brute force.

Het idee: vergelijken en wisselen

Bubblesort sorteert door herhaaldelijk twee elementen te vergelijken en ze om te wisselen wanneer ze in de verkeerde volgorde staan. Door dat genoeg keer te doen, schuift elk element vanzelf naar zijn juiste plaats.

Bubblesort wordt een bruteforcetechniek genoemd omdat het simpelweg alle mogelijke vergelijkingen uitvoert, zonder slimme trucs of optimalisaties. Dat is meteen de definitie van brute force: een probleem oplossen door alle mogelijkheden af te gaan.

We sorteren als voorbeeld een array van vijf namen alfabetisch:

string[] lijst = new string[5];
lijst[0] = "Jan";
lijst[1] = "Piet";
lijst[2] = "Ahmed";
lijst[3] = "An";
lijst[4] = "Max";

Het plan is om eerst het alfabetisch kleinste woord op index 0 te krijgen, dan het op één na kleinste op index 1, enzovoort:

• vergelijk het element op index 0 met dat op index 1, dan met index 2, index 3 en index 4. Wissel telkens als je een kleiner woord tegenkomt. Daarna staat het kleinste woord op index 0.
• doe hetzelfde vanaf index 1 (vergelijk met index 2, 3, 4): nu staat het op één na kleinste woord op index 1.
• ga zo verder tot je het voorlaatste element met het laatste vergelijkt. Dan staat alles in volgorde.

Twee waarden van plaats wisselen

Voor we het algoritme uitschrijven, één bouwsteen: hoe wissel je de inhoud van twee variabelen? Stel woord1 = "tafel" en woord2 = "stoel", en je wil ze omdraaien. Dit lukt niet rechtstreeks:

woord1 = woord2;   // woord1 is nu "stoel" ...
woord2 = woord1;   // ... maar "tafel" is weg, dus woord2 wordt óók "stoel"!

De eerste opdracht overschrijft woord1, dus de oude waarde "tafel" is voorgoed verloren. De oplossing is een hulpvariabele die de waarde even bewaart:

hulp = woord2;     // bewaar "stoel"
woord2 = woord1;   // woord2 wordt "tafel"
woord1 = hulp;     // woord1 wordt "stoel"

Die hulpvariabele heb je nodig telkens je in bubblesort twee elementen omwisselt.

Woorden vergelijken met CompareTo

Voor getallen vergelijk je met < en >. Voor strings gebruik je de ingebouwde functie CompareTo, die twee woorden alfabetisch vergelijkt:

Zo staat lijst[i].CompareTo(lijst[j]) > 0 voor “het woord op index i komt alfabetisch ná het woord op index j”, precies de situatie waarin je beide elementen moet wisselen om oplopend (alfabetisch) te sorteren.

Het algoritme stap voor stap

Laten we de hele sortering volgen op [Jan, Piet, Ahmed, An, Max]. De buitenste lus kiest een index i; de binnenste lus vergelijkt dat element met elk later element en wisselt indien nodig. Vet staat telkens het element dat na die ronde op zijn definitieve plaats staat.

Het eindresultaat is Ahmed An Jan Max Piet, netjes alfabetisch.

In code

De twee geneste lussen, met de hulpvariabele voor het wisselen:

int aantal = lijst.Length;   // hier: 5
string hulp;

for (int i = 0; i <= aantal - 2; i++)
{
    for (int j = i + 1; j <= aantal - 1; j++)
    {
        if (lijst[i].CompareTo(lijst[j]) > 0)   // lijst[i] komt na lijst[j]?
        {
            hulp = lijst[i];
            lijst[i] = lijst[j];
            lijst[j] = hulp;
        }
    }
}

Let op de grenzen: de buitenste i loopt van 0 tot en met aantal - 2 (het laatste element hoef je niet meer met zichzelf te vergelijken), en de binnenste j start telkens op i + 1 (alleen de elementen na i).

Bubblesort bestaat dus uit twee geneste lussen, een if met een vergelijking, en een wissel via een hulpvariabele. Voor getallen vervang je de CompareTo-vergelijking gewoon door < of >; om aflopend te sorteren draai je de vergelijking om. Dat oefen je in de volgende twee oefeningen.