Pe algoritmi pentru ordonarea matrice unidimensionale - Forumul Tehnic

Pe algoritmi pentru ordonarea matrice unidimensionale

De multe ori în sarcini educaționale, care sunt tranzacționate pe forumul nostru acaparează matrice ordonate, și anume Elementele sursă matrice aranjate în ordine crescătoare sau descrescătoare. Există mai multe metode (algoritmi) pentru rezolvarea acestei probleme: în urmă cu 20-30 de ani, au inventat greu, încercând să găsească „optim“, rapidă, etc. Astăzi, ținând cont de vitezele de calculatoare moderne, astfel de activități IMHO nu are sens, și se pare rezonabil de a instrui elevii în posesia a cel puțin o metodă, este cel mai bine să „bubble“, ca cea mai evidentă și simplu, dar nu este - PREDARE continuă să chinuie copiii ukazulyami, cum ar fi „utilizare metoda de introducere. " Ei bine, să se ocupe de bază.

Am observat că această metodă simplă și elegantă pentru mulți începători este dificil de înțeles și chiar întrebări de genul „de ce face o buclă dublă -?! Dimensionale matrice ceva“ etc. Unii, cu toate acestea, preferă să mindlessly din fragmentul de program undeva perekatal, astfel, tind să confunde cele două variabile buclă, care, desigur, „nu e bun“. Între timp, dacă te uiți, toată lumea poate scrie cu ușurință acest lucru este ordonarea doar „din capul meu.“
Să facem un exemplu de analiză. Limba - Pascal (care, de altfel, nu contează cu adevărat).
Să presupunem că este ordine ascendentă cerută de următoarea matrice A:
April 3 5 2 1
Numărul de elemente (5) denota n.
Codul:

Cred că sensul corpului buclei este clar: în cazul în care elementul anterior nu mai urmează, acestea sunt schimbate. În acest caz, rețineți că variabila exterioară buclă ca un index de matrice nu este folosit, este - doar un contor. Dar pentru a fi într-adevăr clar, vom urmări secvența programului:

Deci, amintiți-vă, locația originală:

Primul pasaj al buclei interioare (i = 1, j variază de la unu la 4 = 5-1):
3 (pozițiile schimbate ale elementelor 1 și 2) 4 5 1 2
April 3 5 2 1 (a doua și a treia sunt corecte)
3 (pozițiile schimbate 3 și 4 elemente) 4 2 5 1
3 (pozițiile schimbate 4 și 5 itemi) 4 2 1 5

Este ușor de înțeles că ori de câte ori există un element de maximă, după încheierea primului ciclu intern, acesta va fi ultima, adică în cazul în care acesta face parte. Mai mult, această poziție nu va fi atins, pentru că următoarea bucla internă merge de la 1 la 5-2 = 3:
03 aprilie 2 1 5 (prima și a doua poziție este corectă)
3 (pozițiile schimbate 2 și 3 elemente) 2 4 1 5
3 (pozițiile schimbate 3 și 4 elemente) 2 1 4 5

Acesta este al doilea cel mai mare element (4) în poziție. Următorul ciclu de j - 1 până la 5-3 = 2:
2 (cifre schimbate 1 și 2 elemente) 3 1 4 5
2 (pozițiile schimbate 2 și 3 elemente) 1 3 4 5

Și, în sfârșit, ultimul pasaj al j - 1 până la 1:
1 (cifre schimbate 1 și 2 elemente) 2 3 4 5

Totul! După cum puteți vedea, matrice este sortat, problema este rezolvata.
De ce este numit în continuare o „metoda cu bule“? Și imaginați-vă oferta noastră sub forma unui recipient vertical îngustă, cu un lichid, în cazul în care indicii de jos - este „de jos“, și bătrânii - „Partea de sus“. Apoi, mișcarea elementului de-a lungul șirului de plutitoare ca o bulă de aer în recipient. analogie vizuală simplă.
Desigur, dacă aveți nevoie pentru a aranja elementele care nu sunt în ordine crescătoare în ordine descrescătoare, este necesar doar pentru a schimba semnul inegalității într-o declarație condiționată.

