Sorteren en zoeken
Snel Dingen Vinden
Als je Google doorzoekt, verschijnen resultaten in minder dan een seconde - gerangschikt van meest naar minst relevant. Wanneer Netflix films aanbeveelt, sorteert het duizenden titels op hoe waarschijnlijk je ervan geniet. Achter elke snelle opzoeking en elke gerangschikte lijst schuilt een sorteer- of zoekalgoritme.
Waarom Sorteren Belangrijk Is
Gesorteerde data is krachtige data. Zodra een lijst op orde is, kun je:
- Efficiënt zoeken met binary search (daar komen we zo op).
- Duplicaten vinden - ze staan dan direct naast elkaar.
- De top-N resultaten vinden - pak simpelweg de eerste N items.
- Datasets samenvoegen - twee gesorteerde lijsten combineren is veel sneller dan ongesorteerde.
Bubble Sort - Eenvoudig maar Traag
Bubble sort loopt herhaaldelijk door de lijst, vergelijkt naast elkaar staande items en verwisselt ze als ze in de verkeerde volgorde staan. Grotere waarden "bubbelen" naar het einde.
[5, 3, 8, 1, 2]
↕
[3, 5, 8, 1, 2] → 5 en 3 verwisseld
[3, 5, 1, 8, 2] → 8 en 1 verwisseld
[3, 5, 1, 2, 8] → 8 en 2 verwisseld
... doorgaan totdat er niets meer verwisseld hoeft te worden
Tijdcomplexiteit: O(n²). Met 1.000.000 items? Een biljoen vergelijkingen. Niet praktisch voor AI-werklasten.
Als bubble sort ongeveer n² vergelijkingen kost, hoeveel langzamer zou het zijn om een miljoen items te sorteren vergeleken met duizend? Denk aan de verhouding: (1.000.000)² vs (1.000)². Dat is een miljoen keer langzamer - alleen door duizend keer meer data.
Merge Sort - Verdeel en Heers
Merge sort splitst de lijst in tweeën, sorteert elke helft, en voegt de twee gesorteerde helften samen.
[5, 3, 8, 1, 2, 7, 4, 6]
splits
[5, 3, 8, 1] [2, 7, 4, 6]
splits splits
[5, 3] [8, 1] [2, 7] [4, 6]
↓ ↓ ↓ ↓
[3, 5] [1, 8] [2, 7] [4, 6]
samenvoegen samenvoegen
[1, 3, 5, 8] [2, 4, 6, 7]
samenvoegen
[1, 2, 3, 4, 5, 6, 7, 8]
Tijdcomplexiteit: O(n log n) - dramatisch sneller. Voor een miljoen items is dat circa 20 miljoen vergelijkingen in plaats van een biljoen.
Discussion
Sign in to join the discussion