Bronartikel
Het Bubble Sort-algoritme - DEV Community
Maximilian
Inleiding
Ik heb onlangs een cursus datastructuren en algoritmen gevolgd als onderdeel van mijn streven om programmeerconcepten en informaticaconcepten op een lager niveau te leren. Zoals het gezegde luidt: de beste manier om je kennis van iets te verstevigen is het te onderwijzen, en aangezien ik mijn quotum voor het vervelen van mijn partner met codepraat voor deze maand (waarschijnlijk het jaar) al heb vervuld, dacht ik dat ik een reeks berichten zou schrijven met een aantal 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 boven efficiëntie wordt verkozen. De tijdscomplexiteit is 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 'bubbelen'. 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 gaan we met pointer2 door de hele lijst en verwisselen we het item op de positie van pointer2 als het item op positie pointer2 + 1 een grotere waarde heeft. We herhalen dit proces totdat 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 van commentaar voorziene 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 mooi en eenvoudig algoritme om mee te beginnen. Ik hoop dat je het nuttig vond of op zijn minst een beetje interessant!