Sortare directă. Algoritmi și structuri de date Funcția metodei simple de includere c

Această metodă este utilizată pe scară largă atunci când se joacă cărți. Elementele (cărțile) sunt împărțite mental în secvența deja „gata” A1 ... An și secvența originală Ai ... An. La fiecare pas, pornind de la i=2 și crescând I de fiecare dată cu unul, al-lea element este extras din secvența originală și transferat în secvența terminată și este introdus în locul potrivit.

Mai sus este prezentat ca exemplu procesul de sortare prin includerea a opt numere selectate aleatoriu: Algoritmul pentru acest sortare este următorul:

PENTRU i:=2 TO n DO

includerea lui x în locul corespunzător dintre a ... a[j];

În procesul real de căutare a unui loc potrivit, este convenabil, alternând comparațiile și mișcările prin secvență, să cerneți X, așa cum ar fi, adică X este comparat cu următorul element aj și apoi fie X este inserat într-un gol. spațiu, sau aj este deplasat (transmis) la dreapta, iar procesul „se duce” la stânga. Vă rugăm să rețineți că procesul de cernere se poate termina dacă este îndeplinită una dintre următoarele două condiții diferite:

1. Se găsește un element aj cu o cheie mai mică decât cheia lui X.

2. S-a ajuns la capătul din stânga secvenței terminate.

Acest caz tipic al unui proces repetat cu două condiții de terminare ne permite să folosim cunoscuta tehnică de barieră (sentinelă). Poate fi aplicat cu ușurință aici prin setarea unei bariere a0 cu valoarea X. (Rețineți că pentru aceasta este necesar să extindeți intervalul indicelui în descrierea variabilei a la 0 ... n.)

Analiza metodei includerii directe. Numărul de comparații cheie (Ci) în timpul i-a cernere este cel mult egal cu i - 1, cel puțin 1; Dacă presupunem că toate permutările n chei sunt la fel de probabile, atunci numărul mediu de comparații este i/2. Numărul de transferuri (atribuții de elemente) Mi este egal cu Ci + 2 (inclusiv bariera). Prin urmare, numărul total de comparații și numărul de transferuri sunt următoarele:

Salvare = (n2 + n - 2)/4,

Сmax = (n2 + n - 4)/4,

M min = З*(n - 1),

M ave = (n2 + 9n - 10)/4,

M max = (n2 + 3n - 4)/2.

Estimările minime apar în cazul unei secvențe inițiale de elemente deja ordonate, în timp ce estimările cele mai proaste apar atunci când sunt aranjate inițial în ordine inversă. În anumite privințe, sortarea prin includere prezintă un comportament cu adevărat natural. Este clar că algoritmul de mai sus descrie procesul de sortare stabilă: ordinea elementelor cu chei egale rămâne neschimbată.

Algoritmul cu incluziuni directe poate fi îmbunătățit cu ușurință dacă acordați atenție faptului că secvența gata (a1 ... ai-1 în care trebuie să introduceți un nou element este deja ordonată ea însăși. Este firesc să vă concentrați pe căutarea binară , în care se încearcă compararea cu mijlocul secvenței gata, iar apoi procesul de înjumătățire continuă până când este găsit punctul de inserare. Acest algoritm de sortare modificat se numește metoda de inserare binară.

Această metodă este utilizată pe scară largă atunci când se joacă cărți. Elementele (cărțile) sunt împărțite mental în secvența deja „gata” A 1 , A 2 ,…, A i -1 și partea „rămasă” (nesortată): A i , A i +1 ,…, A N .

Esența metodei este că la fiecare pas i-a (începând de la i = 2), i-lea element este îndepărtat din partea nesortată și plasat în partea „gata” și este introdus în locul potrivit.

Algoritmul text al metodei:

1. Început.

2. Buclă până când i are valori de la 2 la N,
pas = 1:

a) plasați al-lea element (A(i)) în celula A(0);

b) atribuiți j = -1, adică j este egal cu numărul elementului situat în stânga subiectului (i-al-lea) și stă astfel în secvența „gata”;

c) dacă A(0) ≥ A(j), atunci plasați elementul A(0) în celula A(j+1), altfel plasați elementul A(j) în celula A(j+1), reduceți valoarea de j cu unu și executați din nou pasul c.

