Algoritmi de sortare comparați
Nu există un singur algoritm de sortare cel mai rapid. Unii sunt simpli, dar lenți, alții sunt rapizi pe date aleatorii, dar se împiedică la date sortate, iar alții nici nu sortează prin comparații. O cursă a tuturor celor opt pe aceeași listă arată diferențele dintr-o privire.
Trei familii
Metoda bulelor, sortarea prin selecție și sortarea prin inserție sunt sortările simple. Compară și interschimbă valori apropiate și, pe o listă aleatorie, au nevoie de un timp proporțional cu n². Sortarea prin interclasare, sortarea rapidă și sortarea prin ansamble împart munca inteligent și au nevoie de un timp proporțional cu n log n, ceea ce e cel mai bun rezultat posibil pentru o sortare care poate întreba doar care dintre două valori e mai mare. Sortarea radix și sortarea prin numărare sar complet peste această întrebare: folosesc chiar cifrele sau valorile, ceea ce funcționează doar pentru chei precum numerele întregi mici.
Măsurarea muncii
Cursa sortărilor numără o operație pentru fiecare comparație, fiecare cifră sau valoare citită și fiecare interschimbare sau mutare. Pe 40 de valori aleatorii, asta înseamnă circa 120 pentru sortarea prin numărare, 240 pentru sortarea radix, 260 pentru sortarea rapidă, 380 pentru sortarea prin interclasare, 490 pentru sortarea prin ansamble, circa 820 fiecare pentru sortarea prin selecție și cea prin inserție și peste 1.100 pentru metoda bulelor. Calculatoarele reale țin cont și de memorie: în practică, sortarea rapidă e de obicei mai rapidă decât sugerează contorul ei, iar sortarea prin ansamble mai lentă, din cauza felului în care parcurg lista.
Datele de intrare contează
Pe o listă aproape sortată, sortarea prin inserție are nevoie de doar circa 50 de operații pentru 40 de valori, iar metoda bulelor de circa 90, pentru că fiecare valoare e aproape de locul ei. Pe o listă inversată, aceleași două au nevoie de 1.560, cel mai rău caz al lor. Pentru sortarea prin selecție, prin ansamble, prin interclasare, radix și prin numărare, ordinea aproape nu contează. Sortarea rapidă cu mediana din trei se descurcă bine cu liste sortate și inversate, dar cu un pivot naiv o listă sortată e cel mai rău caz al ei. Puține valori distincte încetinesc sortarea rapidă, pentru că valorile egale ajung toate de aceeași parte.
Memorie și stabilitate
Metoda bulelor și sortarea prin selecție, prin inserție, rapidă și prin ansamble lucrează pe loc, cu puțină memorie suplimentară sau deloc. Sortarea prin interclasare, radix și prin numărare au nevoie de un buffer la fel de lung ca lista. O sortare stabilă păstrează valorile egale în ordinea lor inițială: metoda bulelor și sortarea prin inserție, prin interclasare, radix și prin numărare sunt stabile, în timp ce sortarea prin selecție, rapidă și prin ansamble nu sunt. Stabilitatea contează când sortați înregistrări după un câmp, apoi după altul.
Pe care să o folosiți
În practică folosiți sortarea integrată în limbajul de programare: de obicei Timsort, o sortare prin interclasare care folosește sortarea prin inserție pentru bucăți scurte și e rapidă pe date parțial sortate, sau introsort, o sortare rapidă care trece la sortarea prin ansamble la nevoie și folosește sortarea prin inserție pentru părți mici. Pentru multe chei întregi mici, sortarea prin numărare sau sortarea radix le poate întrece pe amândouă. Metoda bulelor și sortarea prin selecție sunt mai ales instrumente didactice.
Explorați
Deschideți cursa sortărilor și apăsați Redare. Fiecare culoar e o sortare pe aceeași listă; numărul din dreapta îi numără operațiile, iar culoarul devine verde când sortarea s-a terminat. Încercați o listă aproape sortată, una inversată și una cu puține valori distincte și urmăriți cum se schimbă ordinea la sosire. Fiecare sortare are și propria aplicație, în care o puteți parcurge pas cu pas, în detaliu.
Întrebări frecvente
Care este cel mai rapid algoritm de sortare?
Pentru date obișnuite, sortarea rapidă și sortarea prin interclasare (și hibrizii construiți pe ele, ca introsort și Timsort) sunt în medie cele mai rapide, cu n log n. Pentru chei întregi mici, sortarea prin numărare și sortarea radix sunt și mai rapide. Pentru liste scurte sau aproape sortate câștigă sortarea prin inserție.
De ce nicio sortare prin comparații nu poate întrece n log n?
O listă de n valori poate fi în n! ordini, iar fiecare comparație are două rezultate, deci în cel mai rău caz sunt necesare cel puțin log₂(n!) comparații pentru a le deosebi pe toate. Asta înseamnă circa n log₂ n. Sortarea radix și sortarea prin numărare ocolesc această limită pentru că nu compară.
Care algoritmi de sortare sunt stabili?
Metoda bulelor și sortarea prin inserție, prin interclasare, radix și prin numărare sunt stabile în formele lor obișnuite. Sortarea prin selecție, sortarea rapidă și sortarea prin ansamble nu sunt, pentru că mută valorile pe distanțe mari.
Care sortări au nevoie de memorie suplimentară?
Sortarea prin interclasare, radix și prin numărare au nevoie de un buffer cam cât lista. Metoda bulelor și sortarea prin selecție, prin inserție și prin ansamble nu au nevoie aproape deloc, iar sortarea rapidă doar de puțină pentru recursivitate.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Porniți cursa sortărilor