Max én min in één pass — het idee

Leerdoel: je begrijpt waarom je beide tegelijk wilt bijhouden, en waarom dat niet dubbel zoveel werk kost als alleen het maximum.

Het verhaal

Stel: je hebt een lijst met dagtemperaturen van een hele maand. Je wilt weten:

Wat was de warmste dag?
Wat was de koudste dag?

Je hebt al geleerd hoe je het maximum vindt. Voor het minimum hetzelfde recept (één teken anders).

Twee mogelijke aanpakken:

Aanpak A — twee aparte passes

pass 1: doorloop alle dagen → vind het maximum
pass 2: doorloop alle dagen → vind het minimum

Dat werkt, maar je leest elke temperatuur twee keer. Bij een miljoen metingen zijn dat twee miljoen leesacties.

Aanpak B — één pass, twee accumulators

één pass:
    doorloop alle dagen
    voor elke dag:
        update zo nodig het maximum
        update zo nodig het minimum

Nu lees je elke temperatuur één keer: een miljoen leesacties in plaats van twee miljoen. Het aantal vergelijkingen blijft ongeveer gelijk, want per element kijk je of het kleiner is én of het groter is.

Visualisatie

We zoeken klein en groot in deze lijst:

lijst:  [ 5 , 2 , 8 , 1 , 7 , 4 ]
index:    0   1   2   3   4   5

start:  klein = 5, groot = 5    beide op het eerste element

waarde 5:  5 < 5 nee, 5 > 5 nee  ->  niets verandert   (2 vergelijkingen)
waarde 2:  2 < 5 ja              ->  klein = 2         (1 vergelijking)
waarde 8:  8 < 2 nee, 8 > 5 ja   ->  groot = 8         (2 vergelijkingen)
waarde 1:  1 < 2 ja              ->  klein = 1         (1 vergelijking)
waarde 7:  7 < 1 nee, 7 > 8 nee  ->  niets verandert   (2 vergelijkingen)
waarde 4:  4 < 1 nee, 4 > 8 nee  ->  niets verandert   (2 vergelijkingen)

eind:   klein = 1, groot = 8    in 10 vergelijkingen

De eerste waarde wordt met zichzelf vergeleken, want de lus begint gewoon bij het begin van de lijst. Verder doe je er per waarde hoogstens twee, en soms maar één: is de waarde de nieuwe kleinste, dan hoeft er niet meer gekeken te worden of hij ook de grootste is. Dat kan namelijk niet allebei. Hoe je dat in code opschrijft zie je in bouwsteen 2.

Twee accumulators tegelijk

Het accumulator-patroon werkt voor meer dan één ding tegelijk. Je hebt er alleen meer variabelen voor nodig:

accumulator_1 = startwaarde_1
accumulator_2 = startwaarde_2
voor elk element:
    update_1?
    update_2?
return beide

Hetzelfde idee als bij vind-maximum, alleen verdubbeld.

Kun je dit ook met drie of meer accumulators?

Ja. Met dezelfde aanpak kun je bijvoorbeeld tegelijk vinden:

het maximum
het minimum
de som
het aantal elementen

En dat allemaal in één pass. Voor n elementen blijft het O(n): extra variabelen kosten geen extra rondes door de lijst.

Zo bouw je het op

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

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

Door naar bekijk het algoritme.

Het verhaal​

Aanpak A — twee aparte passes​

Aanpak B — één pass, twee accumulators​

Visualisatie​

Twee accumulators tegelijk​

Zo bouw je het op​