În fig. Figura 1 prezintă o diagramă bloc a sortării folosind metoda includerii directe.

Metoda funcționează astfel: la pasul i (începând de la i = 2), i-lea element este plasat într-o celulă liberă (de exemplu, A(0)). Acest element este comparat cu elementul care se află în partea „finisată” din stânga acestuia. Dacă elementul A(0) este mai mic, atunci elementul comparat (j-al-lea element) este deplasat la dreapta cu o poziție, după care următorul element este luat pentru comparație. Dacă elementul A(0) nu este mai mic în timpul comparării, atunci acesta este plasat în locul imediat după elementul comparat.

Orez. 1. Organigrama de sortare folosind metoda includerii directe

În fig. Figura 2 prezintă un exemplu de realizare a sortării utilizând metoda includerii directe.

Secvența originală
	A (0)
I = 2
I = 3
I = 4
I = 5
I = 6
I = 7
I = 8
Rezultat

Orez. 2. Exemplu de sortare prin includere directă

Sortarea directă este mai potrivită pentru cazul în care datele sortate ajung secvenţial (una după alta).

Sortare prin selecție directă

Esența metodei este următoarea. Cel mai mic element din partea „rămasă” (nesortată) este selectat și schimbat cu primul element (din aceeași parte nesortată). După aceasta, lungimea piesei nesortate se reduce cu un element (primul), iar întregul proces continuă cu (n – 1) elemente, apoi cu (n – 2) elemente etc., până când există un singur element. stânga.cel mai mare element.

Această metodă este într-un fel opusă metodei de includere directă. În metoda includerii directe, la fiecare pas, sunt luate în considerare doar un element următor și toate elementele părții deja „gata” a secvenței, printre care se găsește punctul de includere a acestui element următor. Și în metoda de selecție directă, pentru a găsi un element (minimal), toate elementele părții nesortate sunt examinate, iar acest element minim este plasat ca un alt element în partea deja „gata”.

Algoritmul text al metodei:

1. Început.

2. Buclă până când i are valori de la 1 la N – 1,
pas = 1:

a) plasați elementul curent (i-al-lea) într-o celulă de memorie (X) și amintiți-vă numărul de serie (i) al elementului curent (în variabila K);

b) executați o buclă în timp ce j are valori de la i + 1 (adică de la elementul de lângă i) până la N, pas = +1:

corpul buclei: dacă X > A(j), atunci plasați elementul A(j) în celula X și amintiți-vă numărul în celula K;

c) atribuiți A(K) = A(i) și A(i) = X.

În fig. Figura 3 prezintă un exemplu de realizare a sortării utilizând metoda de selecție directă.

Secvența originală	44						06
I = 1		55	12
I = 2			55			18
I = 3				42		55
I = 4					94		44
I = 5						55	94
I = 6							94	67
I = 7

Orez. 3. Exemplu de sortare prin selecție directă

Sortarea prin includere directă, ca sortarea prin selecție simplă, este de obicei folosită pentru tablourile care nu conțin elemente duplicate.

Sortarea prin metoda includerii directe, ca toate cele descrise mai sus, se realizează în etape. La pasul k, se consideră că partea din tablou care conține primele k-1 elemente este deja ordonată, adică

a ≤ a ≤ ... ≤ a .

În continuare, trebuie să luați al-lea element și să alegeți un loc pentru acesta în partea sortată a matricei, astfel încât după inserarea lui, ordonarea să nu fie încălcată, adică trebuie să găsiți un j (1 ≤ j ≤ k -1) astfel încât a [j] ≤ a[ k]< a. Затем вставить элемент а [k] на найденное место.

Cu fiecare pas, partea sortată a matricei crește. Pentru a efectua o sortare completă, va trebui să efectuați n-1 pași.

Să ne uităm la acest proces cu un exemplu. Să presupunem că doriți să sortați o matrice de 10 elemente în ordine crescătoare folosind metoda includerii directe

1 - pasul

13 6 8 11 3 1 5 9 15 7 Considerăm o parte a matricei dintr-un element

ment (13). Trebuie să introduceți al doilea în el

element al tabloului (6) astfel încât să fie ordonat

s-a păstrat. Din 6< 13, вставляем

6 pe primul loc. Piesa sortata

