Sortarea este unul dintre algoritmii cei mai complexi și importanți de învățare.
Mai întâi, sortarea este sarcina obișnuită a multor aplicații informatice. Practic orice listă este mai valoroasă atunci când este sortată după un anumit principiu.
În al doilea rând, mulți algoritmi de sortare sunt exemple interesante de programare care demonstrează metode importante: comandarea privată, recursul, combinarea listelor, salvarea copacilor binare în tablouri.
Fiecare algoritm de sortare are avantajele și dezavantajele sale. Performanța diferiților algoritmi depinde de tipul de date, locația inițială, mărimea și valorile. Este important să alegeți algoritmul cel mai potrivit pentru o anumită sarcină.
Sortarea este una dintre puținele sarcini cu limite precise de performanță teoretică. Orice algoritm de sortare care utilizează comparații durează cel puțin timpul O (N * logN).
Sortați după alegere
Sortarea după alegere este un algoritm simplu O (N 2). Sarcina sa este de a căuta cel mai mic element, care apoi schimbă locurile cu elementul de la începutul listei. Apoi, se constată din elementele rămase și schimbările în locurile cu al doilea element. Procesul continuă până când toate elementele își vor lua poziția finală.
Cel mai mic element a7 = 1 este definit
Schimbarea locurilor cu primele 1 4 5 3 10 8 2
Restul este căutat din nou pentru minim și se schimbă cu cel de-al doilea 1 2 5 3 10 8 4
1 2 3 5 10 8 4 1 2 3 4 10 8 5 1 2 3 4 5 8 10 1 2 3 4 5 8 10
Pentru a implementa acest algoritm, aveți nevoie de bucle imbricate. Buclele exterioare (onI) sunt destinate pentru fixarea secvențială a elementelor matriceale, interne (onJ) - căutări pentru poziția minimă (maximă) și poziția sa. După ieșirea din bucla interioară, elementele ar trebui rearanjate. Ultimul element al ciclului exterior nu este luat în considerare: el însuși își va lua locul.
Când căutăm cel mai mic element i, algoritmul trebuie să verifice fiecare dintre elementele rămase N. Durata de execuție a algoritmului este N + (N-1) + (N-2) + ... + 1 sau O (N2).
Sortarea după alegere funcționează destul de bine cu liste în care elementele sunt aranjate aleator sau în ordine directă, dar pentru liste sortate, performanța acestui algoritm este puțin mai proastă. Pentru a căuta elementul minim al listei, selecția este efectuată de următoarea secvență de operatori:
Dacă un (j) Dacă lista este sortată în ordine inversă, condiția a (j) Acesta nu este cel mai rapid algoritm, dar este foarte simplu și, de asemenea, sortează rapid liste mici. Introducerea prin sortare este un alt algoritm de complexitate O (N2). Se bazează pe implementarea în partea sortată a matricei elementului care urmează acestei părți, dacă îndeplinește condiția de sortare. Algoritmul privește în lista ascendentă lista sursă și caută un loc în care doriți să inserați un element nou. Apoi pune noul element în poziția găsită. La prima trecere, al doilea element este comparat cu primul, cel de-al doilea - cel de-al treilea element este comparat cu primul și al doilea element și așa mai departe. Dacă elementul de verificare i + 1 satisface condiția de sortare între elemente, acesta este introdus în locul j fără să perturbe ordinea, adică elemente cu indici> = j și <=i-1 увеличивают свой индекс на 1. Pentru i = 2 Pentru n ', comparatia intotdeauna incepe b = a (i): j = 1' de la primul Do In timp ce b> a (j) 1 Pas -1 "este eliberat un loc (k) = a (k - 1)" pentru inserare Următoarea ka (j) = b 'inserați Pentru l = 1 Pentru n Picture2.Print a (l); ""; Înainte Picture2.Print Next I End Sub Numărul total de treceri este n-1. Un astfel de algoritm își petrece mult timp în căutarea poziției potrivite pentru un element nou. Funcționează mai lent decât sortarea după alegere. Selectarea cu bule este un algoritm conceput pentru a sorta liste care se află deja într-o stare aproape ordonată. Dacă această condiție este îndeplinită, atunci algoritmul este executat foarte repede, într-un moment al ordinului O (N). Dacă elementele sunt inițial aranjate într-o ordine arbitrară, algoritmul este executat în etape (N2). Cu sortarea cu bule, lista este scanată până când există două elemente adiacente care urmează în ordine. Schimbă locurile, iar lista continuă să fie explorată în continuare. După prima trecere, cel mai mic element va apărea în primul rând (în ordine crescătoare). Următorul pas va fi efectuat înainte de acest element, adică restul matricei este sortat. Algoritmul repetă acest proces până când sortează toate elementele.
Introduceți sortarea
Sortarea cu bule
Sortarea piramidelor (copaci binari)
O piramidă este un arbore binar complet în care fiecare nod este mai mare decât cei doi copii ai săi. Ambele noduri copil trebuie să fie mai mici decât nodul părinte, dar oricare dintre ele poate fi mai mare decât celălalt. Nodul rădăcină este întotdeauna cel mai mare din piramida.
Orice matrice poate fi reprezentată ca o piramidă prin plasarea primului element al matricei în rădăcina piramidei.
De exemplu, 2 4 5 3 10 8 1
Un subtree pornind de la orice nod al piramidei este, de asemenea, o piramidă.
Folosind acest fapt, puteți construi o piramidă de jos în sus. Din fiecare dintre subrețelele cu trei noduri este necesar să se formeze o piramidă. Pentru a face acest lucru, trebuie să comparați nodul de vârf cu cei doi copii ai săi. Dacă oricare dintre nodurile copil este mai mare, trebuie să îl modificați cu nodul superior. Dacă ambele noduri copil sunt mai mari, trebuie să treceți de la nodul părinte la cel mai mare dintre nodurile copil. Acest pas este repetat până când toate subrețelele sunt piramide:
Apoi, sunt create piramide mai mari: piramidele mici cu vârfurile 10 și 8 sunt combinate cu elementul 2.
Ca rezultat, chiar în partea de sus a piramidei este elementul maxim al secvenței. Am aruncat-o din piramidă și, în locul ei, a pus elementul cel mai de jos la nivelul inferior. Și din nou construim o piramidă. În partea de sus, vom obține următorul element cel mai mare și așa mai departe.
Articole similare
Trimiteți-le prietenilor: