Comparații
Interschimbări
Extrase

  • În coborâre
  • Comparate
  • Interschimbate
  • La locul lor

Mai multe despre sortarea prin ansamble

Sortarea prin ansamble

Sortarea prin ansamble (heapsort) citește lista ca pe un arbore binar și o rearanjează într-un ansamblu max, în care fiecare părinte este cel puțin la fel de mare ca copiii săi. Cea mai mare valoare ajunge astfel în vârf. Mutați-o la final, unde rămâne, refaceți ansamblul și repetați. Aplicația desenează ansamblul ca arbore deasupra barelor, ca să puteți urmări fiecare valoare în timp ce coboară. Apăsați Redare pentru a urmări sortarea sau Pas și Înapoi pentru a avansa câte o comparație. Trageți glisorul pentru pași ca să săriți oriunde. Arborele de deasupra barelor arată aceleași valori sub formă de ansamblu. Casetele numără comparațiile, interschimbările și valorile scoase din ansamblu. 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 o comparație. Trageți glisorul pentru pași ca să săriți oriunde în sortare.
  3. Urmăriți arborele: mai întâi fiecare părinte coboară până când ansamblul e construit, apoi rădăcina trece la final, iar ansamblul se micșorează cu unu.

Cum funcționează sortarea prin ansamble

Citiți lista ca pe un arbore: valoarea de pe poziția i are copiii pe pozițiile 2i + 1 și 2i + 2. Construiți un ansamblu max coborând fiecare părinte, începând cu ultimul: cât timp o valoare e mai mică decât cel mai mare copil al ei, cele două se interschimbă. Când rădăcina conține cea mai mare valoare, interschimbați-o cu ultima valoare din ansamblu. Acea valoare e acum definitivă, ansamblul e mai scurt cu unu, iar noua rădăcină coboară ca să redevină un ansamblu. Repetați până când ansamblul e gol.

Mereu n log n, pe loc

Arborele are aproximativ log₂ n niveluri, deci fiecare coborâre face cel mult aproximativ 2 log₂ n comparații, iar construirea ansamblului mai puțin de 2n. Astfel, în cel mai rău caz, sortarea prin ansamble face aproximativ 2n log₂ n comparații, fără zonă tampon: pentru 40 de valori, cel mult 352. Spre deosebire de quicksort, nu are date de intrare nefavorabile, iar spre deosebire de sortarea prin interclasare, nu are nevoie de memorie suplimentară. În practică e de obicei mai lentă decât ambele, pentru că sare prin listă, și nu este stabilă.

Întrebări frecvente

Cum funcționează sortarea prin ansamble?

Transformă lista într-un ansamblu max, un arbore stocat în listă în care fiecare părinte e cel puțin la fel de mare ca copiii săi. Apoi mută iar și iar cea mai mare valoare, din rădăcină, la finalul ansamblului și coboară noua rădăcină ca să refacă ansamblul.

Ce este un ansamblu (heap)?

Un arbore binar complet stocat într-o listă, fără pointeri: copiii poziției i sunt pozițiile 2i + 1 și 2i + 2. Într-un ansamblu max fiecare părinte e cel puțin la fel de mare ca copiii săi, deci cea mai mare valoare e mereu în rădăcină, pe poziția 0.

De ce se construiește ansamblul repede?

Majoritatea valorilor sunt aproape de baza arborelui și pot coborî doar un nivel sau două. Adunând munca de pe toate nivelurile, întreaga construcție face mai puțin de 2n comparații, nu n log n.

Este sortarea prin ansamble stabilă?

Nu. Mutarea rădăcinii la final duce valorile pe distanțe mari, așa că valorile egale își pot schimba ordinea.

Sunt trimise undeva numerele mele?

Nu. Sortarea rulează în browserul dumneavoastră, iar ultimele setări rămân în spațiul de stocare local al acestui browser.

Ești gata să încerci?

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

Mergi la editor