Sortați după grămadă

O execuție a algoritmului Heapsort sortează o parte din valorile permutate la întâmplare. În primul rând, elementele sunt rearanjate pentru a îndeplini condițiile de grămadă. Înainte de sortarea propriu-zisă, structura arborelui heap este arătată pe scurt prin ilustrație.

Descoperitor sau inventator	JWJ Williams ( în )
Data descoperirii	1964
Problemă conexă	Algoritm de sortare
Structură de date	Bord
La inceputul	Smoothsort

Complexitatea timpului

Cel mai rău caz	$O (n \ log (n))$
In medie	$O (n \ log (n))$
Cel mai bun caz	$Noi)$

Complexitatea spațiului

Cel mai rău caz	$O (1)$

În informatică , sortarea prin heap este un algoritm de sortare prin comparații. Acest algoritm are o complexitate asimptotică optimă, adică se arată că niciun algoritm de sortare a comparației nu poate avea o complexitate asimptotic mai bună. Complexitatea sa este proporțională cu unde este lungimea tabloului de sortat. Sortarea după heap se face în loc , adică nu necesită alocarea unei zone de memorie suplimentare (mai precis necesită doar o alocare a unei zone de memorie de dimensiuni ). Pe de altă parte, nu este stabil. $n \ log n$ $nu$ $O (1)$

Dezavantajul său major este lentoarea în comparație cu sortarea rapidă (care este în medie de două ori mai rapidă ): pe o matrice mare, va trebui să proceseze un număr mare de locații de memorie a căror distanță poate depăși capacitatea cache, care încetinește accesul la memorie și execuția algoritmului.

Principiu

Ideea din spatele acestui algoritm este de a vedea matricea ca un arbore binar . Primul element este rădăcina, al doilea și al treilea sunt descendenți ai primului element etc. Astfel, al treilea element are drept copii elementele și . Dacă matricea nu are aceeași dimensiune , ramurile nu se termină toate la aceeași adâncime. $nu$ $2n$ $2n + 1$ $(2 ^ {n} -1)$

În algoritm, căutăm să obținem o grămadă , adică un arbore binar care să verifice următoarele proprietăți (primele două proprietăți rezultă din modul în care considerăm elementele matricei):

diferența maximă de adâncime între două foi este 1 ( adică toate foile sunt pe ultimul sau pe penultimul rând);
foile de adâncime maximă sunt „împachetate” în stânga.
fiecare nod are o valoare mai mare (sau mai mică) decât cele ale celor doi copii ai săi, pentru un sortiment ascendent (respectiv. desc.).

Rezultă că rădăcina grămezii (primul element) conține valoarea maximă (resp. Minimă) a arborelui. Sortarea se bazează pe această proprietate.

Așa cum s-a explicat mai sus, un heap aproape complet sau un arbore binar poate fi stocat într-o matrice, presupunând că cei doi descendenți ai elementului index sunt elementele index și (pentru o matrice indexată de la 1). Cu alte cuvinte, nodurile arborelui sunt plasate în tabel rând cu rând, fiecare rând fiind descris de la stânga la dreapta. În rest, considerăm că sortăm în ordine crescătoare. $nu$ $2n$ $2n + 1$

Operația de bază a acestei sortări este cernerea sau percolarea unui element, presupus a fi singurul „deplasat” într-un copac care este aproape o grămadă. Mai precis, luați în considerare un copac ale cărui două subarburi ( și ) sunt grămezi, în timp ce rădăcina este posibil mai mică decât copiii săi. Operația de cernere constă în schimbul rădăcinii cu cel mai mare dintre copiii săi, și așa mai departe, recursiv, până când este la locul său. Pentru a construi un teanc din orice copac, cernem rădăcinile fiecărui teanc, de jos în sus și de la dreapta la stânga. Prin urmare, începem cu sub-copacii „elementari” - conținând două sau trei noduri, așadar situați în partea de jos a copacului. Rădăcina acestui heap este, prin urmare, valoarea maximă a matricei. Apoi schimbăm rădăcina cu ultimul element al matricei și restrângem heap-ul prin a nu atinge ultimul element, adică rădăcina veche; prin urmare, am plasat cea mai mare valoare la sfârșitul matricei (deci la locul său) și nu o mai atingem. Apoi, cerneți rădăcina pentru a crea din nou o grămadă și repetăm operația pe grămada restricționată până când o golim și o înlocuim cu o matrice sortată. $A = A [1]$ $A [2]$ $A [3]$

Pseudo cod

Presupunem că arborele este o matrice indexată între 1 și lungime. arborele [i] desemnează al i-lea element al acestei matrice.

fonction tamiser(arbre, nœud, n) : (* descend arbre[nœud] à sa place, sans dépasser l'indice n *) k := nœud j := 2k tant que j ≤ n si j < n et arbre[j] < arbre[j+1] j := j+1 fin si si arbre[k] < arbre[j] échanger arbre[k] et arbre[j] k := j j := 2k sinon j := n+1 fin si fin tant que fin fonction fonction triParTas(arbre, longueur) : pour i := longueur/2 à 1 tamiser(arbre, i, longueur) fin pour pour i := longueur à 2 échanger arbre[i] et arbre[1] tamiser(arbre, 1, i-1) fin pour fin fonction

La sfârșitul funcției, triParTasmatricea arbreeste sortată în ordine crescătoare. Este suficient să inversați operatorii de comparație pentru a obține o sortare în ordine descrescătoare.

Analiză

Acest algoritm permite sortarea în loc a elementelor unui tablou într-un timp de ordinea , unde este numărul de elemente de sortat. Complexitatea dintre cel mai bun caz și cel mai rău caz variază doar în funcție de un factor constant. Cel mai scump pas din algoritm este a doua buclă, adică extragerea articolelor din heap. Primul pas, constând în construirea grămezii, se efectuează în timp liniar în n . $n \ log n$ $nu$

Principalele avantaje ale acestei metode sunt consumul redus de memorie și eficiența, ceea ce este optim, având în vedere că nu se fac ipoteze cu privire la natura datelor care urmează a fi sortate.

Posibilă îmbunătățire

Când matricea este deja sortată, sortarea heap o amestecă mai întâi înainte de a o sorta din nou. Scopul algoritmului Smoothsort este de a depăși acest dezavantaj.
La sfârșitul sortării heap, pentru ultimele 15 articole, algoritmul efectuează aceleași inversări de mai multe ori la rând, ceea ce nu este necesar. În schimb, puteți opri algoritmul atunci când nu mai sunt multe elemente și puteți trece la altul. Datele rămase sunt sortate aproximativ înapoi. Putem , prin urmare, de exemplu, returnează datele rămase (cu o inversare a 1 st și pe urmă, 2 - lea și penultima, etc.) , apoi efectuați o inserție de sortare .

linkuri externe

(ro) Ilustrație dinamică a sortării după grămadă

Note și referințe

Analiza Heapsort, Schaffer R. și Sedgewick R., 2002.