Zoek- en sorteeralgoritmen en efficiëntie

Bij zoeken vraag je of een zoekwaarde voorkomt en waar die voorkomt. Een lijst heeft genummerde posities die indexen heten. Python telt vanaf nul: in [7, 3, 9, 3, 5] staat op index 0 de waarde 7 en op index 4 de waarde 5. De waarde en de index beantwoorden verschillende vragen.

Controleer één element tegelijk

Lineair zoeken, ook sequentieel zoeken genoemd, begint bij het eerste element en vergelijkt elk element met de zoekwaarde. Zodra de methode een overeenkomst vindt, geeft ze de index terug. Als de lijst eindigt zonder overeenkomst, geeft ze -1 terug, ons signaal voor “niet gevonden”.

def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1

len(items) geeft het aantal elementen. range(len(items)) levert elke geldige index, vanaf 0 tot net vóór de lengte. items[i] leest de waarde op de huidige index. Een return beëindigt de functie, dus een latere overeenkomst vervangt nooit de eerste.

Zoeken naar 3 in de lijst hierboven verloopt als volgt:

1. Vergelijk op index 0 de waarde 7 met 3. Ze verschillen, dus ga verder.
2. Vergelijk op index 1 de waarde 3 met 3. Ze komen overeen, dus geef index 1 terug.

Het resultaat is index 1 na twee vergelijkingen. De tweede 3, op index 3, wordt nooit gecontroleerd. Als je in plaats daarvan naar 4 zoekt, controleert de methode 7, 3, 9, 3 en 5 en geeft ze na vijf vergelijkingen -1 terug. Een teruggegeven index van 1 betekent het tweede element, niet een element met de waarde 1.

Tel het werk

Laat $n$ het aantal elementen zijn. Voor een niet-lege lijst is het beste geval één vergelijking: het eerste element komt overeen. Het slechtste geval is $n$ vergelijkingen: de zoekwaarde staat achteraan of ontbreekt. Een lege lijst heeft nul vergelijkingen nodig en geeft -1 terug.

Als een zoekwaarde één keer voorkomt en even waarschijnlijk op elke positie kan staan, is het gemiddelde aantal vergelijkingen

Voor 1.000 elementen zijn dat 500,5 vergelijkingen. Een gemiddelde kan een breuk zijn, ook al maakt elke afzonderlijke zoekopdracht een geheel aantal vergelijkingen. Dit gemiddelde beschrijft die specifieke verdeling van succesvolle zoekopdrachten; vaak voorkomende mislukte zoekopdrachten zouden het totale gemiddelde verhogen.

Meld een mislukte zoekopdracht na de lus

Een else: return -1 binnen de lus zou bij de eerste ongelijkheid opgeven. Op [7, 3, 9] zou die een zoekopdracht naar 3 afwijzen na alleen 7 te hebben gezien. Het teruggeven van een mislukt resultaat hoort na de lus, als elke positie is uitgesloten.

Lineair zoeken vereist geen gesorteerde volgorde of voorbereiding. Het werkt met getallen, woorden of records die op een identificatie worden vergeleken. Een versie voor gesorteerde gegevens kan stoppen zodra ze voorbij de mogelijke positie van de zoekwaarde komt: in [2, 5, 8, 12] is het zien van 8 genoeg om 6 uit te sluiten. De code hierboven blijft bewust zoeken tot ze een overeenkomst vindt of het einde bereikt.

Verwante taken gebruiken dezelfde doorloop maar een andere stopregel. Om elk voorkomen te tellen, elke overeenkomende index te verzamelen en een grootste element te vinden, moet je de hele lijst bekijken; bij het zoeken naar de eerste overeenkomst mag je eerder terugkeren.

Binair zoeken gebruikt de gesorteerde volgorde om posities uit te sluiten zonder ze afzonderlijk te controleren. De invoer moet in oplopende volgorde gesorteerd zijn. Ook moet het mogelijk zijn snel een element op een gekozen index te bereiken, zoals bij een array of Pythonlijst.

Houd een interval met beide grenzen bij

low en high geven de eerste en laatste nog mogelijke positie aan, inclusief beide grenzen. Begin met low = 0 en high = len(items) - 1. Kies de middelste index door naar beneden af te ronden. Als de middelste waarde te klein is, is elke waarde links daarvan ook te klein; verplaats low voorbij het midden. Is die te groot, verplaats high dan tot net vóór het midden.

def binary_search(items, target):
    low = 0
    high = len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

// deelt en rondt naar beneden af. De lus omvat ook het geval low == high, omdat er dan nog één ongecontroleerde positie over is. Als low > high, is het interval leeg.

Doorloop een gevonden en een ontbrekende waarde

Gebruik [3, 8, 12, 17, 23, 31, 42, 56, 64, 77, 85], met indexen 0 tot en met 10. Om 64 te vinden is de eerste middelste index 5, met waarde 31. Omdat 31 te klein is, zet je low = 6. De volgende middelste index is 8, met waarde 64. Geef na twee controles van het middelste element 8 terug.

Zoek je in dezelfde lijst naar 20, dan krijg je:

Nu is het interval leeg, dus geef je -1 terug. Dit is een onderbouwde melding dat de waarde ontbreekt: de gesorteerde volgorde rechtvaardigde elk uitgesloten deel.

Waarom is dit snel?

Na elke controle zonder overeenkomst blijft hoogstens de helft van het interval over. Voor een niet-lege lijst is het maximale aantal controles van een middelste element $\lfloor {\log }_{2}n\rfloor +1$. De logaritme met grondtal 2 beschrijft herhaald halveren: $2^{10}=1.024$, dus zijn voor duizend elementen hoogstens 10 controles nodig; voor een miljoen hoogstens 20. Eén controle in deze Pythoncode kan twee vergelijkingen maken, == en <. Controles en vergelijkingen zijn verschillende teleenheden.

Voorwaarden en grensfouten

De gesorteerde volgorde is essentieel. Als je in [9, 2, 7, 4, 1] naar 2 zoekt, ziet de methode eerst 7 en sluit ze het rechterdeel uit. Daarna ziet ze 9 en sluit ze de resterende overeenkomst op index 1 uit. Snelle toegang tot het midden is ook belangrijk: als je schakels moet volgen om het midden van een gekoppelde lijst te bereiken, gaat het snelheidsvoordeel van de arrayversie verloren.

Sluit na een controle zonder overeenkomst altijd het gecontroleerde midden uit. Met low = mid kan [10, 20] bij het zoeken naar 20 oneindig onveranderd blijven. Met while low < high sla je de laatste kandidaat over en faalt het zoeken naar 5 in [5]. Bij een lege lijst is high = -1, zodat de correcte lus nooit begint.

Bij dubbele waarden geeft deze versie een willekeurige overeenkomende index terug. Zoeken naar 4 in [2, 4, 4, 4, 9] geeft direct index 2 terug; om de eerste vindplaats te vinden is een aangepaste zoekmethode nodig die na een overeenkomst links verder zoekt.

Sorteren zet elementen op volgorde volgens een gekozen sleutel. Bij getallen in oplopende volgorde is elk element kleiner dan of gelijk aan het volgende. “Niet-dalend” laat ruimte voor gelijke buren: [2, 5, 5, 9] is gesorteerd. Aflopende volgorde keert de richting om.

Controleer twee voorwaarden

Een correcte sortering moet uitvoer opleveren die op volgorde staat en precies de oorspronkelijke elementen bevat, met behoud van elke herhaling. [3, 1, 2] sorteren tot [1, 2, 3] lukt. Zowel [1, 2] als [1, 1, 3] is fout, ook al staan de buren op volgorde. De eerste lijst verliest een element; de tweede verandert welke elementen voorkomen. Een herschikking die alle voorkomens behoudt, heet een permutatie.

Bij een record is de sleutel alleen het veld dat voor de vergelijking wordt gebruikt. Steden kun je sorteren op naam of inwonertal. Het hele stadsrecord beweegt mee als de sleutel met het inwonertal beweegt; als je de naam ervan losmaakt, raken de gegevens beschadigd.

Tekstvolgorde hangt af van de sleutel

Een gewone tekstvergelijking volgt tekencodes, één teken tegelijk. In ASCII en Unicode gebruiken A–Z de codes 65–90 en a–z de codes 97–122. Daardoor komt “Zebra” bij een gewone vergelijking vóór “appel”. Door kopieën in kleine letters te vergelijken kun je voor deze voorbeelden een volgorde krijgen die geen onderscheid maakt tussen hoofdletters en kleine letters.

Ook cijfers in tekst gedragen zich als tekens. “10” komt bij het sorteren vóór “9”, omdat het eerste teken “1” is. Een numerieke sleutel zet die tekenreeksen om in de getallen die ze voorstellen, zodat 9 vóór 10 komt. Bepaal wat de gegevens betekenen voordat je de vergelijking kiest.

Verplaats waarden zonder ze te verliezen

Een verwisseling wisselt twee posities om. Een tijdelijke variabele beschermt de waarde die anders zou worden overschreven:

temp = items[i]
items[i] = items[j]
items[j] = temp

Python staat ook items[i], items[j] = items[j], items[i] toe. Als je de twee toekenningen schrijft zonder de eerste waarde te bewaren, verandert [4, 7] in [7, 7]. Bubblesort en selectionsort verplaatsen elementen door te verwisselen; mergesort kopieert elementen naar samengevoegde uitvoer.

Stabiliteit en geheugen

Een stabiele sortering behoudt de oorspronkelijke volgorde van records met gelijke sleutels. Begin met Ana 85, Ben 92, Cara 85, in alfabetische volgorde. Een stabiele aflopende sortering op score levert Ben 92, Ana 85, Cara 85 op. Ana blijft vóór Cara staan. Zo kan een latere sortering op score een eerdere alfabetische volgorde binnen elke scoregroep behouden. De ingebouwde sorteerfunctie van Python is stabiel.

Een in-placesortering herschikt de bestaande lijst met slechts enkele extra variabelen, onafhankelijk van de lengte. De hier behandelde methoden bubblesort en selectionsort werken in place. De gebruikelijke mergesort heeft extra opslag nodig die evenredig is met het aantal elementen. Stabiliteit en geheugen beschrijven verschillende eigenschappen: een sortering kan in place werken en toch instabiel zijn.

Meet wanorde met inversies

Een inversie is een paar posities waarbij de sleutel van een eerder element groter is dan die van een later element. In [5, 1, 4, 2, 8] zijn de inversies (5, 1), (5, 4), (5, 2) en (4, 2): vier in totaal. De elementen van een paar hoeven geen buren te zijn.

Een gesorteerde lijst heeft nul inversies. Een omgekeerde lijst met $n$ verschillende elementen heeft er $n(n-1)\mathrm{/}2$, het maximum. Gelijke sleutels vormen nooit een inversie: [3, 3, 1] heeft er twee, één voor elke 3 vóór 1. Inversies tellen is nuttig bij het uitleggen van het aantal verwisselingen bij bubblesort.

Bubblesort vergelijkt aangrenzende elementen van links naar rechts. Als het linker element groter is, verwisselt het algoritme het paar. Elke keer door de lijst gaan is een doorgang. Een groot element kan tijdens één doorgang herhaaldelijk naar rechts bewegen, totdat het grootste resterende element zijn definitieve positie bereikt.

Volg de eerste doorgang

Begin met [5, 1, 4, 2, 8]:

1. Vergelijk 5 en 1; verwissel ze voor [1, 5, 4, 2, 8].
2. Vergelijk 5 en 4; verwissel ze voor [1, 4, 5, 2, 8].
3. Vergelijk 5 en 2; verwissel ze voor [1, 4, 2, 5, 8].
4. Vergelijk 5 en 8; laat ze staan.

De doorgang maakt vier vergelijkingen en drie verwisselingen. Het grootste element, 8, staat op zijn plaats. De rest is nog ongesorteerd: 4 staat vóór 2. Eén doorgang garandeert de definitieve positie van het maximum, niet de volgorde van elk element.

Doorgang 2 heeft alleen de eerste vier posities nodig. Vergelijk 1 met 4, verwissel daarna 4 met 2 en vergelijk vervolgens 4 met 5. Dat geeft [1, 2, 4, 5, 8] na nog eens drie vergelijkingen en één verwisseling. Doorgang 3 vergelijkt 1 met 2 en 2 met 4. Er zijn geen verwisselingen, wat bevestigt dat de lijst gesorteerd is. Totaal: negen vergelijkingen en vier verwisselingen.

Verkort elke doorgang en stop vroegtijdig

def bubble_sort(items):
    n = len(items)
    for p in range(n - 1):
        swapped = False
        for j in range(n - 1 - p):
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
                swapped = True
        if not swapped:
            break

Doorgangsteller p begint bij nul. De grootste waarde van j is n - 2 - p, zodat j + 1 binnen het ongesorteerde deel blijft. Zet swapped aan het begin van elke doorgang terug; een verwisseling in een eerdere doorgang zegt niets over de vraag of in de huidige doorgang een element is verplaatst.

Na elke doorgang staat één positie extra aan de rechterkant definitief vast. Een doorgang zonder verwisselingen bewijst dat alle vergeleken buren op volgorde staan. Het al vaststaande einddeel staat ook op volgorde, dus kan het algoritme stoppen. De bevestigende doorgang telt nog steeds mee als werk.

Vergelijk het beste en slechtste geval

Voor een gesorteerde niet-lege lijst maakt de versie met vroegtijdige beëindiging $n-1$ vergelijkingen en nul verwisselingen. Op een omgekeerde lijst met verschillende elementen maakt ze

vergelijkingen en evenveel verwisselingen. Vijf elementen vereisen er 10; 1.000 elementen vereisen er 499.500. Zonder vroegtijdig stoppen zou het uitgewerkte voorbeeld met vijf elementen ook de laatste doorgang met één vergelijking uitvoeren en op 10 vergelijkingen uitkomen.

Elke verwisseling verwijdert precies één inversie. De vier inversies in de oorspronkelijke uitgewerkte lijst verklaren de vier verwisselingen. Gelijke buren blijven staan omdat de test > gebruikt. Daardoor is deze versie stabiel en werkt ze in place. Als je > vervangt door >=, kan de volgorde van records met gelijke sleutels omkeren.

De positie is ook van belang als er weinig inversies zijn. [5, 1, 2, 3, 4] gebruikt vier verwisselingen en een tweede doorgang om de volgorde te bevestigen, voor zeven vergelijkingen. [2, 3, 4, 5, 1] heeft ook vier verwisselingen nodig, maar de 1 kan per doorgang maar één keer naar links bewegen. Er zijn alle vier de doorgangen en 10 vergelijkingen nodig.

Selectionsort bouwt links een gesorteerd begindeel op. Elke doorgang vindt het kleinste element in het resterende einddeel en verwisselt dat met het element op de volgende positie van het begindeel. De doorloop vindt de positie; de verwisseling gebeurt na de doorloop.

Onthoud een index

Begin op positie i met smallest = i. Vergelijk elk later element met items[smallest]. Werk smallest alleen bij als er een kleiner element verschijnt. Wissel na afloop van de doorloop items[i] en items[smallest] om.

def selection_sort(items):
    n = len(items)
    for i in range(n - 1):
        smallest = i
        for j in range(i + 1, n):
            if items[j] < items[smallest]:
                smallest = j
        if smallest != i:
            items[i], items[smallest] = items[smallest], items[i]

Als je alleen de kleinste waarde onthoudt, heb je de positie niet voor de verwisseling. Als je de doorloop bij index 0 begint, bekijk je de al geplaatste elementen opnieuw; de verdere zoektocht begint direct na i.

Doorloop de doorgangen

Begin met [29, 10, 14, 37, 13].

Het derde minimum staat al op zijn plaats, dus bewegen er geen waarden. Na vier doorgangen moet het laatste element het grootste zijn; het heeft geen afzonderlijke doorgang nodig. Er zijn 10 vergelijkingen en drie verwisselingen die elementen verplaatsen. De voorwaarde in de code slaat verwisselingen van een positie met zichzelf over; als je die voorwaarde weglaat, blijft het resultaat hetzelfde.

Vergelijkingen en verwisselingen hebben verschillende kosten

Selectionsort maakt altijd $n(n-1)\mathrm{/}2$ vergelijkingen tussen elementen: elke doorgang moet het hele resterende einddeel bekijken om het minimum te vinden. Het totaal is 10 voor vijf elementen of 499.500 voor 1.000, ook bij al gesorteerde invoer. Een doorloop die de onthouden index niet verandert, stelt het minimum van die doorgang vast, maar garandeert in het algemeen niet dat het resterende einddeel op volgorde staat.

Voor een niet-lege lijst is er hoogstens één verwisseling die elementen verplaatst per doorgang, dus hoogstens $n-1$ in totaal. Lege invoer vereist geen doorgangen of verwisselingen. Bubblesort kan $n(n-1)\mathrm{/}2$ verwisselingen nodig hebben op een omgekeerde lijst met verschillende elementen. Als het verplaatsen van grote records veel meer kost dan het vergelijken van hun sleutels, kan het kleine aantal verwisselingen van selectionsort ondanks de vele vergelijkingen van belang zijn. Als je tijdens de doorloop bij elk nieuw minimum verwisselt, gaat dat voordeel verloren.

Gelijke sleutels kunnen van volgorde veranderen

Deze methode met verwisselingen werkt in place, maar is instabiel. Geef records met gelijke sleutels de labels 4a en 4b zodat hun identiteit zichtbaar is. Begin je met [4a, 4b, 1], dan verwisselt de eerste doorgang 4a en 1, wat [1, 4b, 4a] oplevert. De gelijke sleutels hebben hun oorspronkelijke volgorde omgekeerd, hoewel het algoritme ze nooit rechtstreeks als ongelijk heeft vergeleken. Het eerste minimum dat tijdens een doorloop wordt gevonden behouden, voorkomt niet dat een verwisseling over een grotere afstand een record met gelijke sleutel passeert.

Samenvoegen combineert twee al gesorteerde lijsten tot één gesorteerde uitvoer. Houd bij elke invoerlijst een positiemarkering bij het eerste ongebruikte element. Vergelijk die twee elementen, kopieer het kleinste en schuif alleen de bijbehorende markering op.

Kies het volgende kleinste element

Voeg [3, 27, 38, 43] samen met [9, 10, 82]:

De linker lijst is nu leeg. Kopieer de resterende 82 zonder nog een vergelijking tussen elementen. Het resultaat is [3, 9, 10, 27, 38, 43, 82], met zes vergelijkingen. Het resterende lijstdeel kopiëren hoort bij het algoritme: als je stopt wanneer de vergelijkingen stoppen, gaan gegevens verloren.

Waarom kan de methode elementen achter de eerste ongebruikte elementen negeren? Elk eerste ongebruikte element is het kleinste resterende element van de eigen lijst. Het kleinste van die twee is daarom het kleinste resterende element in totaal. Deze redenering blijft gelden nadat een markering opschuift, omdat de ongebruikte delen gesorteerd blijven.

Lees de code voor samenvoegen

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

append voegt één element toe. Een deel zoals left[i:] bevat het ongebruikte resterende lijstdeel en extend kopieert de elementen daarvan. Als de lus eindigt, kan hoogstens één ongebruikt resterend lijstdeel niet leeg zijn. Als een invoerlijst leeg begint, maakt de lus nul vergelijkingen en wordt de andere lijst intact gekopieerd.

Tel vergelijkingen en opslag

Voor twee niet-lege lijsten met lengtes $m$ en $k$ zijn hoogstens $m+k-1$ vergelijkingen van eerste ongebruikte elementen nodig. Elke vergelijking plaatst één element en minstens het laatste element kan zonder vergelijking worden gekopieerd. Het kleinst mogelijke aantal vergelijkingen bij het samenvoegen is de lengte van de kortste lijst: [1, 2, 3] samenvoegen met [4, 5, 6] kost drie vergelijkingen voordat de linkerkant leeg is.

Het totale kopieerwerk groeit met $m+k$, ook als de vergelijkingen vroeg eindigen, omdat elk element in de uitvoer moet voorkomen. De nieuwe lijst heeft ook ruimte nodig voor $m+k$ elementen. Het aantal vergelijkingen, het kopieerwerk en de extra opslag meten verschillende delen van dezelfde bewerking.

Ga om met gelijke sleutels en invoervolgorde

De test <= neemt bij gelijke sleutels het element van links. Als de twee invoerlijsten uit opeenvolgende delen van een oorspronkelijke lijst komen, blijft zo het eerdere record vóór het latere record met gelijke sleutel staan. Dit is de regel voor gelijke sleutels die nodig is voor stabiele mergesort.

De eis dat de invoer gesorteerd is, staat vast. Als je [5, 1] samenvoegt met [3], kopieert de methode 3 en daarna het resterende lijstdeel [5, 1], wat [3, 5, 1] oplevert. De regel voor het eerste ongebruikte element faalde omdat 5 niet de kleinste resterende waarde in de eigen invoerlijst was.

Mergesort lost een grote sorteertaak op door die in kleinere sorteertaken te splitsen. Dit is verdeel en heers: verdeel de lijst, sorteer elke helft en voeg de gesorteerde helften samen.

Stop met splitsen bij het basisgeval

Een functie is recursief als ze zichzelf aanroept. Mergesort roept zichzelf aan op kortere lijsten. Het basisgeval geeft een lijst met nul of één element ongewijzigd terug, omdat zo’n lijst al gesorteerd is.

def merge_sort(items):
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])
    return merge(left, right)

De delen verdelen de invoer zonder elementen te verliezen. Bij een oneven lengte heeft de rechterkant één element meer: [6, 2, 9, 4, 1, 7, 3] splitst in [6, 2, 9] en [4, 1, 7, 3]. Beide helften zijn korter, dus bereiken recursieve aanroepen uiteindelijk het basisgeval. Een basisgeval alleen zou terminatie niet garanderen als een aanroep de oorspronkelijke lijst steeds aan zichzelf bleef doorgeven.

Bouw de gesorteerde lijst weer op

Doorloop [38, 27, 43, 3, 9, 82, 10, 15]. De lijst splitst in twee helften van vier elementen, daarna vier delen van twee elementen en daarna afzonderlijke elementen. Splitsen herschikt de waarden niet. De volgorde wordt tijdens het samenvoegen opgebouwd:

1. Voeg afzonderlijke elementen samen tot [27, 38], [3, 43], [9, 82] en [10, 15]. Elk paar kost één vergelijking: vier in totaal.
2. Voeg paren samen tot [3, 27, 38, 43] en [9, 10, 15, 82]. Elk kost drie vergelijkingen: zes in totaal.
3. Voeg die helften samen tot [3, 9, 10, 15, 27, 38, 43, 82]. Dit kost zeven vergelijkingen.

De volledige sortering kost $4+6+7=17$ vergelijkingen tussen elementen. Tel niet alleen de laatste samenvoeging: de gesorteerde helften moesten eerst worden gemaakt. Het voorbeeld met zeven elementen hierboven wordt met deze splitsingsregel in 14 vergelijkingen gesorteerd tot [1, 2, 3, 4, 6, 7, 9].

Tel niveaus en werk per niveau

Voor acht elementen bereik je door halveren na drie niveaus afzonderlijke elementen, omdat $2^3=8$. In het algemeen zijn er ongeveer ${\log }_{2}n$ samenvoegingsniveaus. Over een volledig niveau verwerken de samenvoegingen gezamenlijk alle $n$ elementen. Elk niveau doet dus werk dat evenredig is met $n$, wat leidt tot groei als $n{\log }_{2}n$.

Voor acht elementen is $n{\log }_{2}n=24$ een nuttige ruime bovengrens voor vergelijkingen, niet het exacte aantal. De uitgewerkte lijst gebruikte er 17; een al gesorteerde of omgekeerde lijst met acht elementen gebruikt er 12. De invoervolgorde verandert wanneer bij een samenvoeging één kant opraakt, maar elke lijst doorloopt nog steeds de niveaus van splitsen en samenvoegen. De groei van het aantal vergelijkingen blijft bij deze versie in zowel het beste als het slechtste geval $n\log n$.

Voor een miljoen elementen geven ongeveer 20 niveaus ongeveer 20 miljoen vergelijkingen als schatting van de bovengrens. Selectionsort gebruikt er ongeveer 500 miljard. Het verschil groeit snel met de invoergrootte.

Houd rekening met de extra uitvoerruimte

De gewone mergesort met lijsten heeft extra opslag nodig die evenredig is met $n$. Door bij gelijke sleutels het eerste ongebruikte element van links te kiezen, is de sortering stabiel.

Een gemeten uitvoeringstijd hangt af van de machine en het programma. Een aantal stappen beschrijft het werk van het algoritme met behulp van een gekozen herhaalde bewerking. De invoergrootte, geschreven als $n$, is het aantal elementen dat wordt verwerkt.

Kies de bewerking voordat je telt

Bij zoeken en sorteren zijn vergelijkingen tussen elementwaarden meestal een bruikbare basisbewerking. Tel verwisselingen apart als het verplaatsen van gegevens van belang is. Bij binair zoeken is het handig om controles van een middelste element te tellen. In de Pythonversie toetst een controle zonder overeenkomst zowel op gelijkheid als op kleiner zijn en kan die dus twee vergelijkingen tussen elementen omvatten.

Deze aantallen beschrijven herhaalde bewerkingen, geen regels code. Eén regel binnen een lus kan een miljoen keer worden uitgevoerd; verschillende regels voor de voorbereiding worden misschien elk één keer uitgevoerd.

Onderscheid gevallen bij dezelfde grootte

Het beste geval kost de minste stappen van alle geldige invoer met grootte $n$. Het slechtste geval kost de meeste en biedt een garantie. Het gemiddelde geval neemt het gemiddelde over een bepaalde verdeling van invoer.

Voor een niet-lege lijst heeft lineair zoeken één vergelijking nodig als de zoekwaarde vooraan staat en $n$ als die achteraan staat of ontbreekt. Het gemiddelde voor een succesvolle zoekopdracht is $(n+1)\mathrm{/}2$ als de eerste positie met een overeenkomst even waarschijnlijk elke positie kan zijn. Het woord “gemiddelde” vereist die verdeling; het betekent niet voor elk algoritme het midden tussen het beste en slechtste aantal.

Zet lussen om in aantallen

Eén vergelijking per element bij een volledige doorloop geeft $n$ vergelijkingen. Twee volledig geneste lussen die elk $n$ keer worden uitgevoerd, voeren hun gemeenschappelijke inhoud $n^2$ keer uit. Een ander patroon met geneste lussen vergelijkt elk paar slechts één keer:

for i in range(n):
    for j in range(i + 1, n):
        compare(items[i], items[j])

De eerste herhaling van de buitenste lus vergelijkt het element met $n-1$ latere elementen. De volgende vergelijkt met $n-2$ en de laatste vergelijkt met geen enkel element. Het totaal is

Schrijf de som vooruit en achteruit. Elk paar boven elkaar telt op tot $n$ en er zijn $n-1$ van die paren. Hun totaal is $n(n-1)$, tweemaal de oorspronkelijke som. Voor vijf elementen is $4+3+2+1=10$; voor 1.000 is het aantal paren 499.500.

Herken herhaald halveren

Een lus die het resterende werk halveert, kost ongeveer ${\log }_{2}n$ herhalingen. Eén miljoen komt na 20 halveringen voor het eerst op 1 of lager uit: $2^{19}=524.288$ en $2^{20}=\mathrm{1.048.576}$ liggen aan weerszijden van een miljoen. Dit verschilt sterk van telkens maar één element verwijderen.

Houd bij groeivergelijkingen de snelst groeiende term over. Het aantal paren is $n^2\mathrm{/}2-n\mathrm{/}2$. Bij $n=1.000$ zijn de termen 500.000 en 500, dus bepaalt de kwadratische term de groei. Door de kleinere term en de constante factor weg te laten beschrijf je de groeifamilie; het exacte aantal van 499.500 wordt daardoor geen exact aantal van één miljoen.

Een groeisnelheid beschrijft hoe de hoeveelheid werk verandert als de invoer groter wordt. Ze helpt algoritmen te vergelijken buiten de specifieke grootte die in één doorloop is gebruikt.

Lees de gebruikelijke families

Bij exponentiële groei verdubbelt het aantal al als er maar één element bijkomt: $2^{n+1}=2\times 2^n$. De invoer verdubbelen is een veel grotere verandering dan er één element aan toevoegen.

Vergelijk groottes met getallen

Voor invoer van 10, 100, 1.000 en één miljoen elementen is ${\log }_{2}n$ ongeveer 3,3; 6,6; 10 en 20. De bijbehorende waarden van $n{\log }_{2}n$ zijn ongeveer 33, 664, 9.966 en 20 miljoen. De kwadratische waarden zijn 100, 10.000, één miljoen en één biljoen.

