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.

Două jumătăți sortate ale unei liste mutate într-un rând tampon și cea mai mică valoare din față urcând înapoi în listă
Două jumătăți sortate ale unei liste mutate într-un rând tampon și cea mai mică valoare din față urcând înapoi în listă

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.

John von Neumann, în fotografia de pe legitimația de la Los Alamos. A descris sortarea prin interclasare în 1945, unul dintre primele algoritme scrise pentru un calculator cu program stocat.
John von Neumann, în fotografia de pe legitimația de la Los Alamos. A descris sortarea prin interclasare în 1945, unul dintre primele algoritme scrise pentru un calculator cu program stocat.

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