Sortarea este una dintre sarcinile fundamentale de programare algoritmică. Soluția problemelor legate de ordonarea elementelor unui anumit set este dedicată unui număr mare de investigații și este determinată o serie de algoritmi.
Sortarea trebuie înțeleasă ca procesul de rearanjare un anumit set de obiecte într-o anumită ordine a facilita căutarea ulterioară pentru un anumit element dintr-un set dat, iar elementele sub obiecte arbitrare Sortable pot fi înțelese din numerele și simbolurile în formule matematice. În orice caz, sortarea poate fi reprezentată după cum urmează:
- Sunt date mai multe elemente (A1, A2, ..., An). Este necesar să se efectueze permutarea lor în ordine (Ak1, Ak2, ... Akn) astfel încât elementele să respecte funcțiile de ordonare F (Ak1) <= F(Ak2) <= … <= F(Akn), при этом вводят понятие "ключ сортировки".
- Cheia de sortare este atributul elementului, a cărui valoare este ordonarea.
Orice algoritm de sortare este compus din 3 părți:
1) comparație. ordonarea unei perechi de elemente;
2) permutarea. permițând schimbarea a două elemente (A2 în loc de A1, A1 în locul lui A2);
3) algoritmul corespunzător de sortare. care compară și rearanjează elementele până când sunt ordonate toate elementele setului.
Există o gamă destul de largă de algoritmi de sortare, fiecare dintre acestea având anumite caracteristici și este convenabil de utilizat în acest caz sau în acel caz. Pentru a evalua și compara algoritmi de sortare, se introduce un set de parametri:
1) timpul de sortare - parametrul principal care caracterizează viteza algoritmului.
2) memoria este un parametru caracterizat prin faptul că algoritmul necesită memorie suplimentară pentru a stoca temporar valorile sortate. Când se evaluează memoria utilizată, cantitatea de memorie utilizată pentru a stoca setul original (set) nu este luată în considerare.
3) stabilitate - parametrul responsabil pentru faptul că sortarea nu schimbă poziția relativă a elementelor egale în valoare. Stabilitatea este corectă dacă elementele sunt ordonate de cheile secundare, adică Prin atributele care nu sunt reflectate în cheia de sortare principală.
1a 3q 1b 1c 2z: matricea originală (index, valoare)
1a 1b 1c 2z 3q: sortare stabilă
1c 1b 1a 2z 3q: sortare instabilă
4) caracterul natural al comportamentului - un parametru care indică eficiența sortimentului atunci când procesează date deja sortate sau parțial sortate. Se crede că algoritmul se comportă natural dacă ia în considerare această caracteristică a secvenței de intrare (mai bine sau nu mai rău).
Toți algoritmii de sortare care pot fi executați pot fi împărțiți în două clase principale:
1) sortarea internă. algoritmii de sortare internă definesc procesul de ordonare a elementelor care sunt localizate în memoria de operare a dispozitivului de calcul. Se presupune că în orice moment puteți accesa orice element al setului sortat. Sortarea internă este utilizată în toate cazurile, cu excepția citirii și scrierii cu un singur pas a datelor sortate.
2) sortarea externă. sortarea atunci când efectuează secvențierea datelor folosește suporturi externe. Sortarea externă permite procesarea unor cantități mari de date care nu se încadrează în memoria RAM. Aceasta impune o restricție datorită faptului că accesul la elementele sortate se realizează numai secvențial, adică La un moment arbitrar în timp, poate fi accesat numai 1 element sortat curent.
Metodele de sortare internă sunt împărțite în mod universal și special. Universal -> simplă și îmbunătățită. Metodele simple și îmbunătățite diferă în ceea ce privește eficacitatea acestora. Metodele speciale sunt concepute pentru a sorta informații despre o anumită structură.
Metode simple pentru sortarea matricelor.
Metodele simple pentru sortarea matricelor sunt:
Trasarea cu bule este cel mai simplu algoritm de sortare pentru realizare și înțelegere, dar este eficient numai pentru rețelele mici. Complexitatea algoritmului este n ^ 2.
Acest algoritm este considerat educativ și practic nu este aplicat în afara literaturii educaționale; În schimb, în practică se folosesc algoritmi mai eficienți de sortare. În același timp, acest algoritm stă la baza unor algoritmi mai avansați, cum ar fi sortarea piramidală și sortarea rapidă.
Algoritmul constă în treceri repetate prin matricea sortată. Pentru fiecare trece elementele comparate succesiv reciproc, iar în cazul în care ordinea în pereche nu este corectă, elementele sunt schimbate. Treceri prin matrice de repetate N-1 ori sau până până când acesta este la pasajul următor că schimburile nu mai sunt necesare, ceea ce înseamnă - matrice este sortat. Cu fiecare trecere a algoritmului buclei interioare, următorul mare element matrice este pus în locul său, la sfârșitul unei matrice lângă anterior „cel mai mare element“, iar cel mai mic element este mutat o poziție la partea superioară a șirului ( „plutește“ în poziția dorită ca un flacon în apă, prin urmare și numele algoritmului).
Sortarea printr-un balon nu modifică poziționarea relativă a elementelor egale și nu utilizează memorie suplimentară.
- Algoritmul este natural și stabil.
- Complexitatea complexă a algoritmului.
Sortarea după alegere este una dintre metodele clasice de secvențiere bazate pe operația de comparație.
Poate fi stabilă și instabilă.
- Se găsește elementul minim (maxim) al secvenței. Pentru aceasta, primul element este comparat cu al doilea, primul cu cel de-al treilea și așa mai departe. Numărul elementului găsit este marcat.
- Dacă indicele primului element nu este identic cu acest element, atunci ele schimbă valori.
- Sortarea continuă pe partea sortată a matricei.
Numărul de comparații: N ^ 2
- Această metodă de sortare este preferată în cazul în care înregistrările fișierelor sunt uriașe, iar tastele ocupă un spațiu mic.
- Acest algoritm produce cel mai mic număr de mișcări de date, decât metoda de selecție.
- Procesul de identificare a elementului minim într-o singură trecere nu oferă informații despre locul unde va fi localizat elementul minim următor.
- Pe o cantitate mare de date, această sortare este ineficientă.
Acest algoritm aliniază matricea rezultată cu un singur element la un moment dat. Este mult mai puțin eficient pe liste mari decât metode îmbunătățite de sortare (qsort / hsort). Cu toate acestea, acest algoritm are următoarele avantaje:
- Eficace pe seturi de date mici
- Cel mai bun caz este O (n)
- Necesită numai memorie O (1) suplimentară
Dezavantaje - complexitate computațională ridicată O (n ^ 2).
La fiecare pas, selectați unul dintre elementele de date de intrare și este inserat în poziția dorită într-o listă deja sortate, atâta timp cât setul de date de intrare este epuizată. Metoda de selectare a următorului element al șirului sursă este arbitrară; aproape orice algoritm de alegere poate fi utilizat. De obicei, elementele sunt introduse în ordinea în care apar în matrice de intrare.
Merge sortarea este un algoritm de sortare care organizează liste (sau alte structuri de date care pot fi accesate numai secvențial) într-o anumită ordine. În primul rând, sarcina este împărțită în sub-sarcini mai mici, apoi sunt rezolvate printr-un apel recursiv sau direct dacă dimensiunea lor este suficient de mică. Ulterior, soluțiile lor sunt combinate și se obține o soluție a problemei inițiale. Folosit pentru sortarea externă.
Cel mai rău caz este O (n log (n)).
Sortarea matricei este împărțită în 2 rețele de aproximativ aceeași dimensiune. Fiecare dintre piesele rezultate este împărțită de același algoritm până când lungimea fiecărei părți este 1; atunci aceste părți ale matricei sunt unite într-una și sortate.
- Sortarea este stabilă.
- Eficace atunci când procesează date cu un timp de acces lung.
- Cea mai bună modalitate de a sorta listele legate.
- Algoritmul este convenabil pentru structurile cu acces secvențial la elemente.
- Necesită spațiu suplimentar (O (1)).
- Inferioară la viteza de sortare rapidă.
Articole similare
Trimiteți-le prietenilor: