Sortarea prin interclasare
Sortarea prin interclasare transformă o problemă grea în multe probleme ușoare: două liste sortate se combină ușor într-una singură. Împărțiți lista în două până când fiecare bucată e o singură valoare, apoi interclasați bucățile la loc. Este algoritmul clasic de tip „divide et impera”, iar timpul său este n log n, oricare ar fi datele de intrare.
Ideea
Interclasarea este partea ușoară. Având două liste, fiecare sortată, comparați primele lor valori și luați-o pe cea mai mică. Comparați noile prime valori și luați din nou cea mai mică. Când o listă se termină, adăugați restul celeilalte la final. Fiecare pas ia o valoare, deci interclasarea a două liste cu lungimea totală m necesită cel mult m − 1 comparații. Sortarea prin interclasare folosește asta pentru a sorta: împărțiți lista în două, sortați fiecare jumătate prin interclasare și interclasați cele două jumătăți.
Un exemplu
Luați 5, 1, 4, 2, 8. Împărțiți-o în 5, 1 și 4, 2, 8. Prima jumătate se împarte în 5 și 1, care se interclasează în 1, 5. A doua jumătate se împarte în 4 și 2, 8; 2, 8 se obține din 2 și 8, apoi se interclasează cu 4 în 2, 4, 8. La final se interclasează 1, 5 și 2, 4, 8: 1, apoi 2, apoi 4, apoi 5, iar 8 rămâne. Asta înseamnă 8 comparații, 12 scrieri și 4 interclasări.
De ce n log n
Fiecare împărțire înjumătățește bucățile, așa că după cam log₂ n niveluri fiecare bucată e o singură valoare. La urcare, fiecare nivel de interclasări prelucrează fiecare valoare o dată, adică n scrieri și mai puțin de n comparații pe nivel. În total, cam n log₂ n. Pentru 40 de valori, sortarea face 216 scrieri și cel mult 177 de comparații; metoda bulelor poate avea nevoie de 780 de comparații pentru aceeași listă. Ordinea datelor contează mult mai puțin decât la acele metode: pentru 40 de valori, o listă sortată necesită 100 de comparații, una inversată 116, iar una aleatorie cam 160.
Zona tampon și stabilitatea
Pentru a interclasa două jumătăți aflate una lângă alta în listă, metoda obișnuită le copiază într-o zonă tampon și le scrie înapoi în ordine. Aplicația arată zona tampon ca al doilea rând de bare. Ea cere tot atâta memorie suplimentară cât lista, iar acesta e principalul cost al sortării prin interclasare. În schimb, sortarea este stabilă: când cele două valori din față sunt egale, cea din jumătatea stângă merge prima, așa că valorile egale își păstrează ordinea. Stabilitatea contează când sortați înregistrări după un câmp, apoi după altul.
Istorie și utilizare
John von Neumann a descris sortarea prin interclasare în 1945, ceea ce o face unul dintre primii algoritmi scriși pentru un calculator cu program memorat. Pentru că citește și scrie datele în secvențe lungi, a fost metoda standard de sortare a datelor pe bandă și se folosește încă pentru fișiere prea mari pentru memorie. Timsort, folosit de Python și de Java pentru obiecte, este o sortare prin interclasare care găsește întâi secvențele deja sortate și folosește sortarea prin inserție pentru bucățile scurte.
Explorați
Deschideți aplicația și apăsați Pas. Partea umbrită a listei este împărțită sau interclasată, iar linia întreruptă marchează mijlocul. Când începe o interclasare, ambele jumătăți coboară în rândul tampon; cele două valori din față sunt comparate, iar cea mai mică urcă înapoi. Urmăriți contoarele: scrierile sunt aceleași pentru orice listă de aceeași lungime, iar comparațiile sunt cele mai puține pentru o listă sortată sau inversată și cele mai multe pentru una aleatorie, dar niciodată mai multe decât cam n log₂ n.
Întrebări frecvente
Care este complexitatea în timp a sortării prin interclasare?
O(n log n) în cazul cel mai bun, mediu și cel mai rău. Varianta obișnuită are nevoie de O(n) memorie suplimentară pentru zona tampon.
Care este diferența dintre sortarea prin interclasare și quicksort?
Amândouă împart lista și sortează părțile. Sortarea prin interclasare împarte la mijloc fără să se uite la valori și își face treaba la interclasare; quicksort își face treaba la împărțire, mutând valorile în jurul unui pivot, și nu are nevoie de interclasare. Quicksort sortează pe loc și e adesea mai rapid în practică, dar poate încetini până la n² pe date nefavorabile și nu e stabil. Sortarea prin interclasare este mereu n log n și stabilă.
Ce este sortarea prin interclasare bottom-up?
O variantă fără recursivitate: întâi se interclasează valorile individuale vecine în perechi, apoi perechile în grupuri de patru și așa mai departe, dublând lungimea la fiecare rundă. Face aceeași muncă precum varianta top-down prezentată aici.
Este sortarea prin interclasare stabilă?
Da, atât timp cât la egalitate se ia întâi valoarea din jumătatea stângă, cum face această aplicație.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Încercați sortarea prin interclasare