Sammenligninger
Ombytninger
Partitioneringer

  • Del, der partitioneres
  • Pivot
  • Sammenlignet
  • Byttet
  • På plads

Mere om quicksort

Quicksort

Quicksort vælger en pivot, flytter alle mindre værdier før den og alle andre værdier efter den og sorterer så de to sider på samme måde. Pivoten ender på sin endelige plads efter hver partitionering. Vælg hvordan pivoten vælges, afspil sorteringen i valgfri hastighed eller gå igennem den én sammenligning ad gangen, og se hvorfor en dårlig pivot på en sorteret liste gør quicksort langsom. Tryk på Afspil for at se sorteringen, eller brug Trin og Tilbage for at gå én sammenligning ad gangen. Træk i trinskyderen for at hoppe hvorhen du vil. Felterne tæller sammenligninger, ombytninger og partitioneringer. Vælg hvor mange søjler, hvordan de starter, eller skriv dine egne tal, og hvordan pivoten vælges. Når brættet er valgt, går piletasterne et trin, mellemrumstasten afspiller og sætter på pause, og Home og End hopper til starten og slutningen.

Sådan virker det

  1. Vælg hvor mange søjler og hvordan de starter: tilfældigt, næsten sorteret, omvendt eller med få unikke værdier. Eller skriv dine egne tal.
  2. Tryk på Afspil, eller brug Trin og Tilbage for at gå én sammenligning ad gangen. Træk i trinskyderen for at hoppe til et vilkårligt sted i sorteringen.
  3. Vælg pivotreglen: den sidste værdi, den midterste værdi, en tilfældig værdi eller median af tre. Prøv hver af dem på en sorteret liste.

Sådan virker quicksort

Vælg én værdi i den del, der skal sorteres, som pivot, og flyt den til enden. Gå de andre værdier igennem fra venstre mod højre; hver værdi, der er mindre end pivoten, byttes ind i en venstre del, der vokser fra starten. Byt så pivoten ind lige efter venstre del. Alt før den er nu mindre, og intet efter den er, så pivoten står på sin endelige plads. Sortér delen før den og delen efter den på samme måde, indtil hver del er en enkelt værdi.

Hvorfor pivoten betyder noget

Når pivoten lander tæt på midten, halverer hver partitionering problemet, og sammenligningerne vokser som n log n: for 40 tilfældige værdier cirka 190. Når pivoten er den mindste eller største værdi, er den ene side tom, og den anden har alt det andet. Med den sidste værdi som pivot sker det ved hvert trin på en sorteret eller omvendt liste, og sorteringen kræver n(n − 1)/2 sammenligninger, 780 for 40 værdier. En tilfældig pivot eller medianen af den første, midterste og sidste værdi undgår det i praksis.

Ofte stillede spørgsmål

Hvordan virker quicksort?

Den vælger en pivot, partitionerer listen, så de mindre værdier kommer før pivoten og resten efter den, og sorterer så begge sider med quicksort. Efter hver partitionering står pivoten på sin endelige plads.

Hvorfor er quicksort langsom på en sorteret liste?

Med den første eller sidste værdi som pivot giver en sorteret liste altid den mindste eller største værdi som pivot. Den ene side af partitioneringen er så tom, så hver partitionering fjerner kun én værdi, og sorteringen kræver n(n − 1)/2 sammenligninger. En tilfældig pivot eller median af tre løser det i praksis.

Er quicksort hurtigere end flettesortering?

Ofte, i praksis: den sorterer på stedet, behøver ingen buffer, og dens inderste løkke er meget enkel. I gennemsnit laver den lidt flere sammenligninger end flettesortering, og dens værste tilfælde er n², mens flettesortering altid er n log n. Sorteringer i biblioteker, som introsort, starter med quicksort og skifter til heapsort, hvis opdelingerne bliver for skæve.

Er quicksort stabil?

Nej. En partitionering bytter værdier over lange afstande, så ens værdier kan skifte rækkefølge.

Bliver mine tal sendt nogen steder hen?

Nej. Sorteringen kører i din browser, og dine seneste indstillinger gemmes i denne browsers lokale lager.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Gå til Editor