- Jämförda
- Markerade (minsta, pivot eller nyckel)
- Bytta eller flyttade
- På plats
| Plats | Sortering | Jämförelser eller läsningar | Byten eller flyttar | Operationer |
|---|
Sorteringsracet
Vilken sorteringsalgoritm är snabbast? Det beror på listan. Sorteringsracet kör alla åtta sorteringsalgoritmer på samma lista samtidigt, en bana var, och räknar varje jämförelse, läsning, byte och flytt som en operation. Banorna går vidare när deras räkning ökar, så du kan se de effektiva sorteringarna gå i mål medan de långsamma fortfarande byter, och se ordningen ändras när listan är nästan sorterad eller omvänd. Tryck på Spela för att se alla åtta sorteringsalgoritmer tävla på samma lista, eller använd Steg och Bakåt för att gå en operation i taget. Dra i reglaget för att hoppa vart som helst. Varje jämförelse, läsning, byte eller flytt räknas som en operation, och varje bana går vidare när dess egen räkning ökar, så den sortering som behöver färst operationer blir klar först. Välj hur många staplar och hur de börjar, eller skriv dina egna tal. När tavlan är markerad stegar piltangenterna, mellanslag spelar och pausar, och Home och End hoppar till början och slutet.
Hur det fungerar
- Välj antal staplar och startordning: slumpad, nästan sorterad, omvänd eller med få unika värden. Eller skriv dina egna tal.
- Tryck på Spela och följ de åtta banorna. Steg och Bakåt går en operation i taget; reglaget hoppar var som helst i racet.
- Jämför resultattabellen och prova sedan en nästan sorterad och en omvänd lista för att se placeringarna ändras.
Så fungerar racet
Alla åtta sorteringar får samma lista. Varje jämförelse av två värden, varje siffra eller värde som radixsortering och räknesortering läser, och varje byte eller flytt räknas som en operation. I varje ögonblick av racet visar varje bana hur långt dess sortering har kommit med så många operationer. En sortering som behöver färre operationer når slutet tidigare. Resultattabellen visar jämförelserna, bytena eller flyttarna och summan för varje sortering.
Vad resultaten visar
Med 40 slumpade värden behöver räknesortering ungefär 120 operationer, radixsortering ungefär 240, quicksort ungefär 260 och mergesort ungefär 380. Heapsort följer med ungefär 490, medan urvalssortering och insättningssortering behöver ungefär 820 och bubbelsortering över 1 100. På en nästan sorterad lista vinner insättningssortering med ungefär 50, och bubbelsortering kommer tvåa. På en omvänd lista behöver bubbelsortering och insättningssortering båda 1 560. Räknesortering och radixsortering vinner så ofta eftersom de här värdena är små heltal; på andra data går de inte att använda alls.
Ofta ställda frågor
Vilken sorteringsalgoritm är snabbast?
Det beror på datan. För små heltal behöver räknesortering och radixsortering färst operationer. För allmänna data är quicksort och mergesort snabbast på slumpade listor, och insättningssortering är snabbast på listor som är nästan sorterade. Bubbelsortering och urvalssortering är långsamma på alla utom de minsta listorna.
Vad räknas som en operation?
Varje jämförelse av två värden, varje siffra eller värde som radixsortering och räknesortering läser, och varje byte eller flytt av ett värde. Det är en enkel modell: verkliga körtider beror också på minnesåtkomst och vad varje operation kostar.
Varför vinner räknesortering och radixsortering så ofta?
För att de aldrig jämför värden. De utnyttjar att värdena är små heltal, så deras arbete växer med n plus värdenas omfång, inte med n log n. På data som inte består av små heltal går de inte att använda.
Varför vinner insättningssortering på en nästan sorterad lista?
För att dess arbete är antalet värden plus antalet par i fel ordning. En nästan sorterad lista har väldigt få sådana par, så varje värde flyttar bara en plats eller två.
Skickas mina tal någonstans?
Nej. Racet körs i din webbläsare, och dina senaste inställningar sparas i den här webbläsarens lokala lagring.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Gå till Editor