Jämför sorteringsmetoder
↑Snabböversikt
Section titled “Snabböversikt”Insättningssortering bygger upp en sorterad del genom att sätta in nästa värde på rätt plats. Mergesortering delar upp listan rekursivt och slår ihop sorterade delar. Resultatet blir detsamma men arbetsmängden kan skilja sig mycket.
| Insättningssortering | Mergesortering | |
|---|---|---|
| Bästa fall | O(n) |
O(n log n) |
| Sämsta fall | O(n²) |
O(n log n) |
| Extra minne för arrayer | O(1) |
O(n) |
| Stabil i vanliga implementationer | Ja | Ja, om lika värden tas från vänster halva först |
Prova samma värden
Section titled “Prova samma värden”JÄMFÖR SORTERINGSMETODER
Samma värden, olika arbete
Vi räknar antalet jämförelser som behövs för att sortera samma lista. Det är en pedagogisk mätning, inte ett tidsmått.
Staplarna visar antalet jämförelser som implementationerna gör. De visar inte körningstid i millisekunder. Prova en sorterad lista och sedan en omvänd lista.
Varför spelar ordningen roll?
Section titled “Varför spelar ordningen roll?”Insättningssortering går bakåt så länge tidigare värden är större än nyckeln. Är allt redan sorterat räcker en jämförelse för varje nytt värde. Är allt bakvänt måste nyckeln flyttas längst till vänster varje gång. Då blir arbetet kvadratiskt.
Mergesortering använder dela-och-härska. Den delar listan till små intervall och jämför sedan främsta återstående värdet i varje sorterad del. Antalet nivåer växer logaritmiskt och varje nivå går igenom alla element.
Kontrollfråga
Section titled “Kontrollfråga”Vilken metod har garanterad O(n log n) tidsåtgång för en vanlig arrayimplementation?
Visa förklaring
Mergesortering delar listan logaritmiskt många gånger och sammanfogar n element per nivå.