Algoritmul de sortare este un algoritm pentru comanda elementelor dintr-o listă. În cazul în care elementul de listă are mai multe câmpuri, câmpul care servește ca criteriu de comandă se numește cheia de sortare. În practică, cheia este adesea un număr, iar în câmpurile rămase sunt stocate toate datele care nu afectează funcționarea algoritmului.
Formularea problemei
,
Presupunem că fiecare element (în plus față de celelalte informații nu afectează genul) este cheia asociată. Pe setul de chei este dată o relație de ordinul unei ordini liniare (sau perfecte). pentru care ar fi îndeplinite următoarele condiții:
legea trichotomiei. pentru orice, fie, fie;
tranzitivitate. pentru orice și apoi.
Sarcina de a sorta prin nondecreasing este de a găsi o permutare a elementelor cu indicii din, la care cheile sunt aranjate în ordinea descrescătoare:
Ca urmare a algoritmului și a utilizării permutării, obținem matricea sortată:
În mod similar, puteți defini sortarea prin non-creștere.
Evaluarea algoritmului de sortare
Algoritmii de sortare sunt estimate prin viteza de execuție și eficiența utilizării memoriei:
Timpul este parametrul principal care caracterizează viteza algoritmului. Se mai numește și complexitate computațională. Pentru a ordona cel mai rău este important. medie și cel mai bun comportament al algoritmului în termenii puterii setului de intrare A. Dacă setul A este alimentat la intrarea algoritmului, atunci vom denota cu n = | A |. Pentru un algoritm tipic, comportamentul bun este O (n log n) iar comportamentul rău este O (n 2). Comportamentul ideal pentru comanda este O (n). Algoritmii de sortare care utilizează doar o operație de comparație cheie abstractă necesită întotdeauna cel puțin o comparație Ω (n log n). Cu toate acestea, există Khan algoritm de sortare (Yijie Han) cu calcul complexitatea O (n log log n log log log n), exploatând faptul că spațiul este limitat cheie (este extrem de dificil, iar pentru O -oboznacheniem factor foarte mare de acoperire ceea ce face imposibilă utilizarea în practica de zi cu zi). Există și noțiunea de sortare a rețelelor. Presupunând că mai multe comparații pot fi efectuate simultan (de exemplu, în calcul paralel), este posibil să sortați n numere pentru operațiile O (log 2 n). În acest caz, numărul n trebuie să fie cunoscut în prealabil;
Memorie - un număr de algoritmi necesită alocarea de memorie suplimentară pentru stocarea temporară a datelor. Ca regulă, acești algoritmi necesită o memorie O (log n). La evaluarea nu este considerat un loc care ia matrice originală și independentă a secvenței de intrare a costurilor, de exemplu, pentru stocarea de cod de program (deoarece toate aceste potreblyaetO (1)). Algoritmii de sortare care nu consumă memorie suplimentară sunt numite sortare la fața locului.
Proprietăți și clasificare
Stabilitatea (stabilitate stabilă) - sortarea stabilă nu modifică poziția relativă a elementelor cu aceleași taste [3].
Naturitatea comportamentului este eficacitatea metodei atunci când se prelucrează datele deja comandate sau parțial ordonate. Algoritmul se comportă în mod natural dacă ia în considerare această caracteristică a secvenței de intrare și funcționează mai bine.
Utilizarea operației de comparare. Algoritmii care utilizează compararea elementelor între ei pentru sortare sunt numiți pe baza comparațiilor. Complexitatea minimă a celui mai rău caz pentru acești algoritmi este O (n log n), dar acestea sunt flexibile în aplicarea lor. Pentru cazuri speciale (tipuri de date), există algoritmi mai eficienți.
O altă proprietate importantă a algoritmului este domeniul său de aplicare. Aici principalele tipuri de comenzi sunt două:
Sortarea internă funcționează cu rețele care sunt în întregime în RAM cu acces aleatoriu la orice celulă. Datele sunt de obicei aranjate în același loc, fără costuri suplimentare.
În arhitecturile moderne de calculatoare personale, paging-ul și cache-ul de memorie sunt utilizate pe scară largă. Algoritmul de sortare ar trebui să fie bine combinat cu algoritmii cache și swap utilizați.
memorii externe de sortare funcționează un volum mare de dispozitive, dar nu cu acces aleator și secvențiale (organiza fișiere), T. E. În acest moment este „văzut“ doar un singur element, și rebobinare costurile în comparație cu memorie inutil de mare. Acest lucru impune anumite restricții suplimentare asupra algoritmului și duce la metode speciale de comandă, de obicei utilizând spațiu pe disc suplimentar. În plus, accesul la date în memoria externă este mult mai lent decât operațiile cu RAM.
Accesul la mass-media este realizată într-un mod coerent: la fiecare moment poate fi citit sau scrie doar element de după cel curent.
Cantitatea de date nu le permite să fie localizate în RAM.
De asemenea, algoritmii sunt clasificați după:
nevoia de memorie suplimentară sau absența acesteia
nevoia de cunoaștere a structurii datelor dincolo de scopul operațiunii de comparație sau a lipsei acesteia
Lista algoritmilor de sortare
În acest tabel, n este numărul de înregistrări care urmează să fie comandate și k este numărul de chei unice.
Algoritmi de sortare stabilă
Selecția sortimentului - Complexitatea algoritmului: O (n 2); Căutați elementul cel mai mic sau cel mai mare și plasați-l la începutul sau la sfârșitul unei liste ordonate
veziculă sortare (angl.Bubblesort) - algoritm de complexitate: O (n2); Pentru fiecare pereche de indici, se face un schimb, dacă elementele nu sunt aranjate în ordine.
Sortarea agitare (Shaker, Cocktail sort, bidirecțională bule sort) - algoritm de complexitate: O (n 2)
Sortarea dwarven - are în comun cu sortarea unei bule și inserții de sortare. Complexitatea algoritmului este O (n 2).
Insertion sort - Complexitatea algoritmului: O (n 2); Determinați unde ar trebui să fie elementul curent în lista ordonată și introduceți-l acolo
Merge sort - Complexitatea algoritmului: O (n log n); O (n) memorie suplimentară este necesară; Construim separat prima și a doua jumătate a listei și apoi îmbinăm listele ordonate
Sortarea cu un arbore binar (English.Treesort) - Complexitatea algoritmului: O (n log n); Necesită o memorie suplimentară O (n)
Algoritmul de sortare Timsort (English.Timsort) - complexitatea algoritmului: O (n log n); O (n) memorie suplimentară este necesară; Algoritm combinat (folosind sortarea inserției și sortarea fuziunii, dezvoltat pentru utilizarea în Python [
Numărarea sorții - Complexitatea algoritmului: O (n + k); Este necesară o memorie suplimentară O (n + k) (sunt luate în considerare 3 variante)
Blocul de sortare (Sortarea în formă de cupă) - Complexitatea algoritmului: O (n); Necesită O (k) memorie suplimentară și cunoașterea naturii datelor sortate, care depășesc funcțiile "rearanjați" și "comparați".
Statistici de sortare nesigure
Selecția sortimentului - Complexitatea algoritmului: O (n 2); Căutați elementul cel mai mic sau cel mai mare și plasați-l la începutul sau la sfârșitul unei liste ordonate
Shell sort - Complexitatea algoritmului: O (n log 2 n); încercați să îmbunătățiți sortarea inserției
Combinație sortare - Complexitatea algoritmului: O (n log n)
Sortarea Pyramid (Heap Sort, Heapsort) - Complexitatea algoritmului: O (n log n); transforma lista într-o grămadă. luați cel mai mare element și adăugați-l la sfârșitul listei
Smoothsort - complexitatea algoritmului: O (n log n)
Sortarerapidă (sortarerapidă), în exemplul de realizare, cu costuri minime de memorie - complexitatea algoritmului: O (n log n) - timpul mediu, O (n 2) - cel mai rău caz; cunoscuta ca cea mai rapida cunoscuta pentru comanda listelor aleatoare mari; cu împărțirea setului original de date în două jumătăți, astfel încât orice element al primei jumătăți să fie ordonat față de orice element din a doua jumătate; atunci algoritmul se aplică recursiv la fiecare jumătate. Când utilizați O (n) memorie suplimentară, puteți face sortarea stabilă.
Introsort - algoritm de complexitate: O (n log n), o combinație de rapid și heapsort. Sortarea cu piramide este utilizată dacă adâncimea de recursiune depășește log (n).
Selecția sorții: O (n log n) - cel mai rău caz, necesită o memorie O (n), de asemenea, găsește cea mai lungă secvență crescătoare
Stooge sort este un algoritm recursiv de sortare cu o complexitate de timp.
Bitwise sorting - Complexitatea algoritmului: O (n · k); O (k) este necesară o memorie suplimentară.
Sortarea digitală este identică cu sortarea Bitwise.
Modele de sortare nepractice
Bogosort - O (n · n!) În medie. Combinați arbitrar matricea, verificați ordinea.
Sortați după permutare - O (n · n!) - cel mai rău timp. Pentru fiecare pereche, ordinea corectă este verificată și toate permutările posibile ale matricei originale sunt generate.
Tipul stupid - O (n 3); versiunea recursivă necesită O (n 2) memorie suplimentară
Sortarea bilelor - O (n) sau O (√n) necesită hardware specializat
Selecția pancake - O (n), necesită hardware specializat
Algoritmi care nu se bazează pe comparații
Blocul de sortare (sortare după cupă)
Un fel lexicografic sau bitwise (sortare Radix)
Numărarea sorții
Alți algoritmi de sortare
Articole similare
Trimiteți-le prietenilor: