Bubble sort — het idee

Leerdoel: je begrijpt hoe bubble sort werkt: buren vergelijken en swappen, herhaald tot alles klopt. Nog geen Python.

Het verhaal

Je staat met een groepje vrienden op een rij en jullie willen op lengte gaan staan, van klein naar groot. Niemand hoeft daarvoor tegelijk te schuiven; je kunt het per tweetal doen.

1. Kijk naar de linker twee personen. Staat de linker kleiner dan de rechter, laat ze dan staan. Zo niet, wissel ze om.
2. Schuif één plek op en doe hetzelfde met het volgende tweetal.
3. Ga zo door tot je het laatste paar hebt gehad.
4. Begin opnieuw, want er moet waarschijnlijk nog meer geruild worden.
5. Komt er een hele ronde voorbij zonder ruil, dan ben je klaar.

Dat is bubble sort in één zin: vergelijk buren en swap, blijf herhalen tot er geen swap meer nodig is.

Waarom heet het zo?

De grote getallen "borrelen" naar achteren, net als een luchtbel die naar de oppervlakte stijgt. In één pass komt het grootste element altijd op zijn plek, achteraan het ongesorteerde stuk.

Visualisatie

Eén pass over [3, 1, 4, 1, 5]:

start:  [ 3 , 1 , 4 , 1 , 5 ]

paar (3,1):  3 > 1?  ja → swap        [ 1 , 3 , 4 , 1 , 5 ]
paar (3,4):  3 > 4?  nee → laat       [ 1 , 3 , 4 , 1 , 5 ]
paar (4,1):  4 > 1?  ja → swap        [ 1 , 3 , 1 , 4 , 5 ]
paar (4,5):  4 > 5?  nee → laat       [ 1 , 3 , 1 , 4 , 5 ]

einde pass 1: [ 1 , 3 , 1 , 4 ,(5)]   5 is nu op zijn juiste plek

Nog niet gesorteerd — we moeten nog een pass doen:

start pass 2: [ 1 , 3 , 1 , 4 , 5 ]
paar (1,3):  laat                     [ 1 , 3 , 1 , 4 , 5 ]
paar (3,1):  swap                     [ 1 , 1 , 3 , 4 , 5 ]
paar (3,4):  laat                     [ 1 , 1 , 3 , 4 , 5 ]
paar (4,5):  laat                     [ 1 , 1 , 3 , 4 , 5 ]

einde pass 2: gesorteerd

Pass 3 zou doen: vier vergelijkingen, geen swaps. Dan weten we zeker dat we klaar zijn — vroege uitstap.

Verschil met selection sort

	Selection sort	Bubble sort
Hoofdtechniek	vind minimum, swap met begin	vergelijk buren, swap
Swaps per ronde	1	0 tot n − 1
Vergelijkingen	altijd n²/2	minder als al gesorteerd
Vroeg klaar?	nee	ja (met early-exit)

Bubble sort is adaptief: op een lijst die al bijna goed staat is hij veel sneller dan op een willekeurige.

Hoe snel?

• Beste geval, een lijst die al gesorteerd is: één pass met n − 1 vergelijkingen en geen enkele swap. Dat is O(n).
• Slechtste geval, een omgekeerd gesorteerde lijst: n − 1 passes met ongeveer n²/2 vergelijkingen en evenveel swaps, dus O(n²).
• Gemiddeld ook O(n²).

Voor grote lijsten is dat traag. Simpel is hij wel.

info

Buren vergelijken en wisselen gaat ook met echte kaarten: zie de werkvorm in Zoeken en sorteren met kaarten.

Zo bouw je het op

De code bouw je in kleine stappen, elk op een eigen pagina in de map "Bouwen, stap voor stap":

1. Bouwsteen 1 — vergelijk twee buren
2. Bouwsteen 2 — twee buren ruilen
3. Bouwsteen 3 — één pass door de lijst
4. Bouwsteen 4 — herhalen tot het klopt
5. Bouwsteen 5 — vroeg klaar als er niets meer hoeft

Daarna zet je alles samen in Het complete algoritme, en ga je het aanpassen en zelf bouwen.

Door naar bekijk het algoritme.