tabloul conține două elemente (6 13).

3 - pasul

6 8 13 11 3 1 5 9 15 7 Următorul element este 11. Este scris în partea ordonată a matricei pe locul al treilea, deoarece 11 > 8, dar 11< 13.

5- Etapa

3 6 8 11 13 1 5 9 15 7 Din același motiv, scriem 1 ca primul

6 - Etapa

1 3 6 8 11 13 5 9 15 7 Deoarece 5 > 3, dar 5< 6 то место 5 в упоря-

Partea terminată este a treia.

7 -Etapa

1 3 5 6 8 11 13 9 15 7 Locul numărului 9 este al șaselea.

8 -Etapa

1 3 5 6 8 9 11 13 15 7 Stabilirea locului penultimului

Elementul 15. Rezultă că acest element

Matricea este deja la locul lui.

9 -Etapa

1 3 5 6 8 9 11 13 15 7 Tot ce rămâne este să găsim un loc potrivit pentru

Ultimul element (7).

1 3 5 6 7 8 9 11 13 15 Matricea este complet sortată.

Acum putem descrie pe scurt un fragment al algoritmului de sortare folosind metoda includerii directe:

Pentru k: = 2 To n Do

(deoarece începem să sortăm prin găsirea unui loc potrivit pentru a, i variază de la 2 la n)

„inserați x într-un loc potrivit în a, ..., a[k]”

Rămâne să răspundem la întrebarea cum să găsiți un loc potrivit pentru elementul x. Să procedăm astfel: vom căuta prin elementele situate în stânga lui x (adică cele care sunt deja ordonate), trecând la începutul matricei. Trebuie să căutați prin elementele lui a[ j ], j variază de la k-1 la 1. Acest aspect trebuie să se încheie când este îndeplinită una dintre următoarele condiții:

· element a[j] găsit< x, что говорит о необходимости вставки x между a и a[j].

· capătul din stânga părții ordonate a matricei a fost atins, prin urmare, trebuie să inserăm x în primul rând.

Până când una dintre aceste condiții este îndeplinită, vom muta elementele care sunt vizualizate în prima poziție la dreapta, drept urmare spațiul sub x va fi eliberat în partea sortată.

Program de sortare directă:

programul n3; (Sortați în ordine descrescătoare)

tip ar=matrice de întreg;

procedura sorting3(var a:ar);

var i,j,x,k:intger;

pentru k:=2 la n face

x:=a[k]; j:=k-1;

în timp ce (j>0) și (x>=a[j]) fac

writeln("Introduceți matricea sursă:");

pentru i:=1 la n do read(a[i]);

writeln("Matrice sortată:");

pentru i:=1 la n scrieți(a[i]," ");

Scopul lucrării Investigați sortarea matricei folosind metoda includerii directe și evaluați eficacitatea acestui algoritm.

Informații generale

Sortarea prin includere directă, ca sortarea prin selecție simplă, este de obicei folosită pentru tablourile care nu conțin elemente duplicate. Sortarea prin această metodă se realizează secvenţial pas cu pas. La pasul k-a, se consideră că partea din tablou care conține primele k-1 elemente este deja ordonată, adică. Apoi, trebuie să luați elementul k-lea și să alegeți un loc pentru acesta în partea sortată a matricei, astfel încât după inserarea lui, ordonarea să nu fie perturbată, adică trebuie să găsiți astfel încât. Apoi trebuie să inserați elementul a[k] în locația găsită. Cu fiecare pas, partea sortată a matricei crește. Pentru a efectua o sortare completă, va trebui să efectuați n-1 pași. Rămâne să răspundem la întrebarea cum să căutați un loc potrivit pentru elementul x. Să procedăm astfel: vom căuta prin elementele situate în stânga lui x (adică cele care sunt deja ordonate), trecând la începutul matricei. Trebuie să vă uitați prin elementele a[j], j se schimbă de la k-l la 1. O astfel de scanare se va încheia atunci când este îndeplinită una dintre următoarele condiții: este găsit elementul a[j] Exemplu Să descriem pe scurt un fragment al algoritmului de sortare folosind includerea directă: Pentru k:= 2 până la n începe x:= a[k]; j:= k-1; ( inserați x într-un loc potrivit în a, ..., a[k] ) ( pentru aceasta organizăm o buclă care rulează while ) ( j > 0 și x

Sarcina de testare

Scrieți un program pentru a insera ultimul element al unui tablou după primul element negativ al aceleiași matrice.

Opțiuni de sarcină

ATENŢIE!!! Dacă nu este specificat în mod explicit altfel, datele de intrare (matrice originală) și datele de ieșire (matrice sortată) ar trebui să fie generate ca fișier text care conține numere întregi! Pentru toate sarcinile, scrieți mai întâi o procedură pentru sortarea unei matrice folosind metoda includerii directe. 1. Dată o serie care conține n elemente. Sortați-le în ordine crescătoare, eliminând toate elementele duplicat. 2. Determinați modul unei serii date - valoarea care apare cel mai des printre elementele sale. 3. Setul de date inițial este o secvență de înregistrări constând din numele de familie, vârsta și vechimea în muncă. Tipăriți această listă: 1) în ordine alfabetică; 2) în ordinea creșterii vârstei; 3) în ordinea creșterii vechimii în muncă. 4. Scrieți o procedură de sortare în ordine descrescătoare. 5. Având în vedere o serie de numere întregi. Obțineți, în ordine crescătoare, toate numerele diferite incluse în această serie. 6. Având în vedere o serie de n numere întregi diferite. Obțineți numere întregi diferite astfel încât 7. Numerele întregi date Găsiți cea mai mare valoare din această secvență după eliminarea tuturor termenilor cu o valoare din aceasta 8. Dat natural Numerele sunt rezultatele a n sportivi în cursa de 100 m măsurate în sutimi de secundă.Formați o echipă din cei mai buni patru alergători pentru a participa la cursa de ștafetă 4x100, adică indicați unul dintre cele patru numere naturale i, j, k, Sunt astfel încât suma are cea mai mică importanță. 9. Date n puncte aleatoare independente, cu coordonate (xi; yi), distribuite uniform într-un cerc de raza 1 cu un centru la origine. Scrieți un program care aranjează punctele în ordinea creșterii distanței față de centru. 10. Dat n numere întregi pozitive de două cifre. Tratând fiecare număr ca o pereche de cifre din intervalul 0–9, sortați-le (numerele) în ordine crescătoare. 11. Date n puncte din plan. Găsiți o polilinie închisă care nu se intersectează cu legături (n-1) care trece prin toate aceste puncte. (Segmentele adiacente ale poliliniei au voie să se afle pe aceeași linie dreaptă.) Sugestie. Să luăm punctul cel mai din stânga (adică punctul cu cea mai mică coordonată x) și să tragem raze din el către toate celelalte puncte. Acum să ordonăm aceste raze de jos în sus și să ordonăm punctele pe o rază în funcție de distanța de la începutul razei (acest lucru se face pentru toate razele, cu excepția celei de jos și de sus). Polilinia părăsește punctul selectat (cel mai din stânga) de-a lungul razei inferioare, apoi de-a lungul tuturor celorlalte raze (în ordinea descrisă) și revine de-a lungul razei superioare. 12. Date n puncte din plan. Construiți corpul lor convex - figura convexă minimă care le conține. (Un inel de cauciuc întins peste cuiele înfipte într-o placă - învelișul lor convex.) Instrucțiuni. Să aranjam punctele. Apoi, luând în considerare punctele unul câte unul, vom construi carcasa convexă a punctelor deja luate în considerare.

Au fost dezvoltate multe metode pentru sortarea (ordonarea) în ordine crescătoare sau descrescătoare a valorilor într-o matrice [Wirth, Knuth. t 3]. Să considerăm trei dintre ele, considerând, pentru certitudine, că primele n, n=6, elemente ale tabloului X

La fiecare pas următor, i=2, 3,…,n-1, valoarea din celula (i+1) a matricei este mutată spre scăderea indicelui celulei prin schimbul de poziție cu numărul din precedentul celula până la Nu se va dovedi că celula anterioară conține un număr mai mic.

Din cele de mai sus rezultă că la implementarea metodei de includere directă, bucla exterioară trebuie executată de n-1 ori, iar numărul maxim posibil de execuții ale buclei interioare, în corpul căruia trebuie efectuate comparații și rearanjamente ale numerelor, va crește de la 1 la n-1. Cu toate acestea, bucla interioară trebuie organizată astfel încât să se termine sau să nu fie executată deloc atunci când apare condiția: valoarea din celula anterioară a matricei este mai mică decât în ​​cea curentă.

În exemplul nostru:

Când i=2, numărul 15 din celula X 3 schimbă secvențial locuri cu numărul 34 din celula X 2 și apoi cu numărul 21 din celula X 1,

Când i=4, numărul 25 din celula X 5 schimbă locuri cu numărul 34 din celula X 3,

Mai jos este un fragment dintr-un program pentru ordonarea în ordine crescătoare a primelor n elemente ale tabloului X folosind metoda includerii directe (includerea cu menținerea ordinii).

pentru i:=1 la n-1 do

2. în timp ce (X 0) face

3. R:=X[j];

   X[j]:=X;

   X:=R;

Pentru a ordona numerele într-o matrice în ordine descrescătoare, la fiecare pas este suficient să schimbați condiția de permutare a numerelor din celulele învecinate ale matricei la opus, și anume, schimbul de valori ale celulelor învecinate va fi efectuat în cazul în care precedentul este mai mic decât cel actual.

Metoda schimbului direct (metoda cu bule).

Această metodă, ca și cea anterioară, se bazează pe schimbul de valori ale celulelor învecinate ale matricei, dar încă de la primul pas în analiza secvenţială, la trecerea de la un capăt la altul al matricei, toate perechile de sunt implicate celule învecinate ale matricei.

La primul pas, secvenţial, pentru j = n, n-1, ..., 2, se compară valorile celulelor învecinate ale matricei, iar dacă condiţia X j<Х j-1 выполняется их перестановка, в результате чего наименьшее число оказывается в ячейке Х 1 .

În exemplul nostru, după finalizarea primului pas, datele din matrice vor fi localizate astfel:

La fiecare pas următor, numărul de perechi de celule de verificat va scădea cu 1. În general, la orice pas i, i=1, 2, 3, ..., n-1, procesul se va efectua pentru j din n la i+1, în special, pentru i= n-1 – o singură dată pentru celulele n-a și (n-1)-lea.

Din cele de mai sus rezultă că la implementarea metodei de schimb direct, bucla exterioară trebuie executată de n-1 ori, iar numărul de execuții ale buclei interioare, în corpul căreia trebuie efectuate comparații și rearanjamente de numere, va scădea. de la n-1 la 1.

Originea termenului „metoda cu bule” este explicată după cum urmează: dacă vă imaginați aranjamentul vertical al celulelor matrice cu indice crescător de sus în jos, atunci cel mai mic număr dintre cele considerate se va ridica ca un balon în apă.

În exemplul nostru

Când i=3 permutări vor duce la următoarea stare a matricei

Atunci când se utilizează metoda bulelor, nu contează dacă analiza perechilor de numere din matrice se îndreaptă către indici crescători sau descrescători, iar tipul de ordonare (crescător sau descrescător) este determinat doar de condiția permutării numerelor (cel cel mai mic ar trebui să fie situat în spatele celui mai mare sau invers).

Metoda de schimb direct modificată (metoda cu bule modificate).

După cum se poate vedea din exemplul numeric de mai sus, matricea s-a dovedit a fi ordonată după al patrulea pas, adică este posibil să se execute bucla exterioară nu de n-1 ori, dar mai puțin, atunci când se știe că matricea este deja comandat. Această verificare se bazează pe următoarele: dacă nu au existat permutări în timpul execuției buclei interioare, atunci matricea este deja ordonată și puteți ieși din bucla exterioară. O variabilă de tip boolean este utilizată ca semn al faptului că a fost efectuată o permutare: înainte de a intra în bucla interioară, i se dă o valoare, de exemplu, False, iar atunci când permutarea este efectuată, i se dă o altă valoare, de exemplu, Adevărat.

Evident, efectul utilizării metodei cu bule modificate în comparație cu metoda nemodificată în accelerarea procesului de sortare va fi observat dacă succesiunea originală de numere este aproape de a fi ordonată în direcția dorită. În cazul extrem, când matricea este deja ordonată în modul dorit, corpul buclei exterioare va fi executat o singură dată.