Bubble sort

Bubble sort is een eenvoudig sorteeralgoritme. Het is eenvoudig te begrijpen, dus wordt het meestal aan nieuwe studenten geleerd. Het is niet zo efficiënt als sommige andere sorteeralgoritmen.

De naam Bubble sort komt van het feit dat elk item in de lijst omhoog "borrelt" naar waar het moet komen, zoals bellen in water.

Een bubble sort geïllustreerd

Algoritme

Het algoritme vergelijkt paren van elementen in een lijst. De elementen die de paren vormen staan naast elkaar. Beginnend aan het ene eind van de lijst, worden de twee elementen in elk paar in volgorde met elkaar vergeleken. Dat betekent bijvoorbeeld dat het eerste en tweede element worden vergeleken, dan het tweede en derde element, en dan het derde en vierde, enzovoort. Als de elementen in het huidige paar niet in de juiste volgorde staan, wisselen de twee elementen van plaats. Dit proces - het vergelijken van twee elementen - wordt steeds opnieuw uitgevoerd, totdat de hele lijst gesorteerd is. De lijst is gesorteerd, wanneer er geen paren meer zijn die omgewisseld moeten worden.

In het beste geval, waarin de lijst al gesorteerd was voordat het algoritme werd uitgevoerd, is de complexiteit van het algoritme O(n) (Big O-notatie). In het slechtste geval, waarbij de lijst begint als omgekeerd gesorteerd, is de complexiteit O(n²).

Een voorbeeld van bubble sort. Begin bij het begin van de lijst en vergelijk het volgende paar. Verwissel hun posities als ze niet in de juiste volgorde staan (het tweede in het paar is kleiner dan het eerste in het paar). Na elke iteratie moet één element (het laatste) minder worden vergeleken, totdat er geen elementen meer te vergelijken zijn.

Implementatie

In een imperatieve programmeertaal kan bubble sort worden uitgevoerd door een vlagvariabele te gebruiken en door te lussen door de elementen van de array:

Stel de vlag gesorteerd in.
Begin aan één uiteinde, beschouw elk naburig paar elementen in een vector na elkaar (in hun volgorde).
Als de elementen van een paar niet in orde zijn, verwissel ze dan, en maak de gesorteerde vlag leeg.
Herhaal de vorige stappen totdat de sortering ingesteld blijft.

Als alternatief, aangezien de grootste waarde binnen de eerste iteratie oploopt tot de hoogste index en dan zijn uiteindelijke rechterpositie heeft bereikt, sorteren twee in elkaar geneste for-lussen de vector ook:

for top ≔ high(vector)-1 downto low(vector) do for current ≔ low(vector) to top do if vector[current] > vector[current+1] then exchange(vector, current, current+1)

Verwante pagina's

Invoegen sorteren
Selectie sorteren

Vragen en antwoorden

V: Wat is bubbelsorteren?

A: Bubble sort is een eenvoudig sorteeralgoritme.

V: Waarom wordt bubble sort meestal aan nieuwe studenten geleerd?

A: Bubble sort is eenvoudig te begrijpen en wordt daarom meestal aan nieuwe studenten geleerd.

V: Hoe efficiënt is bubble sort in vergelijking met andere sorteeralgoritmen?

A: Bubble sort is niet zo efficiënt als sommige andere sorteeralgoritmen.

V: Waarom heet bubble sort bubble sort?

A: Bubble sort dankt zijn naam aan het feit dat elk item in de lijst omhoog "borrelt" naar waar het naartoe moet, zoals bellen in water.

V: Is bubble sort geschikt voor grote datasets?

A: Bubble sort is niet geschikt voor grote datasets vanwege de inefficiëntie.

V: Wat is het proces van bubble sort?

A: Bij bubble sort worden aangrenzende elementen in een lijst vergeleken en omgewisseld als ze in de verkeerde volgorde staan.

V: Wat kan er gezegd worden over de complexiteit van bubble sort?

A: De worst-case en gemiddelde tijdcomplexiteit van bubble sort is O(n^2), wat betekent dat het erg lang kan duren om grote datasets te sorteren.