Bubble sort

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²).

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

1. Stel de vlag gesorteerd in.
2. Begin aan één uiteinde, beschouw elk naburig paar elementen in een vector na elkaar (in hun volgorde).
3. Als de elementen van een paar niet in orde zijn, verwissel ze dan, en maak de gesorteerde vlag leeg.
4. 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:

• Invoegen sorteren
• Selectie sorteren