Sortare lină

Smoothsort este un  algoritm de sortare a selecției , un fel de sortare heap , dezvoltat de E. Dijkstra în 1981. La fel ca heapsort, are o complexitate în cel mai rău caz de O ( n log  n ) . Avantajul smoothsort-ului este că complexitatea sa se apropie de O( n ) dacă intrarea este sortată parțial, în timp ce heapsort are întotdeauna aceeași complexitate, indiferent de starea intrării.

Introducere generală

Ca și în cazul heapsort, o grămadă de date este acumulată într-o matrice, care este apoi sortată prin eliminarea continuă a maximului din heap. Spre deosebire de heapsort, nu folosește un heap binar , ci unul special obținut folosind numere Leonardo . O grămadă constă dintr-o succesiune de grămezi, ale căror dimensiuni sunt egale cu unul dintre numerele Leonardo, iar rădăcinile sunt stocate în ordine crescătoare. Avantajul unor astfel de grămezi speciale față de cele binare este că, dacă secvența este sortată, va dura O( n ) timp pentru ao crea și distruge, ceea ce este mai rapid. Împărțirea datelor de intrare în heap-uri este simplă: nodurile cele mai din stânga ale matricei vor alcătui cel mai mare heap, iar cele rămase vor fi împărțite într-un mod similar.

• O matrice de orice lungime poate fi, de asemenea, împărțită în bucăți de dimensiunea L( x ) .
• Nu ar trebui să existe două grămezi de aceeași dimensiune, deoarece în acest caz secvența va deveni strict descrescătoare în dimensiune.
• Nu trebuie să existe două grămezi care au dimensiuni egale cu două numere Leonardo consecutive, cu excepția unei matrice de lungime 2.

Aceste afirmații pot fi dovedite.

Fiecare grămada de mărimea L( x ) constă, de la stânga la dreapta, dintr-un subheap de dimensiunea L( x − 1 ) , un subhap de dimensiunea L( x − 2 ) și o rădăcină, cu excepția mormanilor de dimensiunea L(1 ). ) și L(0) , care constau numai din rădăcină. Pentru fiecare heap, este valabilă următoarea proprietate: valoarea rădăcinii trebuie să fie cel puțin la fel de mare ca și valorile rădăcinilor grămezilor sale copil (și, prin urmare, nu mai puțin decât valorile tuturor nodurilor grămele lui de copil). Pentru o secvență de grămezi, la rândul său, este valabilă următoarea proprietate: valoarea rădăcinii fiecărei grămezi trebuie să fie cel puțin la fel de mare ca valoarea rădăcinii grămezii din stânga. Consecința acestui lucru este că nodul cel mai din dreapta din secvență va avea cea mai mare valoare și, important, o matrice parțial sortată nu va trebui să fie rearanjată pentru a deveni o secvență heap adecvată. Aceasta este sursa de adaptabilitate a algoritmului. Algoritmul este simplu. În primul rând, matricea nesortată este împărțită într-un heap cu un element și o parte nesortată. O grămadă cu un element este, evident, o secvență adecvată de grămezi. Secvența începe să crească prin adăugarea câte un element din dreapta la un moment dat (dacă este necesar, elementele sunt schimbate astfel încât proprietatea heap și proprietatea secvenței să fie păstrate) până când ajunge la dimensiunea matricei originale. Și de acum înainte, elementul cel mai din dreapta din secvența de grămezi va fi cel mai mare pentru orice grămada și, prin urmare, va fi în poziția corectă, finală. Secvența heap este apoi redusă la un heap cu un element prin eliminarea nodului din dreapta și repoziționând elementele pentru a restabili starea heap-ului. De îndată ce există un heap cu un element rămas, matricea va fi sortată.

Operațiuni

Sunt necesare două operații: creșterea secvenței heap prin adăugarea unui element la dreapta și scăderea acesteia prin eliminarea elementului din dreapta (rădăcina ultimului heap), păstrând în același timp starea heap-ului și secvența heap-urilor.

Creșterea secvenței de grămezi prin adăugarea unui element la dreapta

• Dacă ultimele două grămezi sunt L( x + 1 ) și L( x ) (două numere Leonardo consecutive), noul element devine rădăcina mormanei mai mari, L( x + 2 ) . Pentru aceasta, proprietatea heap este opțională.
• Dacă dimensiunile ultimelor două grămezi nu sunt egale cu două numere Leonardo consecutive, noul element formează o nouă grămada de dimensiunea 1. Se presupune că această dimensiune este L(1) , cu excepția cazului în care grămada cea mai din dreapta are deja dimensiunea L(1) , caz în care dimensiunea noului heap cu un element se presupune a fi egală cu L(0) .

După aceea, proprietățile heap-ului și secvenței heap-urilor trebuie restaurate, ceea ce se realizează de obicei folosind o variație a sortării de inserție :

1. Grămada cea mai din dreapta (ultima formată) este considerată grămada „actuală”.
2. Atâta timp cât există o grămadă în stânga sa și valoarea rădăcinii sale este mai mare decât valoarea rădăcinii curente și ambele rădăcini ale mormanelor copilului:
   • Noua rădăcină și rădăcina heap din stânga sunt schimbate (ceea ce nu va rupe proprietatea heap-ului curent). Acest heap devine heap-ul curent.
3. Se efectuează o „cernere” astfel încât proprietatea heap să fie satisfăcută:
   • Atâta timp cât dimensiunea heap-ului curent este mai mare decât 1 și valoarea rădăcinii oricăruia dintre heap-urile copil este mai mare decât valoarea rădăcinii heap-ului curent:
     • Cea mai mare rădăcină a heap-ului copil și rădăcina actuală sunt schimbate. Heap-ul copil devine grămada curentă.

Operația de cernere este mult simplificată prin utilizarea numerelor Leonardo, deoarece fiecare grămadă fie va avea un singleton, fie va avea doi copii. Nu este nevoie să vă faceți griji că pierdeți unul dintre grămezi de copii.