Bubble sort og insertion sort

Boblesortering og indsættelsessortering tager O(n²) i værste fald, så de er upraktiske til store inddata. Alligevel forventer ethvert seriøst algoritmeinterview, at du kan implementere og analysere dem. De lærer dig grundlæggende begreber — sammenligning, ombytning, stabil sortering og adfærd i bedste fald — som også gælder for mere avancerede algoritmer. Interviewere bruger dem til at afprøve, om du kan ræsonnere ud fra løkkeinvarianter og asymptotisk notation helt fra bunden.

Boblesortering gennemløber gentagne gange arrayet og bytter naboelementer, der står i forkert rækkefølge. Efter hvert fulde gennemløb "bobler" det største usorterede element op til sin endelige position til sidst. Efter n-1 gennemløb er hele arrayet sorteret. Navnet kommer fra den måde, større elementer flyder opad på som bobler. Det er den enkleste sorteringsalgoritme at beskrive, men bruges sjældent i praksis.

En optimeret boblesortering bruger et swapped-flag: Hvis et helt indre gennemløb ikke foretager nogen ombytninger, er arrayet allerede sorteret, og vi afslutter tidligt. Det giver O(n) i bedste fald for allerede sorteret inddata — boblesorteringens eneste reelle fordel. Uden dette flag udfører den altid O(n²) sammenligninger. Optimeringen med tidlig afslutning er det, interviewere ser efter, når de spørger til forbedringer af boblesortering.

Boblesorteringens ydre løkke kører n-1 gange. Den indre løkke kører n-1-i gange pr. gennemløb: (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2 sammenligninger. Det giver O(n²) i gennemsnit og i værste fald. Med flaget til tidlig afslutning falder bedste fald til O(n) for sorteret inddata. Pladskompleksiteten er O(1) — kun ombytningen kræver en midlertidig variabel. Boblesortering er stabil: Ens elementer bevarer deres indbyrdes rækkefølge, fordi vi kun bytter strengt større elementer.

Indsættelsessortering efterligner sortering af en hånd kort: Tag det næste kort, altså elementet, og indsæt det på den korrekte position blandt de allerede sorterede kort til venstre. Invarianten er, at arr[0:i] altid er sorteret. For hvert nyt element skal du forskyde større elementer mod højre for at skabe plads. Denne algoritme sorterer på stedet, er stabil, tager O(n²) i værste fald og O(n) i bedste fald for næsten sorterede data.

Følg indsættelsessortering på [3, 1, 4, 2]: i=1, key=1, forskyd 3 mod højre → [1, 3, 4, 2]. i=2, key=4, ingen forskydninger → uændret. i=3, key=2, forskyd først 4 og derefter 3 mod højre → [1, 2, 3, 4]. Hvert element sammenlignes med elementerne til venstre, indtil vi finder den korrekte plads. Den indre while-løkke udfører forskydningerne med tildelinger, hvilket er hurtigere end ombytninger, fordi hver forskydning kræver én tildeling mod tre ved en ombytning.

Indsættelsessorteringens afgørende fordel er kompleksiteten O(n + inversioner). En inversion er et par (i,j), hvor i < j, men arr[i] > arr[j]. For næsten sorterede arrays med kun få inversioner er indsættelsessortering ekstremt hurtig — nogle gange hurtigere end flettesortering i praksis på grund af sin enkelhed og cachevenlige adgangsmåde. Pythons Timsort bruger indsættelsessortering på små delarrays af netop denne grund.

En sorteringsalgoritme er stabil, hvis ens elementer bevarer deres oprindelige indbyrdes rækkefølge efter sorteringen. Både boblesortering og indsættelsessortering er stabile — de bytter aldrig ens elementer. Stabilitet er vigtig, når du sorterer efter flere nøgler i rækkefølge: Sortér først stabilt efter den sekundære nøgle, og sortér derefter stabilt efter den primære nøgle, så rækkefølgen efter den sekundære nøgle bevares blandt elementer med samme primære nøgle. Flettesortering er også stabil; heapsort og quicksort er som regel ikke.

Indsættelsessorteringens indre løkke finder både den korrekte position og forskyder elementerne. Du kan bruge binær søgning til at finde positionen på O(log i) sammenligninger, men forskydningerne tager stadig O(i) tid — så den samlede kompleksitet forbliver O(n²). Optimeringen reducerer antallet af sammenligninger, hvilket er nyttigt ved dyre sammenligningsfunktioner, men ikke antallet af samlede operationer. Denne "binære indsættelsessortering" optræder i Timsort ved små blokstørrelser.

I interviews skal du fremsætte denne sammenligning med sikkerhed: indsættelsessortering er entydigt bedre end boblesortering — begge tager O(n²) i værste fald og bruger O(1) plads, men indsættelsessortering udfører færre skrivninger (O(n+k) for k inversioner mod O(n²) for boblesortering), er mere cachevenlig og er det praktiske valg for lille n, som Timsort også bruger. Boblesorteringens eneste reelle fordel er pædagogisk enkelhed. I produktionskode skal du altid bruge sprogets indbyggede sortering.

Antallet af inversioner i et array er lig med antallet af par (i,j), hvor i < j, men arr[i] > arr[j]. Indsættelsessortering udfører præcis lige så mange forskydninger, som der er inversioner — en nyttig indsigt. Effektiv optælling af inversioner (O(n log n)) kræver en ændret flettesortering. Interviewere spørger nogle gange: 'Hvor godt tager din algoritme højde for inversioner?' som opfølgning på en samtale om sortering.

I denne lektion lærte du, at boblesortering foretager n-1 gennemløb, hvor hvert gennemløb får det aktuelle maksimum på plads, med O(n²) i værste fald, men O(n) i bedste fald med flaget til tidlig afslutning, at indsættelsessortering forskyder elementer mod højre for at indsætte den aktuelle nøgle på den korrekte sorterede position og kører på O(n + inversioner), hvilket gør den optimal til næsten sorterede data, og at begge algoritmer er stabile, bruger O(1) plads og tager O(n²) i værste fald — men indsættelsessortering bør entydigt foretrækkes frem for boblesortering i alle praktiske situationer. Som det næste implementerer vi flettesortering fra bunden.