Logaritmische groei is niet “de helft van de lijst”. Voor een miljoen elementen kost herhaald halveren slechts ongeveer 20 stappen. Als de invoer stijgt van 1.000 naar 2.000, stijgt $n{\log }_{2}n$ van ongeveer 9.966 naar 21.932, een factor van ongeveer 2,2. De logaritme verandert ook, dus groeit het aantal iets sneller dan lineair.

Exponentieel werk wordt snel groot. $2^{10}=1.024$ en $2^{20}$ is ongeveer een miljoen. Bij een miljard stappen per seconde kosten $2^{50}$ stappen nog steeds ongeveer 13 dagen. Eén extra element verdubbelt die tijd.

Gebruik informele O-notaties

Programmeurs duiden deze families doorgaans aan met $O(1)$, $O(\log n)$, $O(n)$, $O(n\log n)$, $O(n^2)$ en $O(2^n)$. Hier geven ze de gebruikelijke groeifamilie voor het slechtste geval aan. Spreek $O(n^2)$ uit als “orde n kwadraat”. De notatie laat constante factoren en termen van lagere orde weg: $n(n-1)\mathrm{/}2$ vergelijkingen behoort tot de kwadratische familie.

Een O-notatie is geen exacte uitvoeringstijd of aantal seconden. Ze beweert ook niet dat elke invoer het aantal van het slechtste geval gebruikt. Bubblesort met vroegtijdige beëindiging heeft een lineair beste geval, maar een kwadratisch slechtste geval.

Vind het omslagpunt

Stel dat methode A $100n$ stappen kost en methode B $n^2$. Bij 50 elementen kost A 5.000 stappen en B 2.500. Bij 100 kosten beide 10.000. Bij 1.000 kost A 100.000 en B één miljoen. De langzamere groei van A overwint uiteindelijk de grotere constante factor.

De snelheid van hardware verandert de schaal zonder de familie te veranderen. Een computer die 100 keer zo snel is, geeft een kwadratische methode ruimte voor slechts 10 keer zoveel elementen in dezelfde tijd, want $(10n{)}^2=100n^2$. Een lineaire methode zou er 100 keer zoveel kunnen verwerken. Bij een kleine taak kunnen voorbereiding en constanten overheersen; bij grote invoer wordt de groei doorslaggevend.

Met een bekende uitvoeringstijd en een groeipatroon kun je voorspellen hoe een grotere taak zich gedraagt. De voorspelling is een schatting, omdat de werkelijke tijd ook afhangt van de implementatie, het geheugen, de hardware en ander werk op de machine.

Schaal eerst de invoer en dan de tijd

Bij lineair werk vermenigvuldig je de tijd met de verhouding tussen de invoergroottes. Als een zoekopdracht in het slechtste geval bij één miljoen elementen 3 milliseconden kost, kosten tien miljoen elementen onder vergelijkbare omstandigheden ongeveer 30 milliseconden.

Bij kwadratisch werk kwadrateer je de verhouding. Stel dat selectionsort 2 seconden kost voor 50.000 elementen. Verdubbeling naar 100.000 elementen geeft

seconden. Bij een toename naar 500.000 elementen wordt de invoergrootte met 10 vermenigvuldigd, dus is de geschatte tijd $2\times {10}^2=200$ seconden. De tijd met 10 vermenigvuldigen zou het algoritme ten onrechte als lineair behandelen.

Bij groei volgens $n{\log }_{2}n$ gebruik je de verhouding tussen beide volledige uitdrukkingen. Verdubbeling van grote invoer kost iets meer dan tweemaal zoveel, omdat de logaritme met het aantal elementen meegroeit.

Reken terug vanuit een tijdsbudget

Gebruik dezelfde kwadratische referentiemeting: 2 seconden voor 50.000 elementen. Een budget van 32 seconden staat 16 keer zoveel tijd toe. De invoer kan groeien met de wortel van 16, dat is 4, tot ongeveer 200.000 elementen. Controleer de richting door in te vullen: viermaal zoveel invoer voorspelt 16 keer zoveel tijd, van 2 seconden naar 32 seconden.

Vergelijk algoritmen bij een grote invoer

Voor één miljoen elementen maakt selectionsort 499.999.500.000 vergelijkingen, ongeveer 500 miljard. Mergesort heeft er hoogstens ongeveer 20 miljoen nodig. Bij een hypothetisch miljard vergelijkingen per seconde komen die aantallen overeen met ongeveer 500 seconden tegenover 0,02 seconden, een verschil van grofweg een factor 25.000. Deze berekening gaat uit van gelijke kosten per vergelijking om het effect van het algoritme afzonderlijk te bekijken; gemeten programma’s besteden ook tijd aan verplaatsingen en geheugentoegang.

Test een voorspelling van de groei

Meet de uitvoeringstijd van hetzelfde programma bij verschillende groottes die steeds verdubbelen, zoals 10.000, 20.000 en 40.000 elementen. Deel elke tijd door de vorige tijd. Verhoudingen rond 2 wijzen op lineaire groei; iets boven 2 wijst op $n\log n$; rond 4 wijst op kwadratische groei.

Houd de machine en meetmethode gelijk. Herhaal de metingen en gebruik groottes waarbij de opstarttijd niet overheerst. Vergelijk gelijke gevallen: bij de ene grootte op de eerste positie zoeken en bij een andere tevergeefs zoeken zou invoereffecten met groei vermengen. Voor bubblesort hebben gesorteerde en omgekeerde lijsten verschillende gevalsaanduidingen nodig.

Als verdubbelende groottes 0,04, 0,16 en 0,64 seconden opleveren, zijn beide verhoudingen 4. Dat ondersteunt een kwadratisch model over dat bereik. Eén verhouding met veel meetruis is zwakker bewijs dan een herhaald patroon. Aantallen stappen voor een bepaalde doorloop kunnen exact zijn; bij een voorspelling in seconden hoort “ongeveer” en moet je die toetsen aan metingen.

Een correct algoritme stopt bij elke geldige invoer en produceert de vereiste uitvoer. Een specificatie vermeldt de invoervoorwaarde en het beloofde resultaat. Bij binair zoeken is de preconditie een oplopende gesorteerde volgorde. De postconditie is een overeenkomende index, of -1 precies als de zoekwaarde ontbreekt.

Gebruik een invariant om stappen te verbinden

Een lusinvariant is een uitspraak die geldt voordat de lus begint en door elke herhaling behouden blijft. Een correctheidsargument controleert of de invariant aan het begin geldt, behouden blijft en wat die bij het einde van de lus impliceert. Een afzonderlijk terminatieargument laat zien dat de lus uiteindelijk eindigt.

Gebruik voor selectionsort deze invariant: vóór doorgang i bevatten de eerste i posities de i kleinste elementen op volgorde.

1. Begin: vóór doorgang 0 is het begindeel leeg. Het voldoet al aan de uitspraak.
2. Behoud: de doorgang vindt het kleinste resterende element. Door dat daarna te plaatsen, wordt het gesorteerde begindeel één element langer en is het element minstens even groot als elk eerder geplaatst element.
3. Einde: na hoogstens $n-1$ doorgangen blijft alleen het grootste element buiten het begindeel over. De hele lijst is gesorteerd.

Elke verplaatsing is een verwisseling, dus blijft ook de multiverzameling van elementen ongewijzigd. Uitvoer die alleen op volgorde staat, zou niet aan de volledige sorteerspecificatie voldoen.

Bubblesort gebruikt een invariant voor het einddeel: na $k$ doorgangen bevatten de laatste $k$ posities de $k$ grootste elementen op volgorde. De volgende doorgang brengt het grootste ongesorteerde element naar dat einddeel. Een doorgang zonder verwisselingen stelt vast dat het hele resterende deel op volgorde staat, waardoor vroegtijdige beëindiging mogelijk is.

Leg de uitgesloten intervallen bij binair zoeken uit

Gebruik de invariant: als de zoekwaarde voorkomt, ligt minstens één voorkomen binnen het interval van low tot en met high. Aanvankelijk omvat dat interval de hele lijst. Als de middelste waarde te klein is, maakt de gesorteerde volgorde elke waarde op of links van mid ook te klein. Door low bij te werken naar mid + 1 blijven alle mogelijke overeenkomsten behouden. De bijwerking naar high = mid - 1 volgt dezelfde redenering voor te grote waarden.

Bij een overeenkomst voldoet de teruggegeven positie direct aan de postconditie. Als het interval leeg raakt, sluit de invariant uit dat de zoekwaarde ergens in de lijst staat. De invoer blijft gesorteerd omdat de zoekmethode die nooit verandert.

Laat zien waarom de uitvoering stopt

Een afnemende niet-negatieve gehele maat bewijst voortgang naar een einde. Bij binair zoeken neemt het aantal mogelijke posities na elke controle zonder overeenkomst strikt af. De gecontroleerde middenpositie wordt uitgesloten, dus kan de lus niet oneindig hetzelfde interval behouden. Bubblesort en selectionsort maken hoogstens $n-1$ doorgangen bij niet-lege invoer en geen doorgangen bij lege invoer.

Mergesort bereikt lijsten met nul of één element omdat elke recursieve aanroep een kortere lijst gebruikt. Die basisgevallen zijn gesorteerd. Als de kortere aanroepen correct gesorteerde helften teruggeven, neemt de samenvoeging steeds het kleinste resterende element en behoudt ze alle elementen. Zo werkt de correctheid terug tot aan de oorspronkelijke aanroep.

Gebruik tests voor een andere taak

Een test vergelijkt één werkelijk resultaat met één verwacht resultaat. Veel geslaagde gekozen tests geven vertrouwen, terwijl één falende geldige invoer een tegenvoorbeeld is dat correctheid weerlegt. Een algemeen argument met een invariant dekt de onbegrensde familie van mogelijke invoeren die een eindige verzameling voorbeeldtests niet controleert. Testen is vooral nuttig om te controleren of de werkelijke code de methode uit het argument implementeert.

Een randgeval is geldige invoer dicht bij een grens waar je gemakkelijk fouten maakt in aannames en lusgrenzen. Bepaal het verwachte resultaat vanuit de specificatie voordat je de code uitvoert. Anders kan de foutieve uitvoer van een programma ongemerkt je verwachte antwoord worden.

Kies lijsten die grenzen beproeven

Test lege lijsten, lijsten met één en met twee elementen, al gesorteerde en omgekeerde lijsten, herhaalde en uitsluitend gelijke waarden, negatieve getallen en oneven en even lengtes. Neem bij zoekopdrachten de eerste positie, de laatste positie en zoekwaarden op die onder, boven en tussen opgeslagen waarden ontbreken.

Binair zoeken in een lege lijst moet -1 teruggeven zonder een element te benaderen: low = 0 en high = -1 maken het begininterval leeg. Het sorteren van [3, 3, 3] moet drie exemplaren van 3 teruggeven. Een uitvoer van [3] zou op volgorde staan, maar niet alle elementen behouden.

Doorloop de kleinste falende invoer

Binair zoeken met while low < high gaat bij [5] met zoekwaarde 5 de lus niet in. De oplossing is low <= high, omdat een interval met één positie nog een kandidaat bevat. Deze test met één element isoleert de grens duidelijker dan een lange lijst.

Met low = mid zet een zoekopdracht naar 20 in [10, 20] de middenpositie op 0, ziet 10 en laat low op 0 staan. Het interval is bij de volgende herhaling onveranderd. Gebruik low = mid + 1 om een al gecontroleerde positie uit te sluiten. Een lijst met twee elementen en de zoekwaarde achteraan legt deze oneindige lus bloot.

Bubblesort vergelijkt items[j] met items[j + 1]. Bij de eerste doorgang is de laatste geldige linker index n - 2. Doorgaan tot n - 1 leest voorbij de lijst en veroorzaakt de Pythonfout IndexError. Zo’n grensfout van één positie heet een fout van één te veel of te weinig.

Controleer beide beloften over de uitvoer

Controleer bij een sortering de volgorde van aangrenzende elementen en het aantal van elk oorspronkelijk element. Gebruik gelabelde records om stabiliteit te testen. Bij Ana 85, Ben 92, Cara 85 moet Ana vóór Cara blijven staan als een stabiele sortering op score de gelijke scores groepeert. Een controle van alleen de scores zou een verwisseling van die twee records missen.

Genereer ook willekeurige lijsten. Vergelijk hun resultaten met een betrouwbare implementatie zoals sorted van Python. Neem dubbele waarden en verschillende lengtes op in de gegenereerde invoer. Als een test faalt, verklein je de invoer terwijl de fout blijft optreden en doorloop je die daarna met de hand. Bewaar het kleine voorbeeld als regressietest, zodat de herstelde fout detecteerbaar blijft.

Houd de berekening van het midden veilig

Gehele getallen in Python groeien waar nodig, dus loopt (low + high) // 2 niet over. Sommige talen gebruiken gehele getallen met een vaste bitbreedte. Voor zeer grote niet-negatieve indexen kan hun som het bereik dat kan worden opgeslagen overschrijden. Gehele optelling in Java loopt cyclisch over; overloop van gehele getallen met teken in C heeft ongedefinieerd gedrag.

Bereken bij geldige indexen en low <= high in plaats daarvan low + (high - low) // 2. Het verschil is niet-negatief en het resultaat blijft tussen de grenzen. Dit berekent dezelfde naar beneden afgeronde middenpositie zonder de mogelijk overlopende som te vormen. Hier vullen grenswaardetesten en redeneren over de getalrepresentatie van de taal elkaar aan.

Een algoritme past bij een taak als de eisen en kosten aansluiten bij de gegevens en het werk dat wordt gedaan. Denk aan de invoervolgorde, toegang tot posities, het aantal toekomstige bewerkingen, extra geheugen, stabiliteit en de kosten van het verplaatsen van records.

Vergelijk de methoden

Binair zoeken vereist ook een gesorteerde volgorde en snelle toegang tot het midden. Een goede vergelijking bevat die voorwaarden; alleen een klein aantal zoekcontroles laat de kosten weg van het voorbereiden van ongeschikte gegevens.

Bepaal of eerst sorteren loont

Voor één zoekopdracht in een miljoen ongesorteerde elementen kost lineair zoeken hoogstens een miljoen vergelijkingen. Eerst met mergesort sorteren kost ongeveer 20 miljoen vergelijkingen vóór de eerste binaire zoekopdracht, die daarna hoogstens 20 controles van het midden vereist. De voorbereiding overtreft de besparing op die ene zoekopdracht ruimschoots.

Voor 100 zoekopdrachten in een onveranderde lijst kunnen herhaalde lineaire zoekopdrachten 100 miljoen vergelijkingen kosten. Eén keer sorteren en 100 binaire zoekopdrachten uitvoeren kost ongeveer 20 miljoen vergelijkingen plus 2.000 controles van het midden. De voorbereiding wordt hergebruikt, wat het tweede plan aantrekkelijk maakt. Volgens dit globale kostenmodel ligt het omslagpunt rond 20 zoekopdrachten. De schatting hangt af van vergelijkbare bewerkingskosten en doorlopen in het slechtste geval; het is geen universele grens voor het aantal zoekopdrachten.

Weeg volgorde, verplaatsing en geheugen af

Bubblesort kan snel klaar zijn als alleen een paar naburige elementen verkeerd staat. [1, 2, 4, 3, 5] heeft één verwisseling in de eerste doorgang nodig en een tweede doorgang om de volgorde te bevestigen: zeven vergelijkingen. Maar “bijna gesorteerd” garandeert niet dat er weinig doorgangen nodig zijn. Een kleine waarde helemaal rechts kan per doorgang maar één positie naar links bewegen.

De weinige verwisselingen van selectionsort helpen als records verplaatsen kostbaar is. Zowel selectionsort als bubblesort gebruikt slechts een vaste hoeveelheid extra opslag. Mergesort verwerkt grote lijsten met een veel langzamere tijdsgroei, maar de gebruikelijke vorm met lijsten heeft ruimte nodig voor ongeveer nog een lijst vol elementen.

Als records met gelijke sleutels hun eerdere volgorde moeten behouden, kies dan een stabiele methode. Een lijst die al alfabetisch op naam staat, kun je stabiel op cijfer sorteren en tegelijk binnen elke cijfergroep alfabetisch houden. Gewone selectionsort kan die volgorde bij gelijke sleutels verstoren.

Gebruik geteste bibliotheekfuncties

Echte programma’s gebruiken meestal de ingebouwde sorteerfunctie van de taal. De stabiele sortering van Python gebruikt een adaptieve methode op basis van samenvoegen, algemeen bekend als Timsort, die profiteert van volgorde die al in de invoer aanwezig is. sorted(items) geeft een nieuwe lijst terug, terwijl items.sort() de bestaande lijst verandert. Een methode die als API-gedrag een lijst op zijn plaats verandert, kan intern nog steeds tijdelijk werkgeheugen gebruiken; ze hoeft niet te voldoen aan de definitie van vaste extra opslag die voor de eenvoudige sorteringen hierboven wordt gebruikt.

Voor een handvol elementen kan eenvoudige, heldere code belangrijker zijn dan de groei. Vergelijk bij grote verzamelingen het gedrag in het slechtste geval en het geheugen naast de eigenschappen die de taak werkelijk vereist.