Câștigător
Operații
Terminate

  • Comparate
  • Marcate (minimul, pivotul sau cheia)
  • Interschimbate sau mutate
  • La locul lor
Locul Sortare Comparații sau citiri Interschimbări sau mutări Operații

Mai multe despre algoritmii de sortare

Cursa sortărilor

Care algoritm de sortare e cel mai rapid? Depinde de listă. Cursa sortărilor rulează toți cei opt algoritmi de sortare deodată pe aceeași listă, fiecare pe culoarul lui, și numără fiecare comparație, citire, interschimbare și mutare ca o operație. Culoarele avansează pe măsură ce cresc contoarele, așa că puteți vedea sortările eficiente terminând în timp ce cele lente încă interschimbă și puteți vedea cum se schimbă ordinea când lista e aproape sortată sau inversată. Apăsați Redare pentru a urmări cum toți cei opt algoritmi de sortare se întrec pe aceeași listă sau Pas și Înapoi pentru a avansa câte o operație. Trageți glisorul ca să săriți oriunde. Fiecare comparație, citire, interschimbare sau mutare contează ca o operație, iar fiecare culoar avansează pe măsură ce crește propriul contor, așa că sortarea care are nevoie de cele mai puține operații termină prima. Alegeți câte bare sunt și cum încep sau introduceți propriile numere. Cu tabla selectată, săgețile avansează câte un pas, bara de spațiu pornește și pune pauză, iar Home și End sar la început și la sfârșit.

Cum funcționează

  1. Alegeți câte bare sunt și cum încep: aleatoriu, aproape sortate, inversate sau cu puține valori distincte. Sau introduceți propriile numere.
  2. Apăsați Redare și urmăriți cele opt culoare. Pas și Înapoi avansează câte o operație; glisorul sare oriunde în cursă.
  3. Comparați tabelul cu rezultate, apoi încercați o listă aproape sortată și una inversată ca să vedeți cum se schimbă clasamentul.

Cum funcționează cursa

Toate cele opt sortări primesc aceeași listă. Fiecare comparație a două valori, fiecare cifră sau valoare citită de sortarea radix și de sortarea prin numărare și fiecare interschimbare sau mutare contează ca o operație. În fiecare moment al cursei, fiecare culoar arată cât de departe a ajuns sortarea lui cu atâtea operații. O sortare care are nevoie de mai puține operații ajunge mai repede la final. Tabelul cu rezultate arată pentru fiecare sortare comparațiile, interschimbările sau mutările și totalul.

Ce arată rezultatele

Pe 40 de valori aleatorii, sortarea prin numărare are nevoie de circa 120 de operații, sortarea radix de circa 240, sortarea rapidă de circa 260, iar sortarea prin interclasare de circa 380. Urmează sortarea prin ansamble cu circa 490, în timp ce sortarea prin selecție și cea prin inserție au nevoie de circa 820, iar metoda bulelor de peste 1.100. Pe o listă aproape sortată câștigă sortarea prin inserție cu circa 50, iar metoda bulelor iese a doua. Pe o listă inversată, metoda bulelor și sortarea prin inserție au nevoie amândouă de 1.560. Sortarea prin numărare și sortarea radix câștigă atât de des pentru că aceste valori sunt numere întregi mici; pe alte date nu pot fi folosite deloc.

Întrebări frecvente

Care algoritm de sortare e cel mai rapid?

Depinde de date. Pentru numere întregi mici, sortarea prin numărare și sortarea radix au nevoie de cele mai puține operații. Pentru date obișnuite, sortarea rapidă și sortarea prin interclasare sunt cele mai rapide pe liste aleatorii, iar sortarea prin inserție e cea mai rapidă pe liste aproape sortate. Metoda bulelor și sortarea prin selecție sunt lente pe toate listele, în afară de cele mai mici.

Ce contează ca operație?

Fiecare comparație a două valori, fiecare cifră sau valoare citită de sortarea radix și de sortarea prin numărare și fiecare interschimbare sau mutare a unei valori. E un model simplu: timpii reali de execuție depind și de accesul la memorie și de costul fiecărei operații.

De ce câștigă atât de des sortarea prin numărare și sortarea radix?

Pentru că nu compară niciodată valori. Se folosesc de faptul că valorile sunt numere întregi mici, așa că munca lor crește cu n plus intervalul valorilor, nu cu n log n. Pe date care nu sunt numere întregi mici nu se pot aplica.

De ce câștigă sortarea prin inserție pe o listă aproape sortată?

Pentru că munca ei este numărul de valori plus numărul de perechi aflate în ordine greșită. O listă aproape sortată are foarte puține astfel de perechi, așa că fiecare valoare se mută doar cu o poziție sau două.

Numerele mele sunt trimise undeva?

Nu. Cursa rulează în browserul dumneavoastră, iar ultimele setări rămân în stocarea locală a acestui browser.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Mergi la editor