Algoritm de sortare

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare
Un exemplu de ordonare stabilă pe cărțile de joc.
Un exemplu de ordonare 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ă permită întotdeauna compararea a două elemente ale setului): relațiile de ordine parțiale dau naștere algoritmilor de ordonare 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 ( ) ș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 impusă prin adăugarea unui index mic la fiecare cheie înainte de sortare sau prin alungirea în alt mod a cheilor pe care să funcționeze, pentru a le face unice, păstrând în același timp informații despre 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, sortând î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 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 alcătuite din înregistrări , cheile sunt adesea alcătuite din combinația dintre unul sau mai multe câmpuri ale înregistrării în sine (acest lucru se întâmplă în mod regulat în bazele de date relaționale ). 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

Căutarea și optimizarea algoritmilor de sortare este foarte importantă pentru unele câmpuri de computer și pentru aceste clase de algoritmi au fost dovedite diverse teoreme care definesc limitele lor. Cel mai important este următorul:

Teorema: complexitatea timpului oricărui algoritm de sortare a comparației este egală cu , unde N este numărul de elemente care trebuie sortate.

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. Algoritmi de sortare total cuantici au fost ipotizați (dar nu au fost produși), care pot avea o limită inferioară mai mică de complexitate.

Demonstrație

Vrem să arătăm că complexitatea se află într-un algoritm de comparație și schimb . Introduceți o secvență 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 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. este numărul de frunze din arborele de decizie unde n este numărul de articole de sortat. La tine acasa frunzele și din moment ce arborele este binar, înălțimea arborelui va fi:

Î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 .

Pentru a completa dovada folosim formula Stirling pentru aproximarea lui .

numărul de comparații

care la nivel asimptotic corespunde .

Copac copac

Fiecare operație a algoritmului de sortare poate fi analizată printr-un copac binar . 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:

Lista algoritmilor de sortare

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

Următorul tabel enumeră câțiva algoritmi de sortare, raportând complexitatea acestora la cel mai bun , mediu și cel mai rău caz , 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 2 ) Θ ( n 2 ) Θ (1) Da Da Algoritm pentru comparație prin schimb de elemente
B sort - - - - - - -
Sortare B-Tree - - - - - - -
Sortare bitonică O (log 2 n ) O (log 2 n ) O (log 2 n ) O ( n log 2 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 2 ) O ( n 2 ) Θ (1) da da A. pentru comparație prin schimburi, îmbunătățirea sortării inserției
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 2 ) Θ ( n 2 ) Θ (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. pentru comparație hibridă, 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 2 ) O (jurnal n ) Nu - -
Sortare Plasel - - - - - - -
Sortare rapida Θ ( n jurnal n ) Θ ( n jurnal n ) O ( n 2 ) 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 (vezi Sedgewick), să coste doar O ( n jurnal n ) folosind Quickselect , să utilizeze mai multe pivote 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 de sortat
Sortare ondulată - - - - - - -
Sortare selecție Θ ( n 2 ) Θ ( n 2 ) Θ ( n 2 ) Θ (1) Nu Da A. pentru comparație prin selecția elementelor
Mai multe tipuri unice - - - - - - -
Un fel de agitator O ( n ) Variază O ( n 2 ) Θ (1) Da Da A. pentru comparație prin schimbul de elemente, îmbunătățirea sortării Bubble . 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 2 n ) O ( n log 2 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. pentru comparație prin unirea 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 ( n ~ log (3) / log (1.5) ) - Nu Da A. pentru comparație prin partiționare, de tip recursiv. Variantele sale pot fi stabile

Bibliografie

Alte proiecte

linkuri externe

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