Smoothsort

Smoothsort
Smoothsort atunci când sortați o listă care este deja destul de ordonată, dar cu unele elemente în afara secvenței.
Clasă	Algoritm de sortare
Structură de date	Matrice
Cel mai rău caz din punct de vedere temporal	$O(n\log n)$ ${\ displaystyle O (n \ log n)}$ $O (n \ log n)$
Caz optim în timp	$O(n)$ ${\ displaystyle O (n)}$ $Pe)$
Cel mai rău caz spațial	$O(n)$ ${\ displaystyle O (n)}$ $Pe)$ total, $O(1)$ ${\ displaystyle O (1)}$ $O (1)$ auxiliar
Optim	Când datele sunt deja sortate
Manual

În informatică , Smoothsort ^[1] ^[2] (metodă) este un algoritm de sortare deosebit de potrivit pentru sortarea listelor de date deja parțial ordonate. Smoothsort este o variantă a sortului Heap dezvoltat de Edsger Dijkstra în 1981 : la fel ca sortul Heap, Smoothsort are limita de calcul maximă egală cu O ( n log n ). Cu toate acestea, Smoothsort se apropie de un timp O ( n ) dacă datele de intrare sunt deja parțial sortate , în timp ce sortarea Heap utilizează în medie O ( n log n ), indiferent de nivelul inițial de sortare.

Analize

Lista de sortat este împărțită într-un șir de grămezi , fiecare dintre ele având o dimensiune egală cu unul dintre numerele L (n) ale lui Leonardo . Procesul de împărțire este simplu: nodurile din stânga din listă sunt împărțite în cel mai mare heap posibil, iar restul sunt împărțite în același mod. Se poate arăta că:

orice listă de orice dimensiune poate fi împărțită în secțiuni ale dimensiunii L (x).
Verificare: în mod trivial, cea mai mică secțiune L (0) este 1.
Nu pot exista 2 grămezi cu aceeași dimensiune. Șirul va fi deci un șir de heap cu dimensiuni forțate în ordine descrescătoare. De asemenea, puteți utiliza o matrice de biți pentru a urmări care sunt numerele Leonardo utilizate ca mărimi de heap (multe implementări folosesc biții cei mai puțin semnificativi pentru aceasta).
Verificare: numerele Leonardo L (n) cresc mai puțin rapid decât 2 ⁿ , deci pentru fiecare matrice va exista întotdeauna un L (n) a cărui dimensiune va fi mai mare decât jumătate din matrice. Excepția este matricea de mărimea 2, dar care poate fi împărțită în 2 grămezi de mărimea L (1) și L (0) care sunt, prin definiție, ambele cu valoarea 1.
Nu pot exista 2 grămezi ale căror dimensiuni sunt două numere Leonardo consecutive, cu excepția ultimelor două.
Verificare: dacă a mai rămas ceva, chiar și un singur element, după ce am folosit două numere consecutive L (x + 1) și L (x), le-am fi putut combina împreună pentru a forma o porțiune mai mare a dimensiunii L (x + 2) . Dar, din moment ce nu am făcut-o, nu poate rămâne nimic după două grămezi de mărimea L (x + 1) și L (x).

Fiecare grămadă, a cărei dimensiune este L (x), este structurată de la stânga la dreapta ca o grămadă secundară de dimensiunea L (x-1), o grămadă secundară de dimensiunea L (x-2) și un nod rădăcină, cu excepția heap-ului de mărimea L (1) și L (0) (care au o valoare de 1 prin definiție). Fiecare heap păstrează proprietatea asupra heap-urilor pentru care un nod rădăcină este întotdeauna mai mare sau egal cu nodurile rădăcină ale heap-urilor sale copil (și, prin urmare, mai mare sau egal cu toate nodurile din heap-urile sale copil), iar șirul de heap ca întreg păstrează proprietatea de șiruri pentru care nodul rădăcină al fiecărei grămezi este mai mare sau egal cu nodul rădăcină al grămezii din stânga sa.

Ca o consecință a acestui lucru, nodul din dreapta din șir este întotdeauna mai mare sau egal cu toate celelalte noduri și, foarte important, o matrice care este deja sortată nu necesită ajustări pentru a fi distribuite într-o serie de grămezi valide. Aceasta este caracteristica adaptativă a algoritmului.

Algoritmul este simplu. Începem prin împărțirea listei noastre neordonate într-un singur heap de element, urmat de o porțiune neordonată. O listă a unui element este în mod trivial o secvență validă de grămezi: această secvență este apoi incrementată prin adăugarea unui element la rândul său la dreapta, făcând swap-urile corespunzătoare pentru a păstra proprietatea asupra secvenței și proprietatea heap-ului, până când acoperă întregul lista inițială.

În acest moment, elementul din dreapta din secvența heap va fi cel mai mare element din orice heap și, prin urmare, va fi în poziția sa corectă și finală. Apoi, reducem seria de grămezi la o singură grămadă a unui singur element, eliminând nodul cel mai din dreapta (care este la locul său) și efectuând o rearanjare pentru a restabili starea grămezii. Când ne întoarcem în starea unui singur heap cu un singur element, atunci lista este sortată.

Notă

linkuri externe

Transcriere comentată a EWD796a ( PDF ), pe enterag.ch .

Portal IT : accesați intrările Wikipedia care se ocupă cu IT

[1] wd796a

[2] EWDijkstra Archive: Smoothsort, o alternativă pentru sortare in situ (EWD 796a)

[1]

[2]

V · D · M Algoritmi de sortare
Teorie	Teoria complexității de calcul · notație Big O · Matrice · Listă · Stivă · Coadă · Sortare comparativă · Sortare adaptivă
Algoritmi de schimb	Bubble sortare · Shaker sortare · par-impar sortare · Comb sortare · Gnome sortare · Quicksort
Algoritmi de selecție	Sortare selecție · Sortare grămadă · Smoothsort
Algoritmi de inserție	Inserția sortare · Shell sortare · copac sortare · Bibliotecă sortare · sortare Răbdare
Algoritmi de fuziune	Merge sort · Timsort
Algoritmi necomparativi	Sortare Radix · Sortare cupă · Sortare numărare · Sortare porumbel
Alți algoritmi	Sortarea de rețea · topologică sortare · sortare bitonic · clatite sortare
Algoritmi ineficienți	Sortare stupidă · Sortare Trippel