Bubble sort och insertion sort

En optimerad bubblesortering använder en flagga, swapped: om en fullständig inre genomgång inte utför några byten är arrayen redan sorterad och vi avslutar tidigt. Detta ger O(n) i bästa fall för redan sorterad indata — bubblesorteringens enda verkliga fördel. Utan denna flagga utförs alltid O(n²) jämförelser. Optimeringen med tidigt avbrott är vad intervjuare kontrollerar när de frågar om förbättringar av bubblesortering.

Bubblesorteringens yttre loop körs n-1 gånger. Den inre loopen körs n-1-i gånger per genomgång: (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2 jämförelser. Detta ger O(n²) i genomsnitt och i värsta fall. Med flaggan för tidigt avbrott sjunker bästa fallet till O(n) för sorterad indata. Minneskomplexiteten är O(1) — endast bytet kräver ett tillfälligt byte av variabler. Bubblesortering är stabil: lika element behåller sin inbördes ordning eftersom vi endast byter element som är strikt större.

Insättningssortering efterliknar hur man sorterar en hand med kort: ta upp nästa kort (element) och sätt in det på rätt plats bland de redan sorterade korten till vänster. Invarianten är att arr[0:i] alltid är sorterad. För varje nytt element förskjuter ni större element åt höger för att skapa plats. Den här stabila algoritmen, som arbetar på plats, har O(n²) i värsta fall men O(n) i bästa fall för nästan sorterade data.

Följ insättningssortering på [3, 1, 4, 2]: i=1, key=1, förskjut 3 åt höger → [1, 3, 4, 2]. i=2, key=4, inga förskjutningar → oförändrad. i=3, key=2, förskjut först 4 och sedan 3 åt höger → [1, 2, 3, 4]. Varje element jämförs med elementen till vänster tills rätt plats hittas. Den inre while-loopen utför förskjutningarna med tilldelningar (snabbare än byten eftersom en tilldelning krävs per förskjutning, jämfört med tre för ett byte).

Insättningssorteringens stora styrka är komplexiteten O(n + inversions). En inversion är ett par (i,j) där i < j men arr[i] > arr[j]. För nästan sorterade arrayer med endast några få inversioner är insättningssortering extremt snabb — ibland snabbare än mergesortering i praktiken tack vare sin enkelhet och cachevänliga åtkomstmönster. Pythons Timsort använder insättningssortering på små delarrayer av just den anledningen.

En sorteringsalgoritm är stabil om lika element behåller sin ursprungliga inbördes ordning efter sorteringen. Både bubblesortering och insättningssortering är stabila — de byter aldrig plats på lika element. Stabilitet är viktig när ni sorterar efter flera nycklar i följd: sortera först efter den sekundära nyckeln (stabilt) och sedan efter den primära nyckeln (stabilt), så att ordningen efter den sekundära nyckeln bevaras bland element med samma primärnyckel. Mergesortering är också stabil; heapsortering och quicksort är vanligtvis inte det.

Insättningssorteringens inre loop hittar både rätt position och förskjuter element. Ni kan använda binär sökning för att hitta positionen med O(log i) jämförelser, men förskjutningarna tar fortfarande O(i) tid — den övergripande komplexiteten förblir därför O(n²). Optimeringen minskar antalet jämförelser (användbart för dyra jämförelsefunktioner), men inte det totala antalet operationer. Den här varianten, binär insättningssortering, förekommer i Timsort för små delstorlekar.

I intervjuer bör ni ange jämförelsen med säkerhet: insättningssortering är strikt bättre än bubblesortering — båda har O(n²) i värsta fall och O(1) minne, men insättningssortering utför färre skrivningar (O(n+k) för k inversioner jämfört med O(n²) för bubblesortering), är mer cachevänlig och är det praktiska valet för små n (Timsort använder den). Bubblesorteringens enda verkliga fördel är pedagogisk enkelhet. I produktion bör ni alltid använda språkets inbyggda sortering.

Antalet inversioner i en array är lika med antalet par (i,j) där i < j men arr[i] > arr[j]. Insättningssortering utför exakt lika många förskjutningar som antalet inversioner — en användbar insikt. För att räkna inversioner effektivt (O(n log n)) krävs en modifierad mergesortering. Intervjuare frågar ibland ”hur väl tar er algoritm hänsyn till inversioner?” som en följdfråga vid diskussioner om sortering.

I den här lektionen har ni lärt er: bubblesortering utför n-1 genomgångar, där varje genomgång låter det aktuella maximumet bubbla upp till sin slutliga plats, med O(n²) i värsta fall men O(n) i bästa fall med flaggan för tidigt avbrott, insättningssortering förskjuter element åt höger för att sätta in den aktuella nyckeln på rätt sorterad plats och körs på O(n + inversions) tid, vilket gör den optimal för nästan sorterade data och båda algoritmerna är stabila, använder O(1) minne och har O(n²) i värsta fall — men insättningssortering föredras strikt framför bubblesortering i alla praktiska situationer. Härnäst implementerar vi mergesortering från grunden.