Notities naar quiz

Maximilian

Inleiding

Ik heb onlangs een cursus datastructuren en algoritmen gevolgd als onderdeel van mijn streven om programmeerconcepten op lager niveau en informaticaconcepten te leren. Zoals het gezegde luidt, is de beste manier om je kennis van iets te verstevigen, het te onderwijzen, en aangezien ik mijn quotum om mijn partner deze maand (waarschijnlijk dit jaar) te vervelen met programmeerpraat al heb vervuld, dacht ik dat ik een reeks berichten zou schrijven met een paar dingen die ik heb geleerd. Dit is zo'n bericht.

Wat is het Bubble Sort-algoritme

Het Bubble Sort-algoritme wordt doorgaans toegepast waar eenvoud de voorkeur heeft boven efficiëntie. Het heeft een tijdscomplexiteit van O(n^2), wat minder dan ideaal is bij grotere lijsten.

Hoe werkt het

Om uit te leggen hoe het werkt, is hier wat pseudocode:

for pointer1 in list
    for pointer2 in list
        if list[j] > list[j + 1]
            swap list[j] and list[j + 1]
        pointer2++

    pointer1++

Het idee van dit algoritme is om de grotere items in de lijst naar het einde te 'bubblen'. We kunnen dit voorstellen met 2 pointers, pointer1 en pointer2. We beginnen met beide pointers op het eerste item in de lijst te zetten. Vervolgens doorlopen we de hele lijst met pointer2 en verwisselen we het item op de positie van pointer2 als het item op positie pointer2 + 1 een grotere waarde heeft. We blijven dit proces herhalen tot we het einde van de lijst bereiken. Daarna verhogen we pointer1 met 1 en beginnen we het proces opnieuw met pointer2.

Je hebt misschien gemerkt dat we een manier nodig hebben om te voorkomen dat we items controleren die we al hebben gesorteerd. Aangezien het doel van elke iteratie is om de grotere items naar het einde van de lijst te verplaatsen, kunnen we dit doen door de grens van pointer2 te beperken tot de waarde van pointer1 + 1.

Hoe implementeren we het

Hier is een uitvoerig becommentarieerde implementatie in TypeScript:

function bubbleSort(arr: number[]): void {
    // pointer 1
    for (let i = 0; i < arr.length; ++i) { 
       // pointer 2 + limit iterations by pointer1 + 1
        for (let j = 0; j < arr.length - 1 - i; ++j) {
            // check if current item is larger than the next item
            if (arr[j] > arr[j + 1]) {
                // temporarily store the current item so we don't lose it
                const tmp = arr[j];
                // swap the items in the array
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

Gesorteerd

Dit is in de meeste gevallen niet het algoritme waar je als eerste naar grijpt, maar ik vind het een leuk en gemakkelijk algoritme om mee te beginnen. Ik hoop dat je het nuttig vond of op zijn minst een beetje interessant!