Comparații
Scrieri
Interclasări

  • Porțiunea interclasată
  • Comparate
  • Scrise înapoi
  • Interclasate până acum

Mai multe despre sortarea prin interclasare

Sortarea prin interclasare

Sortarea prin interclasare este un algoritm de tip „divide et impera”. Împarte lista în două, sortează fiecare jumătate la fel și interclasează cele două jumătăți sortate luând mereu cea mai mică valoare din față. Urmăriți cum jumătățile sunt mutate într-un rând tampon și scrise înapoi în ordine, la orice viteză sau câte un pas, și numărați comparațiile, scrierile și interclasările. Apăsați Redare pentru a urmări sortarea sau Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași ca să săriți oriunde. Casetele numără comparațiile, scrierile înapoi în listă și interclasările. Alegeți câte bare sunt, 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 sau folosiți Pas și Înapoi ca să avansați câte un pas. Trageți glisorul pentru pași ca să săriți oriunde în sortare.
  3. Urmăriți fiecare interclasare: cele două jumătăți sortate coboară în zona tampon, iar cea mai mică valoare din față urcă înapoi, pe rând.

Cum funcționează sortarea prin interclasare

O singură valoare este deja sortată. O listă mai lungă se împarte în două jumătăți, iar fiecare jumătate se sortează prin interclasare. Apoi jumătățile se interclasează: priviți valoarea din față a fiecărei jumătăți, mutați-o pe cea mai mică în rezultat și repetați până se golesc ambele jumătăți. Pentru că ambele jumătăți sunt sortate, și rezultatul este sortat.

Mereu n log n

Împărțirea în două iar și iar dă cam log₂ n niveluri, iar fiecare nivel de interclasări scrie fiecare valoare o dată, așa că sortarea face cam n log₂ n scrieri și cel mult tot atâtea comparații. Spre deosebire de metoda bulelor, sortarea prin selecție și sortarea prin inserție, acest număr nu crește cu n², iar ordinea listei contează mult mai puțin. Prețul este o zonă tampon cât lista. Sortarea prin interclasare este și stabilă, de aceea stă la baza sortărilor din Python și Java.

Întrebări frecvente

Cum funcționează sortarea prin interclasare?

Împarte lista în două, sortează fiecare jumătate prin interclasare și interclasează cele două jumătăți sortate luând mereu cea mai mică dintre valorile lor din față. O listă cu o singură valoare este deja sortată, așa că împărțirea se oprește acolo.

Câte comparații face sortarea prin interclasare?

Pentru n valori, cel mult aproximativ n log₂ n − n + 1 și cel puțin aproximativ jumătate din n log₂ n. Pentru 40 de valori, asta înseamnă cel mult 177. Scrierile înapoi în listă sunt mereu aceleași pentru un n dat: una pentru fiecare valoare la fiecare nivel de interclasare.

De ce are nevoie sortarea prin interclasare de memorie suplimentară?

Interclasarea pe loc a două jumătăți e greu de făcut rapid, așa că varianta obișnuită copiază jumătățile într-o zonă tampon și le scrie înapoi în ordine. Zona tampon e cât lista, iar acesta e principalul dezavantaj față de quicksort și heapsort.

Este sortarea prin interclasare stabilă?

Da. 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 inițială.

Numerele mele sunt trimise undeva?

Nu. Sortarea 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