Vinder
Operationer
Færdige

  • Sammenlignet
  • Markeret (mindste, pivot eller nøgle)
  • Byttet eller flyttet
  • På plads
Plads Sortering Sammenligninger eller aflæsninger Ombytninger eller flytninger Operationer

Mere om sorteringsalgoritmer

Sorteringskapløb

Hvilken sorteringsalgoritme er hurtigst? Det afhænger af listen. Sorteringskapløb kører alle otte sorteringsalgoritmer på den samme liste på én gang, i hver sin bane, og tæller hver sammenligning, aflæsning, ombytning og flytning som én operation. Banerne rykker frem, efterhånden som deres optælling stiger, så du kan se de effektive sorteringer blive færdige, mens de langsomme stadig bytter, og se rækkefølgen ændre sig, når listen er næsten sorteret eller omvendt. Tryk på Afspil for at se alle otte sorteringsalgoritmer køre om kap på den samme liste, eller brug Trin og Tilbage for at gå én operation ad gangen. Træk i skyderen for at hoppe hvorhen du vil. Hver sammenligning, aflæsning, ombytning eller flytning tæller som én operation, og hver bane rykker frem, efterhånden som dens egen optælling stiger, så den sortering, der kræver færrest operationer, bliver først færdig. Vælg hvor mange søjler og hvordan de starter, eller skriv dine egne tal. 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, og følg de otte baner. Trin og Tilbage går én operation ad gangen; skyderen hopper til et vilkårligt sted i kapløbet.
  3. Sammenlign resultattabellen, og prøv derefter en næsten sorteret liste og en omvendt liste for at se placeringerne ændre sig.

Sådan fungerer kapløbet

Alle otte sorteringer får den samme liste. Hver sammenligning af to værdier, hvert ciffer eller hver værdi, som radixsortering og tællesortering aflæser, og hver ombytning eller flytning tæller som én operation. På hvert tidspunkt i kapløbet viser hver bane, hvor langt dens sortering er nået med så mange operationer. En sortering, der kræver færre operationer, når hurtigere til enden. Resultattabellen viser sammenligningerne, ombytningerne eller flytningerne og det samlede antal for hver sortering.

Hvad resultaterne viser

Med 40 tilfældige værdier kræver tællesortering omkring 120 operationer, radixsortering omkring 240, quicksort omkring 260 og flettesortering omkring 380. Heapsort følger med omkring 490, mens udvælgelsessortering og indsættelsessortering kræver omkring 820 og boblesortering over 1.100. På en næsten sorteret liste vinder indsættelsessortering med omkring 50, og boblesortering bliver nummer to. På en omvendt liste kræver boblesortering og indsættelsessortering begge 1.560. Tællesortering og radixsortering vinder så tit, fordi disse værdier er små hele tal; på andre data kan de slet ikke bruges.

Ofte stillede spørgsmål

Hvilken sorteringsalgoritme er hurtigst?

Det afhænger af dataene. For små hele tal kræver tællesortering og radixsortering færrest operationer. For generelle data er quicksort og flettesortering hurtigst på tilfældige lister, og indsættelsessortering er hurtigst på lister, der er næsten sorteret. Boblesortering og udvælgelsessortering er langsomme på alt andet end de mindste lister.

Hvad tæller som en operation?

Hver sammenligning af to værdier, hvert ciffer eller hver værdi, som radixsortering og tællesortering aflæser, og hver ombytning eller flytning af en værdi. Det er en enkel model: virkelige køretider afhænger også af hukommelsesadgang og prisen for hver operation.

Hvorfor vinder tællesortering og radixsortering så tit?

Fordi de aldrig sammenligner værdier. De udnytter, at værdierne er små hele tal, så deres arbejde vokser med n plus værdiernes spænd, ikke med n log n. På data, der ikke består af små heltal, kan de ikke bruges.

Hvorfor vinder indsættelsessortering på en næsten sorteret liste?

Fordi dens arbejde er antallet af værdier plus antallet af par i forkert rækkefølge. En næsten sorteret liste har meget få af den slags par, så hver værdi flytter kun en plads eller to.

Bliver mine tal sendt nogen steder hen?

Nej. Kapløbet kører i din browser, og dine seneste indstillinger bliver 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