- Del som partitioneras
- Pivot
- Jämförda
- Bytta
- På plats
Quicksort
Quicksort väljer en pivot, flyttar varje mindre värde före den och varje annat värde efter den, och sorterar sedan de två sidorna på samma sätt. Pivoten hamnar på sin slutliga plats efter varje partitionering. Välj hur pivoten väljs, spela sorteringen i valfri hastighet eller stega igenom den en jämförelse i taget, och se varför en dålig pivot på en sorterad lista gör quicksort långsam. Tryck på Spela för att se sorteringen, eller använd Steg och Bakåt för att gå en jämförelse i taget. Dra i stegreglaget för att hoppa vart som helst. Rutorna räknar jämförelser, byten och partitioneringar. Välj hur många staplar, hur de börjar, eller skriv dina egna tal, och hur pivoten väljs. 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, eller använd Steg och Bakåt för att gå en jämförelse i taget. Dra i stegreglaget för att hoppa var som helst i sorteringen.
- Välj pivotregel: sista värdet, mittersta värdet, ett slumpat värde eller median av tre. Prova var och en på en sorterad lista.
Så fungerar quicksort
Välj ett värde i delen som ska sorteras som pivot och flytta det till slutet. Gå igenom de andra värdena från vänster till höger; varje värde som är mindre än pivoten byts in i en vänsterdel som växer från början. Byt sedan in pivoten direkt efter vänsterdelen. Allt före den är nu mindre och inget efter den är det, så pivoten står på sin slutliga plats. Sortera delen före den och delen efter den på samma sätt, tills varje del är ett enda värde.
Varför pivoten spelar roll
När pivoten hamnar nära mitten halverar varje partitionering problemet, och jämförelserna växer som n log n: för 40 slumpade värden ungefär 190. När pivoten är det minsta eller största värdet är den ena sidan tom och den andra har allt annat. Med sista värdet som pivot händer det i varje steg på en sorterad eller omvänd lista, och sorteringen kräver n(n − 1)/2 jämförelser, 780 för 40 värden. En slumpad pivot eller medianen av det första, mittersta och sista värdet undviker det i praktiken.
Ofta ställda frågor
Hur fungerar quicksort?
Den väljer en pivot, partitionerar listan så att de mindre värdena kommer före pivoten och resten efter den, och sorterar sedan båda sidorna med quicksort. Efter varje partitionering står pivoten på sin slutliga plats.
Varför är quicksort långsam på en sorterad lista?
Med första eller sista värdet som pivot ger en sorterad lista alltid det minsta eller största värdet som pivot. Ena sidan av partitioneringen blir då tom, så varje partitionering tar bara bort ett värde, och sorteringen kräver n(n − 1)/2 jämförelser. En slumpad pivot eller median av tre löser det i praktiken.
Är quicksort snabbare än mergesort?
Ofta, i praktiken: den sorterar på plats, behöver ingen buffert och dess inre loop är mycket enkel. I genomsnitt gör den något fler jämförelser än mergesort, och dess värsta fall är n², medan mergesort alltid är n log n. Sorteringar i bibliotek, som introsort, börjar med quicksort och byter till heapsort om uppdelningarna blir för ojämna.
Är quicksort stabil?
Nej. En partitionering byter värden över långa avstånd, så lika värden kan byta ordning.
Skickas mina tal någonstans?
Nej. Sorteringen 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