Algoritmii de sortare sunt un set de instrucțiuni care iau o matrice sau o listă ca intrare și aranjează articolele într-o anumită ordine.
Sortările sunt cel mai frecvent în ordine numerică sau sub formă de ordine alfabetică (numită lexicografică) și pot fi în ordine crescătoare (AZ, 0-9) sau descendentă (ZA, 9-0).
Conţinut
De ce sunt importante algoritmii de sortare
Deoarece sortarea poate reduce adesea complexitatea unei probleme, este un algoritm important în informatică. Acești algoritmi au aplicații directe în algoritmi de căutare, algoritmi de baze de date, metode de divizare și cucerire, algoritmi de structură a datelor și multe altele.
Unele algoritmi de sortare obișnuiți
Unii dintre cei mai comuni algoritmi de sortare sunt:
- Selecție Sortare
- Sortare cu bule
- Sortare prin inserție
- Merge Sort
- Sortare rapida
- Sortare în grămadă
- Numărare Sortare
- Radix Sort
- Sortare cupă
Clasificarea algoritmului de sortare
Algoritmii de sortare pot fi clasificați pe baza următorilor parametri:
- Bazat pe numărul de swapuri sau inversiuni Acesta este de câte ori algoritmul schimbă elemente pentru a sorta intrarea.
Selection Sort
necesită numărul minim de swap-uri. - Bazat pe numărul de comparații Acesta este de câte ori algoritmul compară elemente pentru a sorta intrarea. Folosind Notare Big-O, exemplele de algoritm de sortare enumerate mai sus necesită cel puțin
O(nlogn)
comparații în cel mai bun caz șiO(n^2)
comparații în cel mai rău caz pentru majoritatea rezultatelor. - Bazat pe recursivitate sau nerecursiune Unii algoritmi de sortare, cum ar fi
Quick Sort
, utilizați tehnici recursive pentru a sorta intrarea. Alți algoritmi de sortare, cum ar fiSelection Sort
sauInsertion Sort
, utilizați tehnici non-recursive. În cele din urmă, un algoritm de sortare, cum ar fiMerge Sort
, utilizați atât tehnici recursive, cât și tehnici non-recursive pentru a sorta intrarea. - Pe baza stabilității, se spune că sunt algoritmi de sortare
stable
dacă algoritmul menține ordinea relativă a elementelor cu chei egale. Cu alte cuvinte, două elemente echivalente rămân în aceeași ordine în ieșirea sortată așa cum erau în intrare. -
Insertion sort
,Merge Sort
, șiBubble Sort
sunt stabile -
Heap Sort
șiQuick Sort
nu sunt stabile - Pe baza cerinței de spațiu suplimentar se spune că algoritmii de sortare sunt
in place
dacă necesită o constantăO(1)
spațiu suplimentar pentru sortare. -
Insertion sort
șiQuick-sort
suntețiin place
sortează pe măsură ce mutăm elementele din pivot și nu folosim de fapt o matrice separată, ceea ce NU este cazul în sortare combinată în care dimensiunea intrării trebuie alocată în prealabil pentru a stoca ieșirea în timpul sortării. -
Merge Sort
este un exemplu deout place
sortați, deoarece necesită spațiu de memorie suplimentar pentru operațiunile sale.
Cea mai bună complexitate de timp posibilă pentru orice sortare bazată pe comparație
Orice algoritm de sortare bazat pe comparație trebuie să facă cel puțin nLog2n comparații pentru a sorta matricea de intrare, iar sortarea Heapsort și merge sunt sortimente de comparație asimptotice optime. Acest lucru poate fi ușor dovedit prin trasarea diagramei arborelui decizional.
#Explicarea #algoritmilor #sortare
Explicarea algoritmilor de sortare