Algoritm de sortare - Sorting algorithm

În informatică , un algoritm de sortare este un algoritm care pune elementele unei liste într-o ordine . Cele mai frecvent utilizate ordine sunt ordinea numerică și ordinea lexicografică , fie crescătoare, fie descendente. Sortarea eficientă este importantă pentru optimizarea eficienței altor algoritmi (cum ar fi algoritmii de căutare și îmbinare ) care necesită ca datele de intrare să fie în liste sortate. Sortarea este, de asemenea, adesea utilă pentru canonicalizarea datelor și pentru producerea de ieșiri citite de om.

În mod formal, ieșirea oricărui algoritm de sortare trebuie să îndeplinească două condiții:

1. Ieșirea este în ordine monotonă (fiecare element nu este mai mic / mai mare decât elementul anterior, conform ordinii solicitate).
2. Ieșirea este o permutare (o reordonare, dar păstrând toate elementele originale) a intrării.

Pentru o eficiență optimă, datele de intrare ar trebui stocate într-o structură de date care să permită accesul aleator, mai degrabă decât una care să permită doar accesul secvențial .

Istorie și concepte

De la începutul informaticii, problema sortării a atras o mulțime de cercetări, probabil datorită complexității soluționării ei în mod eficient, în ciuda afirmației sale simple și familiare. Printre autorii algoritmilor de sortare timpurii din jurul anului 1951 s-a numărat Betty Holberton , care a lucrat la ENIAC și UNIVAC . Sortarea cu bule a fost analizată încă din 1956. Algoritmi asimptotici optimi sunt cunoscuți de la mijlocul secolului al XX-lea - sunt încă inventați algoritmi noi, Timsort utilizat pe scară largă datând din 2002, iar sortarea de bibliotecă fiind publicată pentru prima dată în 2006.

Algoritmii de sortare a comparației au o cerință fundamentală de comparații Ω ( n log n ) (unele secvențe de intrare vor necesita un multiplu de n log n comparații, unde n este numărul de elemente din matrice care trebuie sortată). Algoritmii care nu se bazează pe comparații, cum ar fi numărarea sortării , pot avea o performanță mai bună.

Algoritmii de sortare sunt răspândiți în clasele introductive de informatică , unde abundența algoritmilor pentru problemă oferă o introducere ușoară la o varietate de concepte de algoritmi de bază, cum ar fi notația O mare , algoritmi divizați și cuceriți , structuri de date cum ar fi grămezi și arbori binari , algoritmi de randomizate , cel mai bun, cel mai rău caz , și medie de analiză, compromisurile spațiu-timp , și superioare și limite inferioare .

Sortarea matricelor mici în mod optim (în cel mai mic număr de comparații și swap-uri) sau rapidă (adică luând în considerare detaliile specifice mașinii) este încă o problemă de cercetare deschisă, cu soluții cunoscute doar pentru tablouri foarte mici (<20 de elemente). În mod similar, sortarea optimă (prin diverse definiții) pe o mașină paralelă este un subiect deschis de cercetare.

Clasificare

Algoritmii de sortare pot fi clasificați după:

• Complexitatea computațională
  • Cel mai bun, cel mai rău și cel mai mediu comportament în ceea ce privește dimensiunea listei. Pentru algoritmii tipici de sortare în serie, comportamentul bun este O ( n  log  n ), cu sortare paralelă în O (log ²  n ), iar comportamentul rău este O ( n ² ). Comportamentul ideal pentru o sortare în serie este O ( n ), dar acest lucru nu este posibil în cazul mediu. Sortarea paralelă optimă este O (log  n ).
  • Swap pentru algoritmi „la locul”.
• Utilizarea memoriei (și utilizarea altor resurse de computer). În special, unii algoritmi de sortare sunt „ la locul lor ”. În mod strict, o sortare în loc are nevoie doar de memorie O (1) dincolo de articolele care sunt sortate; uneori O (jurnal  n ) memorie suplimentară este considerată „în loc”.
• Recursivitate: Unii algoritmi sunt recursivi sau nerecursivi, în timp ce alții pot fi ambii (de exemplu, sortare fuzionată).
• Stabilitate: algoritmii de sortare stabilă mențin ordinea relativă a înregistrărilor cu chei egale (adică valori).
• Indiferent dacă sunt sau nu un tip de comparație . Un tip de comparație examinează datele numai comparând două elemente cu un operator de comparație.
• Metoda generală: inserarea, schimbul, selecția, fuzionarea etc. Tipurile de schimb includ sortarea cu bule și quicksort. Sortările de selecție includ sortarea ciclului și heapsort.
• Dacă algoritmul este serial sau paralel. Restul acestei discuții se concentrează aproape exclusiv pe algoritmi seriali și își asumă operații seriale.
• Adaptabilitate: Indiferent dacă presortarea intrării afectează sau nu timpul de funcționare. Se știe că algoritmii care iau în considerare acest lucru sunt adaptivi .
• Online: un algoritm precum Insertion Sort care este online poate sorta un flux constant de intrare.

Stabilitate

Un exemplu de sortare stabilă pe cărțile de joc. Când cărțile sunt sortate în funcție de rang cu un sortare stabilă, cele două 5 trebuie să rămână în aceeași ordine în ieșirea sortată în care erau inițial. Când sunt sortate cu un sort non-stabil, 5 pot ajunge în opus ordinea în ieșirea sortată.

Algoritmii de sortare stabilă sortează elemente egale în aceeași ordine în care apar în intrare. De exemplu, în exemplul de sortare a cărților din dreapta, cărțile sunt sortate în funcție de rangul lor, iar costumul lor este ignorat. Acest lucru permite posibilitatea mai multor versiuni diferite sortate corect ale listei originale. Algoritmii de sortare stabili aleg unul dintre aceștia, conform următoarei reguli: dacă două elemente se compară ca egale (cum ar fi cele două 5 cărți), atunci ordinea lor relativă va fi păstrată, adică dacă una se află înaintea celeilalte în intrare, va veni înainte de cealaltă în ieșire.

Stabilitatea este importantă pentru a păstra ordinea pe mai multe sortări pe același set de date . De exemplu, spuneți că înregistrările elevilor constând din nume și secțiunea de clasă sunt sortate dinamic, mai întâi după nume, apoi după secțiunea de clasă. Dacă se utilizează un algoritm stabil de sortare în ambele cazuri, operațiunea de sortare după clasă nu va modifica ordinea numelui; cu un sort instabil, ar putea fi faptul că sortarea după secțiune amestecă ordinea numelui, rezultând o listă non-alfabetică de studenți.

Mai formal, datele care sunt sortate pot fi reprezentate ca o înregistrare sau un tuplu de valori, iar partea de date care este utilizată pentru sortare se numește cheie . În exemplul de carte, cărțile sunt reprezentate ca o înregistrare (rang, costum), iar cheia este rangul. Un algoritm de sortare este stabil dacă ori de câte ori există două înregistrări R și S cu aceeași cheie și R apare înaintea lui S în lista originală, atunci R va apărea întotdeauna înaintea lui S în lista sortată.

Când elementele egale nu se pot distinge, cum ar fi cu numerele întregi, sau mai general, orice date în care întregul element este cheia, stabilitatea nu este o problemă. Stabilitatea nu este, de asemenea, o problemă dacă toate cheile sunt diferite.

Algoritmii de sortare instabili pot fi implementați special pentru a fi stabili. O modalitate de a face acest lucru este extinderea artificială a comparației cheii, astfel încât comparațiile dintre două obiecte cu chei altfel egale să fie decisă folosind ordinea intrărilor din lista de intrare originală ca un break-tie. Reținerea acestei comenzi, însă, poate necesita timp și spațiu suplimentar.

O aplicație pentru algoritmi stabili de sortare este sortarea unei liste folosind o cheie primară și secundară. De exemplu, să presupunem că dorim să sortăm o mână de cărți astfel încât costumele să fie în cluburile de comandă (♣), diamante ( ♦ ), inimi ( ♥ ), pică (♠) și, în fiecare costum, cărțile sunt sortate după rang. Acest lucru se poate face prin sortarea mai întâi a cărților în funcție de rang (folosind orice fel), apoi efectuarea unei sortări stabile după costum:

În cadrul fiecărui costum, sortul stabil păstrează ordonarea după rang care a fost deja realizată. Această idee poate fi extinsă la orice număr de chei și este utilizată prin sortare radix . Același efect poate fi obținut cu un sort instabil utilizând o comparație cheie lexicografică, care, de exemplu, compară mai întâi după costum și apoi compară după rang dacă costumele sunt aceleași.

Compararea algoritmilor

În aceste tabele, n este numărul de înregistrări care trebuie sortate. Coloanele „Cel mai bun”, „Mediu” și „Cel mai rău” oferă complexitatea timpului în fiecare caz, în ipoteza că lungimea fiecărei chei este constantă și, prin urmare, că toate comparațiile, swap-urile și alte operații pot continua în timp constant. „Memorie” reprezintă cantitatea de spațiu de stocare suplimentară necesară suplimentar față de cea utilizată de listă în sine, sub aceeași ipoteză. Duratele de rulare și cerințele de memorie enumerate se află în notația O mare , prin urmare baza logaritmilor nu contează. Notarea log ² n înseamnă (log n ) ² .

Tipuri de comparație

Mai jos este un tabel de tipuri de comparație . Un tip de comparație nu poate avea o performanță mai bună decât O ( n log n ) în medie.

Tipuri de comparație

Nume	Cel mai bun	In medie	Cel mai rău	Memorie	Grajd	Metodă	Alte note
Sortare rapida	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n ^ {2}}$	${\ displaystyle \ log n}$	Nu	Partiționare	Quicksort se face de obicei în loc cu spațiul de stivă O (log n ) .
Merge sort	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	n	da	Fuziune	Foarte paralelizabil (până la O (log n ) folosind algoritmul celor trei maghiari).
Sortare la locul de îmbinare	-	-	${\ displaystyle n \ log ^ {2} n}$	1	da	Fuziune	Poate fi implementat ca un tip stabil bazat pe o fuziune stabilă la fața locului.
Introsort	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle \ log n}$	Nu	Partiționare și selecție	Folosit în mai multe implementări STL .
Heapsort	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	1	Nu	Selecţie
Sortare prin inserție	n	${\ displaystyle n ^ {2}}$	${\ displaystyle n ^ {2}}$	1	da	Inserare	O ( n + d ) , în cel mai rău caz peste secvențe care au inversiuni d .
Blocare sortare	n	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	1	da	Inserare și fuziune	Combinați un algoritm de îmbinare pe bază de blocuri cu un sortare de îmbinare de jos în sus . ${\ displaystyle O (n)}$
Timsort	n	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	n	da	Inserare și fuziune	Face comparații n-1 atunci când datele sunt deja sortate sau inversate.
Sortare selecție	${\ displaystyle n ^ {2}}$	${\ displaystyle n ^ {2}}$	${\ displaystyle n ^ {2}}$	1	Nu	Selecţie	Stabil cu spațiu suplimentar, atunci când se utilizează liste legate, sau când este realizat ca o variantă de sortare prin inserție în loc să schimbe cele două elemente. ${\ displaystyle O (n)}$
Cubesort	n	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	n	da	Inserare	Face comparații n-1 atunci când datele sunt deja sortate sau inversate.
Shellsort	${\ displaystyle n \ log n}$	${\ displaystyle n ^ {4/3}}$	${\ displaystyle n ^ {3/2}}$	1	Nu	Inserare	Dimensiune mică a codului.
Sortare cu bule	n	${\ displaystyle n ^ {2}}$	${\ displaystyle n ^ {2}}$	1	da	Schimb	Mărime cod mic.
Tip de schimb	${\ displaystyle n ^ {2}}$	${\ displaystyle n ^ {2}}$	${\ displaystyle n ^ {2}}$	1	da	Schimb	Mărime cod mic.
Sortare de arbori	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$(echilibrat)	n	da	Inserare	Când utilizați un arbore de căutare binar auto-echilibrat .
Sortarea ciclului	${\ displaystyle n ^ {2}}$	${\ displaystyle n ^ {2}}$	${\ displaystyle n ^ {2}}$	1	Nu	Selecţie	În loc cu un număr teoretic optim de scrieri.
Sortare bibliotecă	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n ^ {2}}$	n	Nu	Inserare	Asemănător cu un sortare de inserție decalată. Necesită permutarea aleatorie a intrării pentru a garanta cu limite de timp cu probabilitate ridicată, ceea ce o face să nu fie stabilă.
Sortarea răbdării	n	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	n	Nu	Inserare și selecție	Găsește toate cele mai lungi subsecvențe în creștere din O ( n log n ) .
Smoothsort	n	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	1	Nu	Selecţie	O variantă adaptativă a hărțului bazat pe secvența Leonardo, mai degrabă decât pe o grămadă binară tradițională .
Sortare de șuvițe	n	${\ displaystyle n ^ {2}}$	${\ displaystyle n ^ {2}}$	n	da	Selecţie
Sortare turneu	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	n	Nu	Selecţie	Variația Heapsort.
Sort de cocktail shaker	n	${\ displaystyle n ^ {2}}$	${\ displaystyle n ^ {2}}$	1	da	Schimb	O variantă a Bubblesort care se ocupă bine de valori mici la sfârșitul listei
Sortare pieptene	${\ displaystyle n \ log n}$	${\ displaystyle n ^ {2}}$	${\ displaystyle n ^ {2}}$	1	Nu	Schimb	Mai rapid decât sortarea cu bule în medie.
Sortare de gnomi	n	${\ displaystyle n ^ {2}}$	${\ displaystyle n ^ {2}}$	1	da	Schimb	Mărime cod mic.
Sortare impar-pare	n	${\ displaystyle n ^ {2}}$	${\ displaystyle n ^ {2}}$	1	da	Schimb	Poate fi rulat cu ușurință pe procesoare paralele.

Sortări fără comparație

Tabelul următor descrie algoritmi de sortare întregi și alți algoritmi de sortare care nu sunt sortări de comparație . Ca atare, ele nu sunt limitate la Ω ( n log n ) . Complexitățile de mai jos presupun n elemente care urmează a fi sortate, cu chei de dimensiunea k , dimensiunea cifrei d și r gama de numere care urmează a fi sortate. Multe dintre ele se bazează pe presupunerea că dimensiunea cheii este suficient de mare încât toate intrările să aibă valori cheie unice și, prin urmare, n ≪ 2 ^k , unde ≪ înseamnă „mult mai puțin decât”. În modelul de mașină cu acces aleator cu costuri unitare , algoritmii cu timp de funcționare de , cum ar fi sortarea radix, iau totuși timp proporțional cu Θ ( n log n ) , deoarece n este limitat să nu depășească și un număr mai mare de elemente pentru a sorta ar necesita un k mai mare pentru a le stoca în memorie. ${\ displaystyle \ scriptstyle n \ cdot {\ frac {k} {d}}}$${\ displaystyle 2 ^ {\ frac {k} {d}}}$

Sortări fără comparație

Nume	Cel mai bun	In medie	Cel mai rău	Memorie	Grajd	n ≪ 2 k	Note
Sortare porumbel	-	${\ displaystyle n + 2 ^ {k}}$	${\ displaystyle n + 2 ^ {k}}$	${\ displaystyle 2 ^ {k}}$	da	da	Nu se pot sorta non-întregi.
Sortare cupă (chei uniforme)	-	${\ displaystyle n + k}$	${\ displaystyle n ^ {2} \ cdot k}$	${\ displaystyle n \ cdot k}$	da	Nu	Presupune distribuția uniformă a elementelor din domeniul din matrice. De asemenea, nu pot sorta non-întregi
Sortare bucket (chei întregi)	-	${\ displaystyle n + r}$	${\ displaystyle n + r}$	${\ displaystyle n + r}$	da	da	Dacă r este , atunci complexitatea medie a timpului este . ${\ displaystyle O (n)}$${\ displaystyle O (n)}$
Sortare numărare	-	${\ displaystyle n + r}$	${\ displaystyle n + r}$	${\ displaystyle n + r}$	da	da	Dacă r este , atunci complexitatea medie a timpului este . ${\ displaystyle O (n)}$${\ displaystyle O (n)}$
Sortare LSD Radix	${\ displaystyle n}$	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n + 2 ^ {d}}$	da	Nu	${\ displaystyle {\ frac {k} {d}}}$nivelurile de recursie, 2 d pentru conta matrice. Spre deosebire de majoritatea sortărilor de distribuție, aceasta poate sorta numerele cu virgulă mobilă , numerele negative și multe altele.
Sortare MSD Radix	-	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n + 2 ^ {d}}$	da	Nu	Versiunea stabilă folosește o matrice externă de dimensiunea n pentru a conține toate coșurile. La fel ca varianta LSD, poate sorta non-întregi.
Sortare MSD Radix (în loc)	-	${\ displaystyle n \ cdot {\ frac {k} {1}}}$	${\ displaystyle n \ cdot {\ frac {k} {1}}}$	${\ displaystyle 2 ^ {1}}$	Nu	Nu	d = 1 pentru nivelurile de recursie, fără matrice de numărare. ${\ displaystyle k / 1}$
Spreadsort	n	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n \ cdot \ left ({{\ frac {k} {s}} + d} \ right)}$	${\ displaystyle {\ frac {k} {d}} \ cdot 2 ^ {d}}$	Nu	Nu	Asimptoticele se bazează pe presupunerea că n ≪ 2 k , dar algoritmul nu necesită acest lucru.
Burstsort	-	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	Nu	Nu	Are un factor constant mai bun decât sortarea radix pentru sortarea șirurilor. Deși se bazează oarecum pe specificul șirurilor frecvent întâlnite.
Flashsort	n	${\ displaystyle n + r}$	${\ displaystyle n ^ {2}}$	n	Nu	Nu	Necesită distribuirea uniformă a elementelor din domeniul din matrice pentru a rula în timp liniar. Dacă distribuția este extrem de distorsionată, atunci poate deveni pătratică dacă sortarea subiacentă este pătratică (de obicei este o sortare de inserție). Versiunea la fața locului nu este stabilă.
Sortare poștaș	-	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n + 2 ^ {d}}$	-	Nu	O variantă a sortării bucket, care funcționează foarte asemănător cu MSD Radix Sort. Specific nevoilor de servicii postale.

Samplesort poate fi folosit pentru a paralela oricare dintre tipurile care nu sunt comparative, prin distribuirea eficientă a datelor în mai multe cupe și apoi transmiterea sortării către mai multe procesoare, fără a fi necesară combinarea, deoarece cupele sunt deja sortate între ele.

Alții

Unii algoritmi sunt lente în comparație cu cele discutate mai sus, cum ar fi bogosort cu timpul alerga nemărginită și genul lacheu care are O ( n ^2.7 ) timpul de rulare. Aceste tipuri sunt de obicei descrise în scopuri educaționale pentru a demonstra modul în care este estimat timpul de rulare al algoritmilor. Tabelul următor descrie câțiva algoritmi de sortare care nu sunt practici pentru utilizarea în viața reală în contexte software tradiționale din cauza performanțelor extrem de slabe sau a cerințelor hardware specializate.

Nume	Cel mai bun	In medie	Cel mai rău	Memorie	Grajd	Comparaţie	Alte note
Sortare mărgele	n	S	S	${\ displaystyle n ^ {2}}$	N / A	Nu	Funcționează numai cu numere întregi pozitive. Necesită hardware specializat pentru ca acesta să ruleze în timp garantat . Există o posibilitate de implementare a software-ului, dar timpul de rulare va fi , unde S este suma tuturor numerelor întregi care urmează a fi sortate, în cazul numerelor întregi mici poate fi considerat liniar. ${\ displaystyle O (n)}$${\ displaystyle O (S)}$
Un fel simplu de clătite	-	n	n	${\ displaystyle \ log n}$	Nu	da	Numărul este numărul de flip-uri.
Sortare spaghete (sondaj)	n	n	n	${\ displaystyle n ^ {2}}$	da	Sondaj	Acesta este un algoritm analogic în timp liniar pentru sortarea unei secvențe de articole, care necesită spațiu de stivă O ( n ), iar sortarea este stabilă. Acest lucru necesită n procesoare paralele. Vezi sortul de spaghete # Analiza .
Sortarea rețelei	Variază	Variază	Variază	Variază	Variază (rețelele de sortare stabile necesită mai multe comparații)	da	Ordinea comparațiilor este stabilită în avans pe baza unei dimensiuni fixe a rețelei.
Sortator bitonic	${\ displaystyle \ log ^ {2} n}$ paralel	${\ displaystyle \ log ^ {2} n}$ paralel	${\ displaystyle n \ log ^ {2} n}$ non-paralel	1	Nu	da	O variantă eficientă a sortării rețelelor.
Bogosort	n	${\ displaystyle (n \ times n!)}$	nelimitat (sigur), (așteptat)${\ displaystyle (n \ times n!)}$	1	Nu	da	Amestecarea aleatorie. Se folosește numai pentru scopuri, deoarece chiar și cel mai bun timp de rulare așteptat este îngrozitor.
Stooge sort	${\ displaystyle n ^ {\ log 3 / \ log 1.5}}$	${\ displaystyle n ^ {\ log 3 / \ log 1.5}}$	${\ displaystyle n ^ {\ log 3 / \ log 1.5}}$	n	Nu	da	Mai lent decât majoritatea algoritmilor de sortare (chiar și cei naivi) cu o complexitate temporală de O ( n log 3 / log 1.5 ) = O ( n 2.7095 ... ) Poate fi stabilit și este, de asemenea, o rețea de sortare .
Slowsort	${\ displaystyle n ^ {\ log n}}$	${\ displaystyle n ^ {\ log n}}$	${\ displaystyle n ^ {\ log n}}$	n	Nu	da	Un algoritm de multiplicare și predare, antonim cu algoritmul de divizare și cucerire .

Informaticienii teoretici au detaliat alți algoritmi de sortare care oferă o complexitate de timp mai bună decât O ( n log n ) presupunând constrângeri suplimentare, inclusiv:

• Algoritmul lui Thorup , un algoritm randomizat pentru sortarea cheilor dintr-un domeniu de mărime finită, luând O ( n jurnal jurnal n ) timp și O ( n ) spațiu.
• Un algoritm de sortare a numărului întreg randomizat care ia timp așteptat și O ( n ) spațiu.${\ displaystyle O \ left (n {\ sqrt {\ log \ log n}} \ right)}$

Algoritmi de sortare populari

Deși există un număr mare de algoritmi de sortare, în implementările practice predomină câțiva algoritmi. Sortarea prin inserție este utilizată pe scară largă pentru seturile de date mici, în timp ce pentru seturile de date mari se folosește o sortare asimptotic eficientă, în primul rând sortul cu greutăți mari, sortarea prin îmbinare sau sortirea rapidă. Implementările eficiente utilizează, în general, un algoritm hibrid , combinând un algoritm asimptotic eficient pentru sortarea generală cu sortarea de inserție pentru listele mici din partea de jos a unei recursive. Implementările foarte reglate folosesc variante mai sofisticate, cum ar fi Timsort (sortare de fuziune, sortare de inserție și logică suplimentară), utilizate în Android, Java și Python, și introsort (quicksort și heapsort), utilizate (în forme variante) în unele sortări C ++ implementări și în .NET.

Pentru date mai restrânse, cum ar fi numerele într-un interval fix, sunt utilizate pe scară largă sortările de distribuție , cum ar fi sortarea numărării sau sortarea radix. Sortarea cu bule și variantele sunt rareori folosite în practică, dar se găsesc în mod obișnuit în predare și discuții teoretice.

Când sortează fizic obiecte (cum ar fi alfabetizarea hârtiei, testelor sau cărților), oamenii folosesc în mod intuitiv sortări de inserare pentru seturi mici. Pentru seturile mai mari, oamenii adesea primele cupe, cum ar fi prin litere inițiale, și cuple multiple permit sortarea practică a seturilor foarte mari. Adesea spațiul este relativ ieftin, cum ar fi împrăștierea obiectelor pe podea sau pe o suprafață mare, dar operațiunile sunt costisitoare, în special deplasarea unui obiect la o distanță mare - este importantă localitatea de referință . Tipurile de îmbinare sunt, de asemenea, practice pentru obiectele fizice, mai ales că pot fi folosite două mâini, una pentru fiecare listă de îmbinat, în timp ce alți algoritmi, cum ar fi Hipsort sau Quicksort, sunt slab potrivite pentru uz uman. Alți algoritmi, cum ar fi sortarea bibliotecii , o variantă a sortării de inserție care lasă spații, sunt, de asemenea, practice pentru utilizarea fizică.

Tipuri simple

Două dintre cele mai simple sortări sunt sortarea prin inserție și sortarea prin selecție, ambele fiind eficiente pentru datele mici, datorită costurilor reduse, dar nu eficiente pentru datele mari. Sortarea prin inserție este, în general, mai rapidă decât sortarea de selecție în practică, datorită mai puține comparații și performanțe bune la datele aproape sortate, și astfel este preferată în practică, dar sortarea de selecție folosește mai puține scrieri și, astfel, este utilizată atunci când performanța de scriere este un factor limitativ.

Sortare prin inserție

Sortarea prin inserție este un algoritm simplu de sortare, care este relativ eficient pentru listele mici și cele mai ales listele sortate și este adesea folosit ca parte a algoritmilor mai sofisticați. Funcționează luând elemente din listă unul câte unul și inserându-le în poziția corectă într-o nouă listă sortată similară cu modul în care am băgat banii în portofel. În matrici, noua listă și elementele rămase pot partaja spațiul matricei, dar inserția este costisitoare, necesitând schimbarea tuturor elementelor următoare. Shellsort (vezi mai jos) este o variantă de sortare a inserției care este mai eficientă pentru liste mai mari.

Sortare selecție

Sortarea selecției este un sortare de comparație la fața locului . Are o complexitate O ( n ² ), ceea ce îl face ineficient pe liste mari și, în general, are o performanță mai slabă decât tipul de inserare similar . Sortarea selecției este remarcată pentru simplitatea sa și are, de asemenea, avantaje de performanță față de algoritmi mai complicați în anumite situații.

Algoritmul găsește valoarea minimă, o schimbă cu valoarea din prima poziție și repetă acești pași pentru restul listei. Nu face mai mult de n swapuri și, prin urmare, este util acolo unde schimbul este foarte scump.

Sortări eficiente

Algoritmii practici de sortare generală se bazează aproape întotdeauna pe un algoritm cu o complexitate medie a timpului (și, în general, în cel mai rău caz) complexitate O ( n log n ), dintre care cele mai frecvente sunt cele mai mari, cele de sortare și cele mai rapide. Fiecare are avantaje și dezavantaje, cel mai semnificativ fiind faptul că implementarea simplă a sortării de fuziuni folosește O ( n ) spațiu suplimentar, iar implementarea simplă a quicksort are O ( n ² ) complexitatea în cel mai rău caz. Aceste probleme pot fi rezolvate sau ameliorate cu prețul unui algoritm mai complex.

În timp ce acești algoritmi sunt eficienți asimptotic pentru datele aleatorii, pentru eficiența practică a datelor din lumea reală sunt utilizate diverse modificări. În primul rând, cheltuielile generale ale acestor algoritmi devin semnificative pentru datele mai mici, așa că de multe ori se folosește un algoritm hibrid, trecând în mod obișnuit la sortarea prin inserție odată ce datele sunt suficient de mici. În al doilea rând, algoritmii au performanțe slabe în cazul datelor deja sortate sau aproape sortate - acestea sunt comune în datele din lumea reală și pot fi sortate în timp O ( n ) prin algoritmi corespunzători. În cele din urmă, ele pot fi, de asemenea , instabile , iar stabilitatea este adesea o proprietate de dorit într-un fel. Astfel, sunt adesea folosiți algoritmi mai sofisticați, cum ar fi Timsort (bazat pe sortare de îmbinare) sau introsort (bazat pe quicksort, revenind la heapsort).

Merge sort

Sortarea Merge profită de ușurința de a fuziona listele deja sortate într-o nouă listă sortată. Începe prin a compara fiecare două elemente (adică 1 cu 2, apoi 3 cu 4 ...) și schimbându-le dacă primul ar trebui să vină după al doilea. Apoi, fuzionează fiecare dintre listele de două rezultate în liste de patru, apoi fuzionează acele liste de patru și așa mai departe; până când în cele din urmă două liste sunt îmbinate în lista sortată finală. Dintre algoritmii descriși aici, acesta este primul care se ridică bine la liste foarte mari, deoarece cel mai rău timp de rulare este O ( n log n ). De asemenea, se aplică cu ușurință listelor, nu numai matricelor, deoarece necesită doar acces secvențial, nu acces aleatoriu. Cu toate acestea, are o complexitate suplimentară a spațiului O ( n ) și implică un număr mare de copii în implementări simple.

Sortarea Merge a cunoscut o creștere relativ recentă a popularității pentru implementările practice, datorită utilizării sale în algoritmul sofisticat Timsort , care este utilizat pentru rutina de sortare standard în limbajele de programare Python și Java (începând cu JDK7 ). Sortarea Merge în sine este rutina standard în Perl , printre altele, și a fost utilizată în Java cel puțin din 2000 în JDK1.3 .

Heapsort

Heapsort este o versiune mult mai eficientă a tipului de selecție . De asemenea, funcționează determinând cel mai mare (sau cel mai mic) element al listei, plasându-l la sfârșitul (sau începutul) listei, apoi continuând cu restul listei, dar realizează această sarcină în mod eficient utilizând o structură de date numită heap , un tip special de arbore binar . Odată ce lista de date a fost transformată într-o grămadă, nodul rădăcină este garantat a fi cel mai mare (sau cel mai mic) element. Când este eliminat și plasat la sfârșitul listei, grămada este rearanjată, astfel încât cel mai mare element rămas să se mute la rădăcină. Folosind heap-ul, găsirea următorului cel mai mare element necesită timp O (log n ), în loc de O ( n ) pentru o scanare liniară ca în cazul sortării simple de selecție. Acest lucru permite Heapsort să ruleze în timp O ( n log n ), iar aceasta este, de asemenea, cea mai rea complexitate.

Sortare rapida

Quicksort este un algoritm de divizare și cucerire care se bazează pe o operație de partiție : pentru partiționarea unei matrice, este selectat un element numit pivot . Toate elementele mai mici decât pivotul sunt mutate înainte de acesta și toate elementele mai mari sunt mutate după acesta. Acest lucru se poate face eficient în timp liniar și în loc . Sublistele mai mici și mai mari sunt apoi sortate recursiv. Aceasta produce o complexitate medie a timpului O ( n log n ), cu cheltuieli generale reduse, și astfel acesta este un algoritm popular. Implementările eficiente ale quicksort-ului (cu partiționare la fața locului) sunt de obicei sorturi instabile și oarecum complexe, dar se numără printre cei mai rapizi algoritmi de sortare din practică. Împreună cu utilizarea modestă a spațiului O (log n ), quicksort este unul dintre cei mai populari algoritmi de sortare și este disponibil în multe biblioteci de programare standard.

Avertismentul important despre rapiditatea rapidă este că performanța în cel mai rău caz este O ( n ² ); deși acest lucru este rar, în implementările naive (alegerea primului sau ultimului element ca pivot), acest lucru se întâmplă pentru date sortate, ceea ce este un caz obișnuit. Cea mai complexă problemă din quicksort este astfel alegerea unui element de pivot bun, deoarece alegerile constante de pivote pot duce la o performanță drastic mai lentă a O ( n ² ), dar o bună alegere a pivoturilor produce o performanță O ( n log n ), care este asimptotic optimă . De exemplu, dacă la fiecare pas se alege mediana ca pivot, atunci algoritmul funcționează în O ( n  log  n ). Găsirea medianei, cum ar fi prin mediana algoritmului de selecție a medianelor , este totuși o operație O ( n ) pe liste nesortate și, prin urmare, necesită cheltuieli generale semnificative cu sortarea. În practică, alegerea unui pivot aleatoriu produce aproape sigur performanța O ( n  log  n ).

Shellsort

Un Shellsort, diferit de sortul de bule prin faptul că mută elementele în numeroase poziții de schimb .

Shellsort a fost inventat de Donald Shell în 1959. Se îmbunătățește la sortarea prin inserție, deplasând elementele din ordinea mai multor poziții la un moment dat. Conceptul din spatele Shellsort este că sortarea prin inserție se realizează în timp, unde k este cea mai mare distanță dintre două elemente în afara locului. Aceasta înseamnă că, în general, au performanțe în O ( n ² ), dar pentru datele care sunt în mare parte sortate, cu doar câteva elemente deplasate, acestea au performanțe mai rapide. Deci, sortând mai întâi elementele îndepărtate și micșorând progresiv decalajul dintre elementele de sortat, sortarea finală se calculează mult mai repede. O implementare poate fi descrisă ca aranjarea secvenței de date într-o matrice bidimensională și apoi sortarea coloanelor matricei utilizând sortarea prin inserție. ${\ displaystyle O (kn)}$

Cel mai rău caz de complexitate temporală a Shellsort este o problemă deschisă și depinde de secvența de spațiu utilizată, cu complexități cunoscute variind de la O ( n ² ) la O ( n ^4/3 ) și Θ ( n log ² n ). Acest lucru, combinat cu faptul că Shellsort este la locul său , are nevoie doar de o cantitate relativ mică de cod și nu necesită utilizarea stivei de apeluri , îl face util în situațiile în care memoria este la un nivel superior, cum ar fi în sistemele încorporate și nucleele sistemului de operare .

Sortare cu bule și variante

Sortarea cu bule și variante precum sortul Shellsort și cocktail , sunt algoritmi de sortare simpli, extrem de ineficienți. Acestea sunt frecvent văzute în textele introductive datorită ușurinței analizei, dar sunt rareori folosite în practică.

Sortare cu bule

Un sortare cu bule, un algoritm de sortare care parcurge continuu o listă, schimbând elementele până când acestea apar în ordinea corectă.

Sortarea cu bule este un algoritm simplu de sortare. Algoritmul începe la începutul setului de date. Compară primele două elemente și, dacă primul este mai mare decât al doilea, le schimbă. Continuă să facă acest lucru pentru fiecare pereche de elemente adiacente până la sfârșitul setului de date. Apoi începe din nou cu primele două elemente, repetându-se până când nu au avut loc swap-uri la ultima trecere. Durata medie a acestui algoritm și cea mai slabă performanță este O ( n ² ), deci este rar folosit pentru a sorta seturi de date mari, neordonate. Sortarea cu bule poate fi utilizată pentru a sorta un număr mic de articole (în cazul în care ineficiența sa asimptotică nu este o penalitate mare). Sortarea cu bule poate fi, de asemenea, utilizată eficient pe o listă de orice lungime aproape sortată (adică elementele nu sunt în mod semnificativ deplasate). De exemplu, dacă un număr de elemente este deplasat cu o singură poziție (de exemplu, 0123546789 și 1032547698), schimbul sortării cu bule le va face ordine în prima trecere, a doua trecere va găsi toate elementele în ordine, astfel încât sortarea va durează doar 2 n timp.

Sortare pieptene

Comb sort este un algoritm de sortare relativ simplu bazat pe sortarea cu bule și proiectat inițial de Włodzimierz Dobosiewicz în 1980. Ulterior a fost redescoperit și popularizat de Stephen Lacey și Richard Box cu un articol din revista Byte publicat în aprilie 1991. Ideea de bază este eliminarea broaștelor țestoase , sau valori mici aproape de sfârșitul listei, deoarece într-un sortare cu bule acestea încetinesc sortarea în mod extraordinar. ( Iepurii , valori mari de la începutul listei, nu prezintă o problemă în sortarea cu bule) Se realizează acest lucru schimbând inițial elemente care sunt la o anumită distanță una de cealaltă în matrice, mai degrabă decât schimbând elemente numai dacă sunt adiacente la unul pe altul, și apoi micșorarea distanței alese până când acesta funcționează ca un tip normal de bule. Astfel, dacă Shellsort poate fi gândit ca o versiune generalizată a sortării de inserție care schimbă elemente distanțate la o anumită distanță unul de altul, sortarea pe pieptene poate fi considerată aceeași generalizare aplicată sortării cu bule.

Tip de schimb

Sortarea schimbului este uneori confundată cu sortarea cu bule, deși algoritmii sunt de fapt distincti. Schimbarea sortării funcționează comparând primul element cu toate elementele de deasupra acestuia, schimbând acolo unde este necesar, garantând astfel că primul element este corect pentru ordinea de sortare finală; apoi continuă să facă același lucru pentru al doilea element și așa mai departe. Îi lipsește avantajul pe care îl are sortarea cu bule de a detecta într-o singură trecere dacă lista este deja sortată, dar poate fi mai rapidă decât sortarea cu bule printr-un factor constant (o trecere mai puțin peste datele care trebuie sortate; jumătate din numărul de comparații totale) în situații în cel mai rău caz. La fel ca orice sortare simplă O ( n ² ), aceasta poate fi destul de rapidă pe seturi de date foarte mici, deși, în general, sortarea inserției va fi mai rapidă.

Sortare distribuție

Sortarea distribuției se referă la orice algoritm de sortare în care datele sunt distribuite de la intrarea lor în mai multe structuri intermediare care sunt apoi adunate și plasate pe ieșire. De exemplu, atât sortarea bucket , cât și flashsort sunt algoritmi de sortare bazate pe distribuție. Algoritmii de sortare a distribuției pot fi folosiți pe un singur procesor sau pot fi un algoritm distribuit , în care subseturile individuale sunt sortate separat pe diferite procesoare, apoi combinate. Acest lucru permite sortarea externă a datelor prea mari pentru a se potrivi în memoria unui singur computer.

Sortare numărare

Sortarea numărării este aplicabilă atunci când se știe că fiecare intrare aparține unui anumit set, S , de posibilități. Algoritmul rulează în timp O (| S | + n ) și memorie O (| S |) unde n este lungimea intrării. Funcționează prin crearea unei matrice întregi de dimensiuni | S | și folosind i - lea bin pentru a număra aparițiile de i - lea membru al S în intrare. Fiecare intrare este apoi numărată prin creșterea valorii coșului său corespunzător. Ulterior, matricea de numărare este realizată în buclă pentru a aranja toate intrările în ordine. Acest algoritm de sortare nu poate fi folosit adesea deoarece S trebuie să fie destul de mic pentru ca algoritmul să fie eficient, dar este extrem de rapid și demonstrează un comportament asimptotic excelent pe măsură ce n crește. De asemenea, poate fi modificat pentru a oferi un comportament stabil.

Sortare galeata

Sortarea bucket este un algoritm de sortare divizare și cucerire care generalizează sortarea numărării prin partiționarea unei matrice într-un număr finit de găleți. Fiecare cupă este apoi sortată individual, fie utilizând un algoritm de sortare diferit, fie aplicând recursiv algoritmul de sortare a cupei.

Un sortare de găleată funcționează cel mai bine atunci când elementele setului de date sunt distribuite uniform pe toate gălețile.

Sortare Radix

Sortarea Radix este un algoritm care sortează numerele prin procesarea cifrelor individuale. n numere formate din k cifre fiecare sunt sortate în timp O ( n · k ). Sortarea Radix poate procesa cifre ale fiecărui număr, fie începând de la cea mai puțin semnificativă cifră (LSD), fie începând cu cea mai semnificativă cifră (MSD). Algoritmul LSD sortează mai întâi lista cu cea mai mică cifră semnificativă, păstrând în același timp ordinea lor relativă utilizând un sortare stabilă. Apoi le sortează după următoarea cifră și așa mai departe de la cel mai puțin semnificativ la cel mai semnificativ, ajungând cu o listă sortată. În timp ce sortarea LSD radix necesită utilizarea unui sortare stabilă, algoritmul MSD radix sort nu (dacă nu se dorește sortarea stabilă). Sortarea în loc a radixului MSD nu este stabilă. Este obișnuit ca algoritmul de sortare de numărare să fie utilizat intern de sortarea radix. O abordare de sortare hibridă , cum ar fi utilizarea sortării de inserție pentru pubele mici, îmbunătățește semnificativ performanța sortării radix.

Modele de utilizare a memoriei și sortarea indexului

Când dimensiunea matricei care urmează a fi sortată se apropie sau depășește memoria primară disponibilă, astfel încât spațiul (mult mai lent) pe disc sau swap trebuie utilizat, modelul de utilizare a memoriei unui algoritm de sortare devine important și un algoritm care ar fi putut fi destul eficient atunci când matricea se potrivește ușor în RAM poate deveni impracticabil. În acest scenariu, numărul total de comparații devine (relativ) mai puțin important, iar numărul de secțiuni de memorie care trebuie copiate sau schimbate pe și de pe disc poate domina caracteristicile de performanță ale unui algoritm. Astfel, numărul de treceri și localizarea comparațiilor pot fi mai importante decât numărul brut de comparații, deoarece comparațiile elementelor din apropiere se întâmplă la viteza magistralei de sistem (sau, cu cache, chiar și la viteza procesorului ), care, comparativ la viteza discului, este practic instantanee.

De exemplu, popularul algoritm quursort recursiv oferă o performanță destul de rezonabilă cu o memorie RAM adecvată, dar datorită modului recursiv de a copia porțiuni din matrice, devine mult mai puțin practic atunci când matricea nu se potrivește în memorie RAM, deoarece poate provoca un număr de copiați lent sau mutați operațiile pe și de pe disc. În acest scenariu, un alt algoritm poate fi preferabil chiar dacă necesită comparații totale.

O modalitate de a rezolva această problemă, care funcționează bine atunci când înregistrările complexe (cum ar fi într-o bază de date relațională ) sunt sortate după un câmp cheie relativ mic, este crearea unui index în matrice și apoi sortarea indexului, mai degrabă decât întregul matrice. (O versiune sortată a întregului tablou poate fi apoi produsă cu o singură trecere, citind din index, dar deseori chiar și asta nu este necesar, deoarece indexul sortat este adecvat.) Deoarece indexul este mult mai mic decât întregul tablou, poate se potrivește cu ușurință în memorie acolo unde nu ar fi întreaga matrice, eliminând efectiv problema schimbării discului. Această procedură se numește uneori „sortare etichetă”.

O altă tehnică pentru depășirea problemei dimensiunii memoriei este utilizarea sortării externe , de exemplu una dintre modalități este de a combina doi algoritmi într-un mod care profită de puterea fiecăruia pentru a îmbunătăți performanța generală. De exemplu, matricea ar putea fi împărțită în bucăți de o dimensiune care să se potrivească în RAM, conținutul fiecărei bucăți sortate folosind un algoritm eficient (cum ar fi quicksort ), iar rezultatele fuzionate folosind o fuziune k -way similară cu cea utilizată în fuzionează sort . Acest lucru este mai rapid decât efectuarea fie a sortării fuziunii, fie a rapidității pe întreaga listă.

Tehnicile pot fi, de asemenea, combinate. Pentru sortarea unor seturi foarte mari de date care depășesc cu mult memoria sistemului, chiar și indexul poate fi necesar să fie sortat folosind un algoritm sau o combinație de algoritmi concepute pentru a funcționa în mod rezonabil cu memoria virtuală , adică pentru a reduce cantitatea de schimb necesară.

Algoritmi înrudiți

Probleme similare includ sortarea parțială (sortare numai K mai mici elemente ale unei liste, sau , alternativ , de calcul a k mai mici elemente, dar neordonate) și de selecție (calculând k mai mic element - lea). Acestea pot fi rezolvate ineficient printr-o sortare totală, dar există algoritmi mai eficienți, adesea derivați prin generalizarea unui algoritm de sortare. Cel mai notabil exemplu este quickselect , care este legat de quicksort . În schimb, unii algoritmi de sortare pot fi derivați prin aplicarea repetată a unui algoritm de selecție; quicksort și quickselect pot fi văzute ca aceeași mișcare pivotantă, diferind doar dacă se recurge de ambele părți (quicksort, divide și cucerește ) sau o parte (quickselect, micșorează și cucerește ).

Un fel de opus unui algoritm de sortare este un algoritm de amestecare . Acestea sunt fundamental diferite, deoarece necesită o sursă de numere aleatorii. Amestecarea poate fi implementată și printr-un algoritm de sortare, și anume printr-un sortare aleatorie: atribuirea unui număr aleatoriu fiecărui element al listei și apoi sortarea pe baza numerelor aleatorii. În general, acest lucru nu se face în practică și există un bine cunoscut algoritm simplu și eficient pentru amestecare: amestecul Fisher – Yates .

Vezi si

• Colationare  - Asamblarea informațiilor scrise într-o comandă standard
• Transformarea Schwartziană
• Algoritm de căutare  - Orice algoritm care rezolvă problema căutării
•  Sortare cuantică - Algoritmi de sortare pentru calculatoare cuantice

Referințe

Lecturi suplimentare

• Knuth, Donald E. (1998), Sorting and Searching , The Art of Computer Programming, 3 (ediția a doua), Boston: Addison-Wesley, ISBN 0-201-89685-0
• Sedgewick, Robert (1980), „Efficient Sorting by Computer: An Introduction”, Computational Probability , New York: Academic Press, pp.  101–130 , ISBN 0-12-394680-8

linkuri externe

• Sorting Algorithm Animations at the Wayback Machine (arhivat 3 martie 2015).
• Algoritmi de sortare secvențiali și paraleli - Explicații și analize ale multor algoritmi de sortare.
• Dicționar de algoritmi, structuri de date și probleme - Dicționar de algoritmi, tehnici, funcții comune și probleme.
• Vedere ușor sceptică asupra algoritmilor de sortare - Discută mai mulți algoritmi clasici și promovează alternative la algoritmul rapid .
• 15 Sorting Algorithms in 6 Minutes (Youtube) - Vizualizare și „audibilizare” a 15 Sorting Algorithms in 6 Minutes.
• Secvența A036604 din baza de date OEIS intitulată „Sortarea numerelor: număr minim de comparații necesare pentru sortarea n elemente” - Efectuată de algoritmul Ford – Johnson .
• Algoritmi de sortare utilizați pe picturi celebre (Youtube) - Vizualizarea algoritmilor de sortare pe multe picturi celebre.
• O comparație a algoritmilor de sortare - Execută o serie de teste a 9 dintre principalii algoritmi de sortare folosind Python timeit și Google Colab.