Acesta este considerabil inferior „balon“, în simplitate și claritate și, în plus, necesită utilizarea de recepție artificiale - adăugarea de elemente auxiliare suplimentare (posibil și fără ea, dar atunci programul devine greoaie). Linia de jos: lasa primul dintre elementele deja n „comandate“, adică primul loc este cel mai mic element. Apoi, pornind de la al doilea mod suplimentar ca în „bubble“ permutare pairwise lanț „persecutat“ dreapta, elementele - primul, al doilea, apoi al treilea și așa mai departe până la n-lea. Dar cum să-și îndeplinească condiția ca primul loc a fost cel mai mic element? Dar pentru această „față“ și se agață de o matrice o dată „zero“ într-un element rând, cu siguranță, mai puțin decât ceilalți. cod:

sortare Selectarea metodei

Totul e destul de simplu - găsi cel mai mic element, schimbarea de locuri cu primul, apoi găsi cel mai mic de altă parte, schimbarea de locuri cu al doilea, etc. până la penultima, care, dacă este necesar, pentru a schimba locurile cu acesta din urmă. cod:

Aici - atenție! METODA Shelley rezolvă problema În cele din urmă, el efectuează doar preliminar de clasificare „dur“, și în cele din urmă caz ​​introdusă prin introducerea sau bule. Essence: interschimbate inițial elemente ascendente distanțate la n / 2 poziții (adică, în cazul în care n = 6, apoi 1 la 4, 2 până la 5 și 3 până la 6), apoi "distanța" împărțită la doi (rotunjite, desigur), iar procedura se repetă, și așa continuă atâta timp cât „teren“ devine egal cu 1. cod:

Sortarerapidă Metoda (Hoare algoritm)

Considerat unul dintre cele mai rapide și mai eficiente. În același timp, foarte nenaglyaden și greu de înțeles. Shell este oarecum similar cu algoritmul, dar, spre deosebire de acesta din urmă, aduce pentru a sorta. În continuare, voi împrumuta practic material din Wikipedia. atât în ​​ceea ce privește caietul de sarcini și în lista de program.
Pașii sunt după cum urmează:

1. Selectați un element din matrice, care va fi numit elementul de susținere. Din punct de vedere al corectitudinii alegerii algoritmului a elementului de sprijin este indiferent.
2. Operația de separare matrice: reorganiza matrice, astfel încât toate elementele care au o valoare mai mică sau egală cu elementul de referință, se întoarse spre stânga sa și toate elementele care depășesc valoarea de referință - dreapta. Algoritmul de funcționare normală:
   1. Două index - l și r. egală cu indicele minim și maxim al șirului partajat, respectiv.
   2. Se calculează indicele elementului de referință m.
   3. Index l crește succesiv până când elementul l-lea nu ar fi mai mare sau egală cu referința.
   4. Indicele r scade la secvențial până când elementul-r-lea este egal cu sau este mai mică decât referința.
   5. Dacă r = l - găsit mid array - operație de separare este finalizată, ambii indicatori indicați spre elementul de susținere.
   6. Dacă l
3. comanda recursiv sub-matrice, situată pe partea stângă și dreaptă a membrului de sprijin.
4. recursie de bază sunt truse compuse din unul sau două elemente. Originea revine la forma sa inițială, cea de a doua, dacă este necesar, sortarea reduce la interschimba cele două elemente. Toate aceste segmente au comandat deja în procesul de separare.

Deoarece fiecare iterație (fiecare următorul nivel de recursie) lungimea intervalului array procesat scade cu cel puțin unul, terminalul de ramură recursie este atinsă și prelucrarea este necesara pentru a garanta completă.

Punerea în aplicare a algoritmului poate fi executat ca folosind recursie, și fără ea. În acest din urmă caz, programul este extins în mod semnificativ.

Aici este comanda program de listare întreg matrice ascendentă utilizând o procedură recursiv:

Am venit aici peste această dimineață pentru o altă metodă. Simplu și prostie. Din moment ce eu nu știu cum se numește, și este acolo nici un fel la toate, să o numim „metoda XXXX“.
Linia de jos: introduceți un b-box variabilă booleană și începe trecerea multiplă a șirului de la început până la sfârșit prin schimbarea elementelor adiacente „dezordonate“, la fel și atâta timp cât o astfel de „dezordonate“ cupluri nu rămân, adică, având în vedere înainte de următorul pasaj din valoarea de pavilion va rămâne aceeași (dacă îndeplinește cel puțin o pereche de „întâmplare“, caseta de validare este activată). cod:

__________
Mai jos sunt capturi de ecran prin care se dispune de aceeași matrice de toate metodele avute în vedere. Încă o dată să atragă atenția asupra „incompletitudinea“ a metodei de Shell.

__________________
Cu Mozilla Firefox - direct la comunism!