Sortare toate gradele - fundații - Pascali - Articole Directory - liber programabile

Sortarea de tot felul

Mai întâi a venit algoritmii mai nepretențioase inventat ulterior mai eficient. Deși pentru a spune tot în acest articol nu este posibil, voi descrie cele mai comune și faimos.

In mod normal, algoritmi de sortare sunt împărțite în două tipuri - sortare matrice și sortare secvențe. În acest articol, ne vom concentra pe modul de sortare o serie de cele mai comune sarcini atunci când creați un program de procesare a datelor. Prin „matrice“ Vreau să spun matrice unidimensională. Cred că, pentru că nu va fi dificil să se scrie după ce a citit articolul de sortare algoritmul de matrice bidimensional sau mai mult. Scopul meu - nu pentru a vă scrie un program gata făcute, și să introducă ideea, metoda. Pentru practic pentru o descriere a algoritmului va urma codul sursă al programului de probă în Pascal. De ce Pascal? Da, pentru că este limba cea mai comună pentru scopuri didactice. Și, în opinia mea, Pascal cele mai potrivite pentru a demonstra mecanismele de sortare.

Pentru a evalua eficiența algoritmului, vom folosi două valori: numărul de comparații cheie (K) și numărul transporturilor de elemente (S). Cea din urmă valoare este de mare interes pentru noi - trimite date în memorie este mai mult timp decât comparația. De asemenea, în descrierea I se va folosi algoritmi cantități: n - numărul elementelor de matrice A [1..n] - matrice sortate, x - variabile de același tip ca și elementele de matrice. Presupunem că avem un tablou de întregi (A: array [l..n] integer; x: integer;).

În funcție de numărul de comparații necesare algoritmii de sortare sunt împărțite în două clase: un simplu apel despre n ^ 2 comparații și mai eficiente - de ordinul a log n * (n). Voi începe cu algoritmi de simplu și intuitiv. Metoda de sortare prima, pe care vreau să-ți spun, este numit „sortarea prin conexiune directă.“ Ideea este că luăm ordinea elementelor de matrice și a pus pe locul lor „de drept“. Din al doilea, am itera prin toate elementele de matrice și compara succesiv cu elemente care au un indice mai mică decât aceasta. Dacă elementul nostru mai puțin decât precedentul, apoi le rearanja și să continue să compare în continuare, în cazul în care mai mult, atunci lăsați - este deja în vigoare. Și așa a mers până când, până când vom ajunge la granița stângă a șirului. În vederea în acest caz procesul de comparare nu este lăsat în afara graniței din stânga al șirului este necesară pentru a crea așa-numita „bariera“ - a adăugat la începutul celulei matrice (de exemplu, A [0]), care va aduce sortate în acest element de trecere. Aici este codul complet al algoritmului:

Aici, A [0] - deasupra barierei A [1..n] - array sortat.

Sfatul meu pentru cei mai simpli algoritmi de sortare a încerca să scrie pe hârtie orice secvență de numere 4-5. Și apoi „alerga“ l pe o bucată de hârtie printr-un algoritm de sortare. În acest caz, scrie valorile tuturor variabilelor și a modificărilor în matrice la fiecare pas. Nu este atât de dificil de făcut pentru primele trei algoritmi și nu va dura mai mult de jumătate din foaia de notebook-uri. Astfel, mult mai ușor de înțeles algoritmul. Desigur, pentru metode îmbunătățite de acest lucru reprezintă o provocare semnificativă, dar în acest caz, există o ieșire. De exemplu, în Delphi puteți rula programul pas cu pas și urmăriți valorile tuturor variabilelor programului - un lucru foarte util pentru a înțelege modul în care unele dintre programele. Nu neglija acest sfat!

Numărul mediu de comparație cheie și transmiterea elementelor au următoarele valori: K = (n ^ 2 + n 2) / 4, S = (n ^ 2 +-9n 10) / 4 Valorile maxime și minime sunt: ​​Kmin = n-1, Smin = 3 * (n-1), kmax = (n ^ 2 + n-4) / 4, Smax = (n ^ 2 + 3n-4) / 2. În algoritmul, există un dezavantaj semnificativ. Să presupunem că avem o serie de numere: 3,7,4,6,8,2. În acest caz, ultimul element de matrice (2) va trebui să „trageți“ pe întreaga matrice.

Să algoritm în cazul în care mișcarea se face la distanțe mari. Acest algoritm se numește „sortare de selecție directă.“ Ea se bazează pe următoarea idee: alege cel mai mic element din matrice și schimba locul cu prima, apoi repetați această operație pentru elementele rămase atâta timp cât va exista doar un singur element. Următoarele este algoritmul în sine:

În acest caz, nici o barieră (A [0]) nu este necesară, și considerăm matrice în intervalul [1..n].

Tasta de comparare: K = (n ^ 2-n) / 2. Pentru a trimite cheile pentru a calcula valoarea medie a usor, deoarece cita minim (chei deja sortate) și maxime (tastele sunt inversate) valori: Smin = 3 * (n-1), Smax = n ^ 2/4 + 3 * (nl) . După cum puteți vedea, algoritmul de selecție directă în cele mai multe cazuri de conectare directă în mod eficient. Singura excepție este o situație în care matrice este deja sortate sau aproape sortate. Cu toate acestea, în acest caz, câștigul nu este la fel de mare, și, în general, această metodă este preferabilă celei anterioare.

Și ultimul tip de primă clasă de sortare se numește „sortarea schimb direct.“ Diferența principală a acestei metode de mai sus două - schimbul este caracteristic acestui algoritm. Ideea algoritmului obține secvențial peste două elemente adiacente sunt comparate și, dacă este necesar, schimbă locurile. Se repetă această operație atât timp cât ordinea întreaga matrice.

În aceste pasaje vom trece prin matrice de cel mai mic element la marginea din stânga. Dacă ne gândim la matrice ca lanț vertical, produsele vor fi sortate când bulele „plutesc“ la nivelul lor. Prin urmare, un nume bine-cunoscut al metodei - pentru „sortarea balon“. Aici este codul pentru acest algoritm:

Se folosește variabila f ca un steag. Dacă f = true, atunci, în ultimul pasaj au fost făcute de permutare și au nevoie de mai multe treceri, iar dacă f = false, atunci permutarea în ultima trecere nu a fost, iar matrice este deja sortate. În acest algoritm, există, de asemenea, un dezavantaj: În cazul în care cel mai mic număr este situat la capătul șirului, în scopul de a se trece la partea de sus (în locul său „drept“) necesită n-1 trece. Între timp, de la începutul celui mai mare element al matrice se va muta la sfârșitul o singură trecere. Sunt de acord fapt destul de neplăcut. Concluzia este clară: este necesar să se treacă matrice din unghiuri diferite, la un moment dat, și anume prima dată de la începutul până la sfârșitul celei de a doua - de la capăt la început, al treilea - din nou, de la început până la sfârșit, etc. O astfel de algoritm îmbunătățit numit „se agită .... sort »(ShakerSort). Dar programul pentru acest tip de ofertă de a se scrie. Dacă sunt complet terminat cu metoda de sortare cu bule, nu va fi pentru tine o provocare.

contoriza numărul de chei comparații și expedieri este dificil de bule și se agită de soiuri. Prin urmare, în mod obiectiv compara eficacitatea ultimelor două metode cu anterioare, putem la sfârșitul articolului - Eu va oferi o serie de algoritmi de sortare de timp.

Acum am ajuns aproape de a discuta despre metodele de sortare îmbunătățite. Înțelege-le mult mai dificil. În 1959, oferta D. Shell îmbunătățită de sortare a conexiunii directe. Ideea este destul de simplu. În primul rând, sorteze elementele distanțate în regiunea 4. De exemplu, luați elementul A [1] și se compară cu elementul A [5] (A [4 + 1]), când A [1] este mai mare decât A [5] apoi le rearanja. Atunci A [2] și pentru a compara o [6] și așa mai departe. D. După această trecere cu „trimestru“, sortarea se trece din nou prin matrice, dar sorteze elementele distanțate în regiune 2. Și în ultima trecere este de obicei unică de sortare. distanțează de secvență poate fi modificată, precum și cantitatea acestora. Prin urmare, pentru a rezuma toate distantele T incluse în matrice s [1..t]. Sorteaza fiecare distanta este la fel de sortare includerea directă. Condiții de sortare sfârșitul va trebui să instalați o barieră și nu una.

Dar tocmai am împărtășit matrice, și trebuie să-l rezolve. De aceea, aplicăm aceeași operație de separare pentru fiecare jumătate, apoi injumatateste pentru jumătățile și t. D. Finish divizare când fiecare parte va consta dintr-un singur element. Atunci când construirea unui program de acest algoritm este cel mai bine să utilizați recursivitate:

În principal de rutină sortarerapidă apel subrutina sortarea elementelor 1 la n. Într-o subrutină de sortare vom lua pentru x mijlocul acestui interval și au o serie de metoda de mai sus. Apoi, acest apel subrutina din nou, dar jumătățile și t. D. De altfel, x și w ar trebui să fie de același tip ca și elementele de matrice.

În acest caz, valoarea medie a S = (n-1 / n) / 6.

Acum este necesar să se rezume rezultatele și concluziile (a se vedea. Tabelul). Pentru evaluarea obiectivă a eficienței algoritmilor de sortare a da timp de aceeași matrice (elementele sunt aranjate la întâmplare) prin diverse metode. Din tabel vedem că tipul cu bule și versiunea îmbunătățită (tremurul PR) este mult mai rău decât toate celelalte. Metode îmbunătățite. De remarcat că numai Deși metoda Shell a demonstrat rezultate foarte bune, cel mai bun este încă sortarerapidă. Prin modul în care, în cazul în care matrice este deja sortate, toate metodele eficiente pentru a arăta rezultate mai slabe decât de obicei.