DSA Interview Prep · Les

Quick sort en pivotselectie

Bouw quick sort met de partitieschema's van Lomuto en Hoare, bespreek het slechtste geval O(n²) en hoe gerandomiseerde pivotselectie dit beperkt.

Les 3 van 413 stappen

Quick sort en pivotselectie is een gratis DSA Interview Prep-les op CoddyKit. Dit is les 3 van 4. Je kunt 3 lessen uit dit leerpad gratis volledig lezen — daarna ontgrendelt CoddyKit PRO alle lessen, plus praktische oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject DSA Interview Prep. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus DSA Interview Prep bevat in totaal 4 lessen.

Quicksort: splitsen en heersen in-place

Quicksort is in de praktijk het meest gebruikte sorteeralgoritme. In tegenstelling tot merge sort sorteert het algoritme in-place zonder extra arrays toe te wijzen. Het kernidee: kies een pivot-element, partitioneer de array zodat alle elementen die kleiner zijn dan de pivot ervoor staan en alle grotere elementen erna, en sorteer vervolgens elke partitie recursief. De partitioneringsstap kost O(n) tijd en bij een goede pivot is de recursiediepte O(log n).

def quick_sort(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo < hi:
        pivot_idx = partition(arr, lo, hi)
        quick_sort(arr, lo, pivot_idx - 1)  # sort left
        quick_sort(arr, pivot_idx + 1, hi)  # sort right

def partition(arr, lo, hi):
    pivot = arr[hi]  # Lomuto: choose last element as pivot
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[hi] = arr[hi], arr[i+1]
    return i + 1

arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort(arr)
print(arr)  # [1, 1, 2, 3, 6, 8, 10]

Partitioneringsschema van Lomuto

De Lomuto-partitionering gebruikt het laatste element als pivot. Een langzame aanwijzer i houdt de grens bij van het gebied met elementen die kleiner zijn dan de pivot; een snelle aanwijzer j scant vooruit. Wanneer arr[j] <= pivot, verhoog je i en verwissel je arr[i] met arr[j], waardoor het gebied met kleine elementen groter wordt. Plaats na het scannen de pivot op i+1 door deze te verwisselen met arr[hi]. Eenvoudig te implementeren, maar het voert 3× meer wisselingen uit dan het schema van Hoare.

def lomuto_partition_traced(arr, lo, hi):
    pivot = arr[hi]
    i = lo - 1
    print(f'Pivot: {pivot}, array: {arr[lo:hi+1]}')
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[hi] = arr[hi], arr[i+1]
    print(f'After partition: {arr[lo:hi+1]}')
    return i + 1

arr = [3, 1, 4, 1, 5, 9, 2, 6]
lomuto_partition_traced(arr, 0, len(arr)-1)

Partitioneringsschema van Hoare

De Hoare-partitionering gebruikt twee aanwijzers die aan beide uiteinden beginnen en naar elkaar toe bewegen tot ze elkaar kruisen. De pivot (meestal het eerste element) wordt gekozen en elementen die kleiner zijn dan de pivot worden naar links verplaatst, terwijl grotere elementen naar rechts gaan. Het schema van Hoare voert 3× minder wisselingen uit dan Lomuto en werkt beter met gelijke elementen, maar de pivot komt na het partitioneren niet op zijn definitieve positie terecht — daarom zijn iets andere recursieve aanroepen nodig.

def hoare_partition(arr, lo, hi):
    pivot = arr[lo]  # first element as pivot
    i, j = lo - 1, hi + 1
    while True:
        i += 1
        while arr[i] < pivot: i += 1
        j -= 1
        while arr[j] > pivot: j -= 1
        if i >= j: return j
        arr[i], arr[j] = arr[j], arr[i]

def quick_sort_hoare(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo < hi:
        p = hoare_partition(arr, lo, hi)
        quick_sort_hoare(arr, lo, p)      # note: p not p-1
        quick_sort_hoare(arr, p+1, hi)

arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort_hoare(arr)
print(arr)  # [1, 1, 2, 3, 6, 8, 10]

Slechtste geval O(n²): al gesorteerde invoer

Het slechtste geval van quicksort doet zich voor wanneer de pivot consequent het kleinste of grootste element in de partitie is. Bij Lomuto's pivot als laatste element op een al gesorteerde array plaatst de partitionering altijd 0 elementen links en n-1 rechts: de recursieboom ontaardt in een keten met diepte n, wat O(n²) vergelijkingen oplevert. Daarom is pivotkeuze zo belangrijk en kiezen productie-implementaties de pivot willekeurig.

import sys
sys.setrecursionlimit(5000)

def quick_sort_naive(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    comparisons = [0]
    def _qs(lo, hi):
        if lo >= hi: return
        pivot = arr[hi]  # last element pivot
        i = lo - 1
        for j in range(lo, hi):
            comparisons[0] += 1
            if arr[j] <= pivot:
                i += 1; arr[i], arr[j] = arr[j], arr[i]
        arr[i+1], arr[hi] = arr[hi], arr[i+1]
        p = i + 1
        _qs(lo, p-1); _qs(p+1, hi)
    _qs(lo, hi)
    return comparisons[0]

import math
n = 100
sorted_arr = list(range(n))
ops = quick_sort_naive(sorted_arr)
print(f'n={n}, ops={ops}, n^2={n**2}')  # ops close to n*(n-1)/2

Willekeurige pivot: verwacht O(n log n)

Door de pivot uniform willekeurig te kiezen (verwissel vóór het partitioneren een willekeurig element met arr[hi]), neemt de kans op het consequent kiezen van slechte pivots exponentieel af. Het verwachte aantal vergelijkingen is 2n ln(n) ≈ 1.39 n log₂(n), wat met zeer hoge waarschijnlijkheid een verwachte tijd van O(n log n) oplevert. Daarom wordt quicksort met willekeurige pivotkeuze in de praktijk gebruikt — het voorkomt pathologische slechtste gevallen die een tegenstander voor strategieën met een vaste pivot zou kunnen construeren.

import random

def quick_sort_random(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo < hi:
        # Randomise pivot
        rand_i = random.randint(lo, hi)
        arr[rand_i], arr[hi] = arr[hi], arr[rand_i]
        # Lomuto partition with last element as pivot
        pivot = arr[hi]
        i = lo - 1
        for j in range(lo, hi):
            if arr[j] <= pivot:
                i += 1; arr[i], arr[j] = arr[j], arr[i]
        arr[i+1], arr[hi] = arr[hi], arr[i+1]
        p = i + 1
        quick_sort_random(arr, lo, p - 1)
        quick_sort_random(arr, p + 1, hi)

arr = list(range(100, 0, -1))  # worst case for naive
quick_sort_random(arr)
print(arr[:10])  # [1,2,3,4,5,6,7,8,9,10]

Mediaan-van-drie-pivot

Een andere pivotstrategie: kies de mediaan van het eerste, middelste en laatste element. Hiermee vermijd je gedrag in het slechtste geval bij gesorteerde of omgekeerd gesorteerde invoer (de meest voorkomende invoer die een tegenstander gebruikt), zonder de kosten van het genereren van willekeurige getallen. Veel productie-implementaties gebruiken mediaan-van-drie of ninther (de mediaan van drie medianen) voor grote arrays en schakelen voor kleine deelarrays onder een drempel van ongeveer 10 elementen over op insertion sort.

def median_of_three(arr, lo, hi):
    mid = (lo + hi) // 2
    # Sort lo, mid, hi values in place
    if arr[lo] > arr[mid]:  arr[lo], arr[mid] = arr[mid], arr[lo]
    if arr[lo] > arr[hi]:   arr[lo], arr[hi]  = arr[hi],  arr[lo]
    if arr[mid] > arr[hi]:  arr[mid], arr[hi] = arr[hi],  arr[mid]
    # Median is now at arr[mid]; swap to arr[hi-1] as pivot
    arr[mid], arr[hi] = arr[hi], arr[mid]
    return arr[hi]  # pivot value

arr = [3, 9, 1]
print(median_of_three(arr, 0, 2), arr)  # 3, [1,3,9] (sorted)

Nederlandse vlag: partitionering in drie delen

Bij standaardpartitionering worden elementen die kleiner zijn dan de pivot links geplaatst en grotere elementen rechts, maar elementen die gelijk zijn aan de pivot raken verspreid. Partitionering in drie delen (Nederlandse vlag) maakt drie gebieden: <pivot, ==pivot, >pivot. Dit is cruciaal voor arrays met veel dubbele waarden — bij standaardquicksort verslechtert de uitvoering tot O(n²), terwijl quicksort met drie delen O(n) oplevert voor invoer waarin overal dezelfde waarde staat.

def three_way_partition(arr, lo, hi):
    pivot = arr[lo]
    lt = lo      # arr[lo..lt-1] < pivot
    gt = hi      # arr[gt+1..hi] > pivot
    i = lo       # current
    while i <= gt:
        if arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1; i += 1
        elif arr[i] > pivot:
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1  # don't advance i
        else:
            i += 1
    return lt, gt  # pivot occupies arr[lt..gt]

arr = [3, 1, 4, 1, 5, 9, 2, 6, 3, 3]
lt, gt = three_way_partition(arr, 0, len(arr)-1)
print(arr, '| pivot region:', lt, 'to', gt)

Het k-de kleinste element in O(n) met quickselect

Quickselect gebruikt de partitioneringsstap van quicksort om het k-de kleinste element te vinden in gemiddeld O(n)-tijd, zonder alles volledig te sorteren. Na het partitioneren staat de pivot op zijn definitieve positie p. Als p == k, geef arr[p] terug. Als k < p, voer je recursie uit op de linkerpartitie; als k > p, op de rechterpartitie. Gemiddeld halveert elke recursiestap het probleem: O(n) + O(n/2) + O(n/4) + ... = O(2n) = O(n).

import random

def quickselect(nums, k):
    '''Find kth smallest (0-indexed) in O(n) average.'''
    def _select(lo, hi):
        if lo == hi: return nums[lo]
        rand_i = random.randint(lo, hi)
        nums[rand_i], nums[hi] = nums[hi], nums[rand_i]
        pivot = nums[hi]
        i = lo - 1
        for j in range(lo, hi):
            if nums[j] <= pivot:
                i += 1; nums[i], nums[j] = nums[j], nums[i]
        p = i + 1
        nums[p], nums[hi] = nums[hi], nums[p]
        if p == k:    return nums[p]
        elif k < p:   return _select(lo, p - 1)
        else:         return _select(p + 1, hi)
    return _select(0, len(nums) - 1)

print(quickselect([3,2,1,5,6,4], 1))  # 2  (2nd smallest)

Ruimtecomplexiteit van quicksort

Quicksort wordt in-place genoemd, maar gebruikt gemiddeld O(log n) stackruimte voor de recursie (één frame per niveau van de recursieboom). In het slechtste geval is de stackdiepte O(n). Om in het slechtste geval O(log n) stackruimte te garanderen, voer je altijd eerst recursie uit op de kleinere partitie en gebruik je staartaanroepoptimalisatie voor de grotere partitie. De recursielimiet van Python maakt zeer diepe quicksort-recursies riskant — het is de moeite waard dit in sollicitatiegesprekken te noemen.

def quick_sort_optimised(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    while lo < hi:
        p = lomuto_partition_qs(arr, lo, hi)
        # Recurse on smaller partition; iterate on larger
        if p - lo < hi - p:
            quick_sort_optimised(arr, lo, p - 1)
            lo = p + 1  # tail-call elimination
        else:
            quick_sort_optimised(arr, p + 1, hi)
            hi = p - 1

def lomuto_partition_qs(arr, lo, hi):
    pivot = arr[hi]; i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot: i += 1; arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[hi] = arr[hi], arr[i+1]
    return i + 1

Sorteeralgoritmen vergelijken

Combineer je kennis:

Quicksort: verwacht O(n log n), O(n²) in het slechtste geval, O(log n) ruimte, niet stabiel, in de praktijk het snelst voor willekeurige gegevens
Merge sort: gegarandeerd O(n log n), O(n) ruimte, stabiel, het beste voor gekoppelde lijsten en extern sorteren
Heapsort: gegarandeerd O(n log n), O(1) ruimte, niet stabiel, in de praktijk langzamer door cachemissers
Insertion sort: O(n) in het beste geval, ideaal voor kleine n of bijna gesorteerde gegevens

Motiveer je keuze in sollicitatiegesprekken aan de hand van deze afwegingen.

# Python's sorted() uses Timsort:
# - Hybrid: merge sort for large runs, insertion sort for small (< 64 elements)
# - Stable, O(n log n) worst case
# - O(n) best case for sorted/reverse-sorted/nearly-sorted
# - O(n) extra space

import random
arr = random.sample(range(10000), 1000)
sorted_arr = sorted(arr)  # Timsort
print(sorted_arr[:5], '...')  # first 5 elements

Introsort: alle drie combineren

Introsort (gebruikt in C++ STL std::sort) combineert quicksort, heapsort en insertion sort: begin met quicksort met willekeurige pivotkeuze; schakel over op heapsort als de recursiediepte groter wordt dan 2 log n (wat op een slechte pivotreeks wijst) om O(n log n) te garanderen; gebruik insertion sort voor deelarrays met minder dan 16 elementen. Dit levert in het slechtste geval O(n log n) op, met de snelheid van quicksort in het gemiddelde geval en de efficiëntie van insertion sort voor kleine deelarrays.

# Introsort hybrid (simplified)
def introsort(arr, depth_limit=None):
    if depth_limit is None:
        import math
        depth_limit = 2 * int(math.log2(len(arr) + 1)) if arr else 0
    if len(arr) <= 16:
        # insertion sort for small arrays
        for i in range(1, len(arr)):
            key = arr[i]; j = i - 1
            while j >= 0 and arr[j] > key:
                arr[j+1] = arr[j]; j -= 1
            arr[j+1] = key
        return arr
    if depth_limit == 0:
        arr.sort()  # fall back to heapsort equivalent
        return arr
    # Otherwise quick sort
    pivot = arr[-1]
    small = [x for x in arr[:-1] if x <= pivot]
    large = [x for x in arr[:-1] if x > pivot]
    return introsort(small, depth_limit-1) + [pivot] + introsort(large, depth_limit-1)

print(introsort([5,3,8,1,9,2,7]))

Snelle controle

Toets je begrip van de concepten uit Data Structures & Algorithms — Coding Interview Prep in deze les.

Beantwoord dit in de interactieve les

Samenvatting van de les

In deze les heb je geleerd: quicksort partitioneert in-place rond een pivot en voert recursie uit aan beide kanten, met een verwachte tijd van O(n log n) en O(log n) stackruimte — in de praktijk sneller dan merge sort voor willekeurige gegevens, het slechtste geval O(n²) doet zich voor bij gesorteerde invoer met een vaste pivot en wordt vermeden door willekeurige pivotkeuze of mediaan-van-drie, en partitionering in drie delen verwerkt dubbele elementen efficiënt, terwijl quickselect het partitioneringsidee uitbreidt om het k-de kleinste element in gemiddeld O(n) te vinden zonder volledig te sorteren. Hierna onderzoeken we niet-vergelijkende sorteeralgoritmen en de ingebouwde sorteerfunctie van Python.

Gratis beginnen

Leer Python 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: 30
Lessen: 120

Gratis beginnen met leren Bekijk de volledige cursus

Veelgestelde vragen

Is de les “Quick sort en pivotselectie” gratis?

Ja — je kunt hier op het web alle 3 lessen van het leerpad DSA Interview Prep, waaronder “Quick sort en pivotselectie”, gratis volledig lezen. Daarna ontgrendelt CoddyKit PRO alle lessen, plus interactieve oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. De cursus DSA Interview Prep bevat in totaal 4 lessen.

Wat leer ik in “Quick sort en pivotselectie”?

Bouw quick sort met de partitieschema's van Lomuto en Hoare, bespreek het slechtste geval O(n²) en hoe gerandomiseerde pivotselectie dit beperkt. Je oefent met DSA Interview Prep 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 DSA Interview Prep te beginnen?

Ervaring vooraf is niet nodig. DSA Interview Prep 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 3 van 4.

Hoe lang duurt de les “Quick sort en pivotselectie”?

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 DSA Interview Prep?

Ja. Elke les over DSA Interview Prep 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

Bubble sort en insertion sort
Merge sort: verdelen, sorteren, samenvoegen
Quick sort en pivotselectie
Sorteren zonder vergelijkingen en Python's sort()

← Terug naar DSA Interview Prep