Twee gesorteerde reeksen samenvoegen
Beide lijsten doorlopen met elk één pointer
Twee gesorteerde reeksen samenvoegen is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 4 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
De samenvoegstap
Gegeven twee gesorteerde lijsten: voeg ze samen tot één gesorteerde lijst. Deze samenvoeging vormt de kern van mergesortering en komt overal voor. 🔗
Twee invoeren, elk één pointer
Geef elke lijst een eigen pointer, beide beginnend op index 0. Je loopt met beide samen vooruit en nooit achteruit.
i = 0
j = 0Kies altijd de kleinste
Vergelijk bij elke stap de twee voorste elementen. Voeg het kleinste toe aan het resultaat, want dat moet in de gesorteerde volgorde als volgende komen.
Verplaats de winnende pointer
Nadat je een waarde hebt gekozen, verhoog je alleen de pointer waar die waarde vandaan kwam. De andere lijst heeft nog steeds zijn kleinste element klaarstaan.
if a[i] <= b[j]:
out.append(a[i])
i += 1
else:
out.append(b[j])
j += 1De hoofdlus
Blijf samenvoegen while beide lijsten nog elementen bevatten. Zodra een van beide leeg is, heeft vergelijken geen zin meer.
while i < len(a) and j < len(b):
# compare and append
passDe overgebleven elementen toevoegen
Wanneer één lijst leeg raakt, staat de andere al in de juiste volgorde. Voeg de overgebleven rest daarom direct toe aan het resultaat met append.
out.extend(a[i:])
out.extend(b[j:])Waarom de rest vanzelf gaat
De overgebleven rest staat al in de juiste volgorde, dus verder vergelijken is niet nodig. Een van de twee aanroepen van extend voegt simpelweg niets toe.
In totaal lineaire tijd
Elk element wordt één keer bekeken. Daarom kost het samenvoegen van twee lijsten met lengtes n en m O(n + m)-tijd. Sneller kan niet.
Behoud de stabiliteit
Door <= te gebruiken wanneer waarden gelijk zijn, blijven gelijke elementen in hun oorspronkelijke volgorde staan. Die stabiliteit is belangrijk wanneer je extra gegevens meeneemt.
Ook achteruit samenvoegen
Als je wilt samenvoegen in een buffer zonder vrije ruimte, loop je juist vanaf de achterkant en plaats je het grootste element als laatste. Hetzelfde idee, maar gespiegeld.
Van samenvoegen naar sorteren
Splits, sorteer de helften en voeg ze daarna samen: die recursie is mergesortering. De samenvoeging met twee pointers die je net hebt geleerd, is de kern ervan.
Korte controle
Je voegt twee gesorteerde lijsten samen met één pointer in elke lijst.
Samenvatting
Doorloop twee gesorteerde lijsten met elk een pointer, kies steeds het kleinste voorste element en voeg daarna de rest toe. Dit werkt in O(n + m) en vormt de basis van mergesortering. 🚀
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Twee gesorteerde reeksen samenvoegen” gratis?
Ja — de volledige tekst van “Twee gesorteerde reeksen samenvoegen” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Twee gesorteerde reeksen samenvoegen”?
Beide lijsten doorlopen met elk één pointer Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 4 van 4.
Hoe lang duurt de les “Twee gesorteerde reeksen samenvoegen”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Twee pointers in een gesorteerde array
- Een paar met een gegeven som vinden
- Duplicaten ter plaatse verwijderen
- Twee gesorteerde reeksen samenvoegen