Rezumat: Cursul discută definire și clasificare algoritmii pentru tablouri de sortare, în special sortarea, rapid, a studiat parametrii ce caracterizează complexitatea algoritmilor, sortare, sunt considerate ca descrierea și exemplele de cod de program următor algoritmi de sortare rapidă: heapsort binar, îmbinare sortare, sortare shell și sortare Hoare.
Scopul prelegerii. învăța algoritmii de bază pentru sortare internă și să învețe cum să rezolve problema de sortare matrice folosind diferite metode (heapsort binar. Metoda Shell, sortarea rapidă Hoare, îmbinare sortare).
Sortarea este una dintre sarcinile fundamentale de programare algoritmică. O mulțime de cercetări științifice au fost dedicate rezolvării problemelor legate de sortare și au fost elaborate numeroase algoritmi.
În general, sortarea ar trebui înțeleasă ca procesul de regrupare a unui anumit set de obiecte într-o anumită ordine. Sortarea este aplicată în toate domeniile de programare, fără excepție, fie că sunt baze de date sau programe matematice.
Un algoritm de sortare este un algoritm pentru ordonarea unui anumit set de elemente. De obicei, algoritmul de sortare înseamnă un algoritm pentru ordonarea setului de elemente în ordine ascendentă sau descendentă.
În cazul elementelor cu aceleași valori, într-o ordine ordonată, ele sunt aranjate una lângă alta în orice ordine. Cu toate acestea, uneori este util să păstrăm ordinea originală a elementelor cu aceleași valori.
În algoritmii de sortare, doar o fracțiune din date este utilizată ca cheie de sortare. Cheia de sortare este un atribut (sau mai multe atribute), valoarea cărora determină ordinea elementelor. Astfel, atunci când se scriu algoritmi pentru sortarea matricelor, trebuie avut în vedere faptul că cheia coincide complet sau parțial cu datele.
Aproape fiecare algoritm de sortare poate fi împărțit în 3 părți:
- o comparație care determină ordinea unei perechi de elemente;
- permutare. schimbarea unor elemente;
- algoritmul de sortare, care compară și rearanjează elementele până când sunt ordonate toate elementele setului.
Algoritmii de sortare sunt de mare folos practic. Ele pot fi găsite acolo unde este vorba de procesarea și stocarea unor cantități mari de informații. Unele sarcini de procesare a datelor sunt mai ușor de rezolvat dacă datele sunt pre-comandate.
Evaluarea algoritmilor de sortare
Nicio altă problemă nu a generat mai multe soluții diferite decât problema de sortare. Un algoritm universal de sortare optimă nu există în prezent. Cu toate acestea, având caracteristicile aproximative ale datelor de intrare. este posibil să alegeți o metodă care să funcționeze optim. Pentru aceasta, este necesar să se cunoască parametrii prin care vor fi evaluați algoritmii.
- Timpul de sortare este parametrul principal care caracterizează viteza algoritmului.
- Memoria este unul dintre parametrii, caracterizat prin faptul că un număr de algoritmi de sortare necesită alocarea unei memorii suplimentare pentru stocarea temporară a datelor. Când se evaluează memoria utilizată, spațiul ocupat de setul de date original și costurile independente de secvența de intrare nu vor fi luate în considerare, de exemplu, pentru stocarea codului de program.
- Stabilitatea este un parametru care este responsabil pentru faptul că sortarea nu schimbă poziționarea relativă a elementelor egale.
- Naturitatea comportamentului este un parametru care indică eficacitatea metodei atunci când procesează date deja sortate sau parțial sortate. Algoritmul se comportă în mod natural dacă ia în considerare această caracteristică a secvenței de intrare și funcționează mai bine.
Clasificarea algoritmilor de sortare
Toate varietatea și diversitatea de algoritmi de sortare pot fi clasificate în funcție de diverse criterii, cum ar fi stabilitatea comportamentului, cu privire la utilizarea comparațiilor, pentru cerințe suplimentare de stocare, după cum este necesar în cunoașterea structurii de date, dincolo de operațiunea de comparație, și altele.
Cea mai detaliată considerație este clasificarea algoritmilor de sortare pentru domeniul de aplicare. În acest caz, tipurile de bază de ordonare sunt împărțite după cum urmează.
- Interfața de sortare internă este un algoritm de sortare care utilizează numai memoria on-line a computerului (RAM) în procesul de secvențiere a datelor. Asta este, RAM este suficient pentru a pune într-o serie sortată de date cu acces aleatoriu la orice celulă și de fapt pentru a executa algoritmul. Sortarea internă este utilizată în toate cazurile, cu excepția citirii datelor cu o singură trecere și a înregistrării cu o singură trecere a datelor sortate. În funcție de algoritmul particular și de implementarea acestuia, datele pot fi sortate în aceeași zonă de memorie sau pot fi utilizate memorii RAM suplimentare.
- Sortarea externă este un algoritm de sortare care utilizează memorie externă atunci când efectuează secvențierea datelor. de regulă, hard disk-uri. Sortarea externă este concepută pentru a gestiona liste mari de date care nu se încadrează în memoria RAM. Accesul la medii diferite impune anumite restricții suplimentare asupra acestui algoritm: accesul la mediu se realizează într-o manieră secvențială, adică în fiecare moment al timpului este posibilă citirea sau notarea numai a elementului următor celui curent; Cantitatea de date nu le permite să se încadreze în memoria RAM.
Interpretarea internă este fundamentală pentru orice algoritm extern de sortare - părțile individuale ale matricei de date sunt sortate în memorie RAM și sunt conectate la o singură matrice folosind un algoritm special. ordonat de către cheie.
Trebuie remarcat faptul că sortarea internă este mult mai eficientă decât cea externă, deoarece durează mult mai puțin timp pentru a accesa memoria RAM decât pentru mass-media.
Să luăm în considerare algoritmii de bază de sortare internă, care se numesc algoritmi avansați (logaritmici).
Sortare binară piramidală
Această metodă de sortare a fost propusă de J.W.J. Williams și R.U. Floyd în 1964. Sortarea cu piramide este într-un fel o modificare a acestei abordări, cum ar fi sortarea prin alegere. singura diferență fiind faptul că elementul minim (sau maxim) din secvența nesortată este selectat pentru un număr mai mic de operații. Pentru o astfel de alegere rapidă, o structură este construită din această secvență nesortată. Este esența acestei metode și constă în construirea unei astfel de structuri, care se numește o piramidă.
O piramidă (arbore de sortare, grămadă binară) este un arbore binar cu frunze ordonate (rădăcina copacului este elementul cel mai mic sau cel mai mare). Piramida poate fi reprezentată ca o matrice. Primul element al piramidei este cel mai mic sau cel mai mare, în funcție de cheia de sortare.
Screening-ul - este de a construi o nouă piramidă pe următorul algoritm: un nou element este plasat în partea de sus a arborelui, apoi se misca ( „ecranate“), pe drum în jos prin comparație cu copiii. Coborârea este terminată dacă rezultatul comparației cu copii corespunde cheii de sortare.
Secvența numerelor xi, xi + 1. xn formează o piramidă. dacă pentru toate k = i, i + 1. n / 2, următoarele inegalități dețin: xk> x2k. xk> xi (sau xk Gama de numere 12 10 7 5 8 7 3 este o piramidă. O astfel de matrice este reprezentată convenabil ca un copac. Primul element al matricei, ale cărui elemente formează o piramidă. este cea mai mare (sau cea mai mică). Dacă matricea este reprezentată ca o piramidă. atunci matricea este ușor de sortare. Algoritmul de sortare piramidală. Pasul 1. Transformați matricea într-o piramidă (Figura 42.1.A).
Articole similare
Trimiteți-le prietenilor: