Algoritm de sortare

Un exemplu de comandă stabilă pe cărțile de joc.

Un algoritm de sortare (( EN ) algorithm de sortare ) este un algoritm care este utilizat pentru a poziționa elementele unui set conform unei secvențe stabilite printr-o relație de ordine , astfel încât fiecare element să fie mai mic (sau mai mare) decât ceea ce urmează. În absența altor specificații, relația de ordine este întotdeauna considerată totală (adică, astfel încât să facă întotdeauna posibilă comparația între două elemente ale setului): relațiile de ordine parțiale dau naștere algoritmilor de sortare topologică . În funcție de direcția relației luate în considerare, o ordine poate fi ascendentă sau descendentă.

Criterii de partiționare

Pentru a analiza și studia algoritmii de sortare, au fost definite diferite criterii de partiționare, analizate mai jos.

Comandare internă și externă

Dacă fișierul care urmează a fi sortat sau structura datelor poate fi conținută în memorie, metoda se numește internă. Sortarea fișierelor rezidente pe disc sau bandă se numește sortare externă: principala diferență între cele două tipuri de sortare este că, în timp ce în prima puteți accesa direct o înregistrare, în cea din urmă înregistrările trebuie adresate secvențial sau cel mult pentru blocuri mari.

Comparație-schimb și sortare digitală

În funcție de tipul de operație care se efectuează, există două tipuri diferite de sortare: sortarea care face comparații și schimburi ( $a\leq b:exch(a,b)$ ${\ displaystyle a \ leq b: exch (a, b)}$ $a \ leq b: exch (a, b)$ ) și algoritmul digital care accesează informațiile printr-un grup de biți la un moment dat.

Sortare adaptivă

De obicei, un algoritm de sortare folosește operații de comparație și schimb. Dacă aceste operații sunt efectuate independent de datele de intrare, algoritmul este definit ca neadaptativ. În timp ce dacă o metodă de sortare efectuează diferite secvențe de operații în funcție de rezultatul comparațiilor, avem un algoritm adaptativ.

Stabilitatea unui algoritm

Se spune că o metodă de sortare este stabilă dacă păstrează ordinea relativă a datelor cu chei egale în fișierul care urmează a fi sortat. De exemplu, dacă sortați în funcție de an de curs o listă de studenți deja sortați alfabetic, o metodă stabilă produce o listă în care studenții din același an sunt încă în ordine alfabetică, în timp ce o sortare instabilă va produce probabil o listă fără urmă de comanda anterioară.

Stabilitatea poate fi forțată prin adăugarea unui index mic la fiecare cheie înainte de sortare sau prin alte prelungiri ale tastelor pe care trebuie să funcționeze, astfel încât să le facă unice, păstrând în același timp informațiile privind poziția relativă a elementelor.

Algoritmi la locul lor

Un algoritm este numit algoritm în loc atunci când nu creează o copie a intrării pentru a atinge obiectivul, legea în acest caz. Prin urmare, un algoritm în loc economisește memorie în comparație cu un algoritm care nu este în loc. De fapt, trebuie remarcat faptul că, deși considerațiile făcute asupra complexității au sens în general, ele au o importanță decisivă asupra numărului mare. De asemenea, proprietatea de a fi la locul sau nu.

Relații de ordine și chei

Relația de ordine dintre elementele setului poate fi:

cea naturală (dacă există) pentru mulțimea considerată (de exemplu relația dintre $\leq$ ${\ displaystyle \ leq}$ $\ leq$ pentru subseturi de numere naturale)
o relație definită de nevoile aplicației.

Este frecvent cazul în care algoritmul de sortare nu funcționează direct pe datele de interes, ci pe un set diferit de date care sunt în legătură unu-la-unu cu cel al datelor de interes: aceasta se numește setul de chei. În cazul frecvent în care datele sunt compuse din înregistrări , cheile sunt adesea formate prin combinarea unuia sau mai multora dintre aceleași câmpuri de înregistrare (acest lucru se întâmplă în mod regulat în baza de date relațională ). Scopul metodelor de sortare este de a rearanja înregistrările astfel încât cheile lor să fie aranjate într-o ordine bine definită (de obicei în ordine numerică sau alfabetică). Caracteristicile specifice ale cheilor și înregistrărilor pot varia foarte mult de la o aplicație la alta. Noțiunea abstractă de ordonare este independentă de aceste caracteristici.

Complexitatea algoritmilor de sortare

Cercetarea și optimizarea algoritmilor de sortare sunt foarte importante pentru anumite domenii IT și pentru aceste clase de algoritmi au fost demonstrate mai multe teoreme care definesc limitele. Cel mai important este următorul:

Teorema: complexitatea timpului oricărei comparații de algoritmi de sort este egală cu

\Omega (NlogN)

{\ displaystyle \ Omega (NlogN)}

{\ displaystyle \ Omega (NlogN)}

Unde N este numărul de articole care trebuie comandate.

Această teoremă stabilește limita inferioară de complexitate pentru algoritmi bazată pe compararea perechilor de chei (prin comparație). Nu se știe nimic despre alți algoritmi de sortare, nici măcar ce ar putea fi aceștia. Au fost supuși (dar nu produse) algoritmi de sortare total cuantici , care pot avea o limită inferioară de complexitate mai mică.

Demonstrație

Doriți să arătați că într-un algoritm de comparație și complexitate comerțul are ${\mathsf {\Omega }}(n\log n)$ ${\ displaystyle {\ mathsf {\ Omega}} (n \ log n)}$ ${\ mathsf \ Omega} (n \ log n)$ . Introduceți o secvență $e_{1},e_{2},...e_{n}$ ${\ displaystyle e_ {1}, e_ {2}, ... e_ {n}}$ $e_ {1}, e_ {2}, ... e_ {n}$ de n elemente, acțiunea algoritmului poate fi reprezentată ca un arbore binar, pentru fiecare secvență de intrare va exista o cale în interiorul arborelui, acest lucru se datorează faptului că există o permutare a secvențelor, de fapt numărul de permutări posibile pe n elementele sunt $n!$ ${\ displaystyle n!}$ $n!$ combinații care corespund numărului de frunze de pe copac.

Având în vedere două permutări distincte, ele identifică căi diferite în interiorul copacului. $n!$ ${\ displaystyle n!}$ $n!$ este numărul de frunze din arborele de decizie unde n este numărul de articole de sortat. La tine acasa $n!$ ${\ displaystyle n!}$ $n!$ frunzele și din moment ce arborele este binar, înălțimea arborelui va fi:

$h(T)\leq \lceil \log _{2}n!\rceil$ ${\ displaystyle h (T) \ leq \ lceil \ log _ {2} n! \ rceil}$ $h (T) \ leq \ lceil \ log _ {2} n! \ rceil$

Înălțimea arborelui corespunde numărului de comparații, un element indicativ al timpului de execuție al algoritmului. În cel mai rău caz, adică, când ajungi în partea de jos a copacului, vei avea o complexitate egală cu $\geq \lceil log_{2}n!\rceil$ ${\ displaystyle \ geq \ lceil log_ {2} n! \ rceil}$ $\ geq \ lceil log_ {2} n! \ rceil$ .

Pentru a completa dovada folosind formula lui Stirling pe aproximarea lui $n!$ ${\ displaystyle n!}$ $n!$ .

numărul de comparații $\geq ({\frac {1}{2}}\log _{2}2\pi +{\frac {1}{2}}\log _{2}n+n\log _{2}n-n\log _{2}e)\sim n\log _{2}n$ ${\ displaystyle \ geq ({\ frac {1} {2}} \ log _ {2} 2 \ pi + {\ frac {1} {2}} \ log _ {2} n + n \ log _ {2 } nn \ log _ {2} e) \ sim n \ log _ {2} n}$ $\ geq ({\ frac {1} {2}} \ log _ {2} 2 \ pi + {\ frac {1} {2}} \ log _ {2} n + n \ log _ {2} nn \ log _ {2} e) \ sim n \ log _ {2} n$

care la nivel asimptotic corespunde ${\mathsf {\Omega }}(n\log n)$ ${\ displaystyle {\ mathsf {\ Omega}} (n \ log n)}$ ${\ mathsf \ Omega} (n \ log n)$ .

Copac copac

Fiecare operație de algoritm de sortare poate fi analizată prin intermediul unui arbore binar de acoperire. Pentru a comanda o secvență de n elemente, va fi necesar să efectuați un număr de operații egal cu înălțimea minimă a unui arbore binar cu k frunze:

$h(T)\geq \lceil \log k\rceil$ ${\ displaystyle h (T) \ geq \ lceil \ log k \ rceil}$ $h (T) \ geq \ lceil \ log k \ rceil$

Lista algoritmilor de sortare

Există diverse clase de algoritmi de sortare, cei mai cunoscuți și utilizați pentru comparație sunt algoritmii de sortare ( algoritmi de sortare de comparație), dar există și alte clase caracterizate printr-un timp de rulare în cel mai rău caz mai mic decât O (n log n).

Următorul tabel listează câțiva algoritmi de sortare, raportând complexitatea cazului Best, Worst Middle și memoria suplimentară necesară și stabilitatea. Două convenții sunt utilizate în tabel: algoritmii sunt implementați pe matrice de chei întregi; complexitatea de calcul a algoritmilor de sortare a comparației derivă numai din numărul de comparații făcute.

Nume	Îmbunătăţi	Mediu	Mai rea	Memorie	Grajd	La loc	Notă
Sortare Avl	-	-	-	-	-	-	-
Sortare cu bule	Θ (n)	Θ (n ²⁾	Θ (n ²⁾	Θ (1)	Da	Da	Algoritm pentru comparație prin schimb de elemente
B sort	-	-	-	-	-	-	-
Sortare B-Tree	-	-	-	-	-	-	-
Sortare bitonică	O (log ² n)	O (log ² n)	O (log ² n)	O (n log ² n)	-	-	A. paralela nu se bazează pe comparație
Bogosort	Pe)	O (n · n!)	∞	Θ (1)	Nu	Da	A. nu se bazează pe comparație
Btm	-	-	-	-	Da	Nu	-
Sortare de gnomi	O ( n )	O (n ²⁾	O (n ²⁾	Θ (1)	da	da	A. comparație prin intermediul schimburilor, îmbunătățirea sortării Insertion
Sortare grămadă	O (n jurnal n)	O (n jurnal n)	O (n jurnal n)	Θ (1)	Nu	Da	A. pentru comparație prin selecție, optim
Sortare prin inserție	Θ (n)	Θ (n ²⁾	Θ (n ²⁾	Θ (1)	Da	Da	A. pentru comparație prin inserție
Sortare numărare	Θ (n + k)	Θ (n + k)	Θ (n + k)	O (k)	Da	Nu	A. nu se bazează pe comparație. k = max (A) -min (A) +1, unde A este matricea. versiunea in-place nu este stabilă, versiunea non-in-place folosește un spațiu O (n + k) și este stabilă.
Introducere sort	O (n jurnal n)	O (n jurnal n)	O (n jurnal n)	O (jurnal n)	Nu	da	A. Hibrid pentru comparație, derivat din sortare Heap și sortare rapidă
Salt sort	-	-	-	-	-	-	-
Merge sort	Θ (n jurnal n)	Θ (n jurnal n)	Θ (n jurnal n)	O ( n )	Da	Nu	A. pentru comparație prin îmbinarea componentelor, optimă și ușor de paralelizat
Doamna sort	-	-	-	-	-	-	-
Oet sort	-	-	-	-	-	-	-
Sortarea pacientului	O (n jurnal n)	O (n jurnal n)	O (n jurnal n)	O ( n )	Da	Nu	A. pentru comparație prin partiționare și selecție, optim și ușor de paralelizat
Sortare partiție	O (n jurnal n)	O (n jurnal n)	O (n ²⁾	O (jurnal n)	Nu	-	-
Sortare Plasel	-	-	-	-	-	-	-
Sortare rapida	Θ (n jurnal n)	Θ (n jurnal n)	O (n ²⁾	O ( n )	Nu	Da	A. pentru comparație prin partiționare. Variantele sale pot: să fie stabile, să utilizeze numai O (jurnal n) de memorie (v. Sedgewick), să coste doar O (n jurnal n) folosind Quickselect , să utilizeze mai mult pivot etc.
Sortare Radix	O (n · k / s)	O (n · k / s)	O (n · k / s)	O ( n )	Da	Nu	A. nu se bazează pe comparație. k este numărul mediu de cifre ale tastelor care trebuie comandate
Sortare de tip ondulare	-	-	-	-	-	-	-
Sortare selecție	Θ (n ²⁾	Θ (n ²⁾	Θ (n ²⁾	Θ (1)	Nu	Da	A. pentru comparație prin selecția elementelor
Mai multe tipuri unice	-	-	-	-	-	-	-
Un fel de agitator	O ( n )	Variază	O (n ²⁾	Θ (1)	Da	Da	A. pentru comparație prin schimb de elemente, îmbunătățirea sortării cu bule . Cunoscut și sub numele de Cocktail sort
Sortare de forfecare	-	-	O (n jurnal n)	-	-	-	A. pentru compararea matricilor bidimensionale
Sortare Shell	O ( n )	O (n ^1,5) / O (n log ² n)	O (n log ² n)	Θ (1)	Nu	Da	A. Pentru comparație, complexitatea sa depinde de secvența de spațiu utilizată.
Sortare simplă	-	-	-	-	-	-
Somn de somn	O ( n )	-	O (k)	Θ (1)	da	da	A. nu se bazează pe comparație. k este egal cu max (A), unde A este matricea. Algoritmul are nevoie de un proces paralel independent pentru fiecare element al matricei.
Sortare netedă	O ( n )	O (n jurnal n)	O (n jurnal n)	O ( n )	-	-	A. compararea Fuzionării componentelor, îmbunătățirea tipului „ Heap ”
Sortare răsărit	O (n jurnal n)	O (n jurnal n)	O (n jurnal n)	O ( n )	Nu	-	-
Trippel sort	-	-	O ^(log n ^{~ (3) / log (1.5))}	-	Nu	Da	A. pentru comparație prin partiționare, de tip recursiv. Variantele sale pot fi stabile

Bibliografie

(EN) DE Knuth , The Art of Computer Programming , Volumul 3: Sortare și căutare.

Alte proiecte

Wikiversitatea conține resurse de algoritm de sortare
Wikimedia Commons conține imagini sau alte fișiere pentru algoritmul de sortare

linkuri externe

Un scurt ghid pentru sortarea și căutarea algoritmilor
(EN) Explicația și analiza multor algoritmi , pe iti.fh-flensburg.de.
(EN) Java Applet care arată grafic funcționarea anumitor algoritmi , pe cs.oswego.edu.
(EN) curs despre algoritmi disponibil gratuit online de la MIT. Diverse lecții se referă la algoritmi de sortare pe ocw.mit.edu.

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

V · D · M Algoritmi de sortare
Teorie	Teoria complexității de calcul · notație Big O · Matrice · Listă · Stack · 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