Metoda de inserare directă. Metode de sortare matrice. Eficiența algoritmului de includere directă

Sortarea prin includere funcționează pe o listă de numere întregi pozitive neordonate (numite în mod obișnuit chei), sortându-le în ordine crescătoare. Acest lucru se face în același mod în care majoritatea jucătorilor aranjează cărțile care le sunt împărțite, ridicând câte o carte. Să arătăm cum funcționează procedura generală prin exemplul următoarei liste nesortate de opt numere întregi:

27 412 71 81 59 14 273 87.

Lista sortată este recreată; la început este gol. La fiecare iterație, primul număr al listei nesortate este eliminat din ea și plasat în poziția corespunzătoare din lista sortată. Pentru a face acest lucru, lista sortată este scanată, începând cu cel mai mic număr, până când este găsit un loc adecvat pentru noul număr, adică. până când toate numerele sortate cu valori mai mici sunt în fața lui și toate numerele cu valori mari sunt după el. Următoarea secvență de liste arată cum se face acest lucru:

Iterația 0

Sortat 27

Iterația 1 Nesortat 412 71 81 59 14 273 87

Sortat 27.412

Iterația 2 Nesortat 71 81 59 14 273 87

Asortate 27 71 412

Iterația 3 Nesortat 81 59 14 273 87

Asortate 27 71 81 412

Iterația 4 Nesortat 59 14 273 87

Asortate 27 59 71 81 412

Iterația 5 Nesortat 14 273 87

Sortat 14 27 59 71 81 412

Iterația 6 Nesortat 273 87

Sortat 14 27 59 71 81 273 412

Iterația 7 Nesortat 87

Sortat 14 27 59 71 81 87 273 412

În următorul algoritm, este începută o singură listă, iar numerele sunt rearanjate în lista veche.

Algoritmul SIS(Sortați după includere directă). Sortați șirul numerelor întregi I (1), I (2), în locul vechi. ... ... , I (N) în ordine crescătoare.

Pasul 1.[Iterație principală]

Pentru J ← 2 la N face prin pasul 4 od ;și STOP.

Pasul 2.[Selectați următorul întreg] A stabilit K ← I (J); și L ← J − 1.

Pasul 3.[Comparație cu numere întregi sortate] In timp ce K

ȘI L≥1 setați I (L + 1) ← I (L); și L ← L − 1 od.

Pasul 4.[ Se pornește ] A stabilit I (L + 1) ← K.

SORTARE RAPIDA:Algoritm de sortare cu durata medie de rulare O (N ln N)

Motivul principal pentru funcționarea lentă a algoritmului SIS este că, toate comparațiile și schimburile între cheile din secvență a 1, a 2,. ... ... si n apar pentru perechi de elemente adiacente. Această metodă necesită un relativ mare

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Linii 38 08 16 06 79 76 57 24 56 02 58 48 04 70 45 47 Acțiune

1 38 47 scăderea j

5 04 38 schimb

6 08 38 spor i

10 38 79 schimb

14 02 38 schimb

15 76 38 spor i,>

16 38 76 schimb

17 38 56 scădere j

19 24 38 schimb

20 57 38 spor i,>

21 38 57 schimb, scadere

22 04 08 16 06 02 24 38 57 56 76 58 48 79 70 45 47

(1 2 3 4 5 6) 7 (8 9 10 11 12 13 14 15 16)

este timpul să puneți o cheie deplasată în poziția corectă în ordinea de sortat. Este firesc să încercăm să accelerăm acest proces comparând perechi de elemente care sunt departe unul de celălalt în secvență.

K. Hoore a inventat și aplicat foarte eficient această idee (algoritmul QUICKSORT), reducând timpul mediu de rulare al algoritmului SIS de la ordinul lui O (N 2) la ordinul lui O (N ln N). Să explicăm acest algoritm cu următorul exemplu.

Să presupunem că vrem să sortăm o secvență de numere din primul rând din figura 1. 15. Să începem cu presupunerea că primul cheia din această secvență (38) servește ca o bună aproximare a cheii care va apărea în cele din urmă la mijlocul secvenței sortate. Folosim această valoare ca pivot, în raport cu care cheile pot fi schimbate și procedăm după cum urmează. Setăm doi pointeri I și J, dintre care I începe de la stânga (I = 1) și J - de la stânga în succesiune (J = N). Comparând un euși un J... Dacă a I ≤a J, setați J ← J − 1 și faceți următoarea comparație. Noi continuăm reduce J până ajungem a I> a J. Atunci hai să facem schimb a I ↔a J(Fig. 15, linia 5, schimbul cheilor 38 și 04), setați I ← I + 1 și continuați crește Eu până ajungem a I> a J. După următorul schimb (linia 10, 79↔38), scădem din nou J. Alternând între scăderea J și creșterea I, continuăm acest proces de la ambele capete ale secvenței la „mijloc” până când obținem I = J.

Acum sunt două fapte. În primul rând, cheia (38), care a fost inițial în prima poziție, până la acest moment este la locul său corespunzător în secvența sortată. În primul rând, toate tastele din stânga acestui element vor fi mai mici, iar toate tastele din dreapta vor fi mari.

Aceeași procedură poate fi aplicată subsecvențelor din stânga și din dreapta pentru sortarea finală a întregii secvențe. Ultima linie (numerotată 22) din Fig. 15 arată că atunci când I = J este primit, atunci I = 7. După aceea, procedura se aplică din nou la subsecvențele (1,6) și (8,16).

Natura recursivă a algoritmului sugerează că valorile indicilor elementelor cele mai exterioare ale celei mai mari dintre cele două subsecvențe nesortate (8,16) ar trebui să fie împinse pe stivă și apoi să se procedeze la sortarea subsecvenței mai mici (1,6). ).

În linia 4 din Fig. 15, numărul 04 s-a mutat în poziția 2, iar secvențele (1,1) și (3,6) trebuie sortate. Deoarece (1,1) este deja sortat (numărul 02), sortăm (3,6), care, la rândul său, duce la rândul 6, în care (3,4) și (6,6) trebuie sortate. Pe linia 7 se sortează subsecvența (1,6). Acum scoatem (8,16) din stivă și începem să sortăm această subsecvență. Linia 13 conține subsecvențele (8,11) și (13,16) care trebuie sortate. Punem (13,16) pe stivă, sortăm (8,11) etc. Pe linia 20, întreaga secvență este sortată.

Înainte de a descrie formal algoritmul QUICKSORT, trebuie să arăți exact cum funcționează. Folosim stiva [LEFT (K), RIGHT (K)] pentru a stoca indicii elementelor din stânga și din dreapta ale subsecvențelor nesortate. Deoarece subsecvențele scurte sunt sortate mai rapid folosind algoritmul normal, algoritmul QUICKSORT are un parametru de intrare M care determină cât de scurtă trebuie să fie subsecvența pentru a o sorta în mod obișnuit. În acest scop folosim Sortare prin includere simplă (SIS).

Căutare

Acum să ne întoarcem la studiul unora dintre principalele probleme legate de regăsirea informațiilor pe structurile de date. Ca și în secțiunea anterioară despre sortare, vom presupune că toate informațiile sunt stocate în înregistrări care pot fi identificate prin valori cheie, de exemplu. înregistrarea R i corespunde valorii cheii notate cu K i.

Să presupunem că fișierul conține N înregistrări într-un mod aleatoriu sub forma unui tablou liniar. O metodă de căutare evidentă înregistrarea dată va exista o vedere secvenţială a tastelor. Daca este gasit cheia necesară, căutarea se încheie cu succes; în caz contrar, toate cheile vor fi scanate, iar căutarea nu va avea succes.Dacă toate ordonările posibile ale cheilor sunt la fel de probabile, atunci un astfel de algoritm necesită operații de bază O (N) atât în cele mai rele, cât și în cele medii. Timpul de căutare poate fi redus considerabil prin precomandarea fișierului cu taste. Această lucrare preliminară are sens dacă fișierul este suficient de mare și accesat frecvent.

Să presupunem că am mers la mijlocul fișierului și am găsit acolo cheia K i. Să comparăm K și K i. Dacă K = K i, atunci înregistrarea necesară a fost găsită. Dacă K<К i ,то ключ К должен находиться в части файла, предшествующей К i (если запись с ключом К вообще существует) . Аналогично, если К i <К, то дальнейший поиск следует вести в части файла, следующей за К i . Если повторять эту процедуру проверки ключа К i из середины непросмотренной части файла, тогда каждое безуспешное сравнение К с К i будет исключать из рассмотрения приблизительно половину непросмотренной части.

O organigramă a acestei proceduri, cunoscută ca căutare binară, prezentat în Fig. 16

Algoritm BSEARCH (căutare binară) căutați o înregistrare cu cheia K într-un fișier cu N≥2 înregistrări, ale căror chei sunt ordonate în ordine crescătoare K 1<К 2 …<К N .

Pasul 0.[Inițializare] A stabilit PRIMUL ← 1; LAST ← N. (PRIMUL și ULTIMUL sunt indicatori către prima și ultima cheie din partea nevizuită încă a fișierului.)

Pasul 1.[Bucla principală] In timp ce ULTIMUL≥PRIMUL face prin pasul 4 od.

Pasul 2.[Obținerea unei chei centrale] A stabilit I ← | _ (PRIMUL + ULTIMUL) / 2_ | . (K i este o cheie situată în mijlocul sau în stânga mijlocului părții din fișier care nu a fost încă vizualizată.)

Pasul 3.[Verificați finalizarea cu succes] Dacă K = K I atunci PRINT „Finalizare cu succes, cheia este K I”; și STOP fi.

Pasul 4.[Comparaţie] Dacă K < K I apoi setați ULTIMA ← I-1 alt set PRIMUL ← I + 1 fi.

Pasul 5.[Căutare nereușită] PRINT „nereușită”; și STOP.

Algoritmul BSEARCH este utilizat pentru a găsi K = 42 în Figura 17.

Căutarea binară poate fi folosită și pentru a reprezenta un fișier ordonat ca un arbore binar. Valoarea cheie găsită în prima execuție a pasului 2 (K (8) = 53) este rădăcina arborelui. Intervalele de taste din stânga (1,7) și din dreapta (9,16) ale acestei valori sunt împinse pe stivă. Coșul de sus este scos din stivă și pasul 2 găsește elementul din mijloc (sau elementul din stânga mijlocului). Această cheie (K (4) = 33) devine următorul element după rădăcină la stânga dacă valoarea sa este mai mică decât valoarea rădăcinii, iar următorul din dreapta în caz contrar. Subintervalele acestui interval la dreapta și la stânga tastei nou adăugate [(1,3), (5,7)] sunt acum împinse pe stivă.Această procedură se repetă până când stiva este goală. Figura 18 prezintă un arbore binar care ar fi construit pentru cele 16 chei ordonate din Figura 17.

Căutarea binară poate fi acum interpretată ca traversând acest arbore de la rădăcină la înregistrarea dorită. Dacă vârful final este atins și cheia specificată nu este găsită, intrarea necesară din acest fișier lipsește. Rețineți că numărul de vârfuri pe o singură cale de la rădăcină la o anumită cheie K este egal cu numărul de comparații efectuate de algoritmul BSEARCH atunci când încercați să găsiți K.

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

Sortarea după această metodă se realizează pas cu pas secvenţial. Pe k-Această etapă se consideră că partea din matricea care îl conține pe primul k– 1 articol este deja comandat, adică.

În continuare, trebuie să luați k–Elementul și găsiți un loc pentru acesta în partea sortată a matricei, astfel încât după inserarea lui ordonarea să nu fie întreruptă, adică este necesar să găsiți astfel încât. Apoi trebuie să introduceți elementul a (k) la locul găsit.

Cu fiecare pas, partea sortată a matricei crește. Pentru a efectua o sortare completă, trebuie să faceți n– Pasul 1.

Rămâne să răspundem la întrebarea cum să găsiți un loc potrivit pentru un element X... Vom proceda astfel: vom vizualiza elementele situate în stânga X(adică cele care sunt deja comandate), trecând la începutul matricei. Trebuie să vizualizați articolele a (j), j variază de la k– de la l la 1. Această scanare se va încheia dacă este îndeplinită una dintre următoarele condiții:

S-a găsit un element care indică necesitatea introducerii X intre si a (j).

S-a ajuns la capătul stâng al părții comandate a matricei, prin urmare, trebuie să introduceți X pe primul loc.

Până când una dintre aceste condiții este îndeplinită, vom deplasa elementele vizualizate cu 1 poziție la dreapta, drept urmare spațiul din partea sortată va fi eliberat pentru X.

Tehnica de sortare este ilustrată în Tabelul 2:

Tabelul 2 - Exemplu de sortare prin includere directă

Secvența ordonată inițial constă din primul element 9. Element A( 2) = 5 este primul din secvența neordonată și 5< 9, поэтому ставится на его место, а 9 сдвигается вправо. Теперь упорядоченная последовательность состоит из двух элементов 5, 9. Элемент A( 3) = 15 din secvența neordonată este mai mare decât toate elementele șirului ordonat, prin urmare șirul ordonat rămâne în locul său și la pasul următor secvența ordonată este formată din 5, 9, 15, iar elementul luat în considerare este 6. procesul continuă până când secvența devine ordonată.

Sortare agitatoare

Există trei îmbunătățiri simple ale metodei cu bule. În primul rând, dacă la un anumit pas nu a fost efectuat un singur schimb, atunci execuția algoritmului poate fi încheiată. În al doilea rând, vă puteți aminti cea mai mică valoare a indexului matricei pentru care au fost efectuate permutările la pasul curent. Evident, partea de sus a matricei până la elementul cu acest index este deja sortată, iar la pasul următor, puteți opri compararea valorilor elementelor învecinate când este atinsă această valoare a indexului. În al treilea rând, metoda cu bule funcționează inegal pentru valorile „ușoare” și „grele”. Valoarea luminii ajunge la locul potrivit într-un singur pas, iar valoarea grea scade cu o poziție spre locul potrivit la fiecare pas.

Metoda ShakerSort se bazează pe aceste observații. Când îl aplicați, la fiecare pas următor, direcția de vizualizare secvențială se schimbă. Ca urmare, la un pas, următorul element cel mai ușor „apare”, iar în celălalt, următorul element cel mai greu „se scufundă”. Un exemplu de sortare a agitatorului este prezentat în Tabelul 3.

Tabelul 3 - Exemplu de sortare a agitatorului

Sortarea unei matrice folosind incluziuni cu distanțe descrescătoare (metoda Shell)

D. Schell a propus o îmbunătățire a sortării folosind includerea directă.

Ideea metodei: toate elementele matricei sunt împărțite în grupuri, astfel încât fiecare grup să includă elemente distanțate unele de altele de un anumit număr de poziții L... Elementele fiecărui grup sunt sortate. După aceea, toate elementele sunt re-combinate și sortate în grupuri, în timp ce distanța dintre elemente scade. Procesul se încheie după ce se realizează ordonarea elementelor cu distanța dintre ele egală cu 1.

Un exemplu de sortare Shell este prezentat în Tabelul 4.

Tabelul 4 - Exemplu de sortare Shell

În primul rând, luați în considerare opțiunea când valoarea inițială L este egal cu jumătate din numărul de elemente din matrice, iar fiecare valoare ulterioară este jumătate din cea anterioară. Rețineți că sunt schimbate elemente care sunt distanțate. Dacă, la compararea a 2 elemente, schimbul nu a avut loc, atunci locurile elementelor comparate sunt deplasate la dreapta cu o poziție. Dacă schimbul a avut loc, atunci elementele comparate corespunzătoare sunt deplasate cu L.

Sortare divizată (sortare rapidă)

Metoda de sortare split a fost propusă de Charles Hoare. Această metodă este o dezvoltare a metodei de schimb simplu și este atât de eficientă încât a devenit cunoscută ca metoda „Quicksort”.

Ideea principală a algoritmului este că un anumit element al matricei este selectat aleatoriu X, după care matricea este scanată din stânga până când este întâlnit un element a (i) astfel încât a (i) > Xși apoi matricea este scanată din dreapta până când este întâlnit elementul a (i) astfel încât a (i)< X... Aceste două elemente sunt schimbate și procesul de vizualizare, comparare și schimb continuă până când ajungem la element X... Ca rezultat, matricea va fi împărțită în două părți - cea din stânga, în care valorile cheilor vor fi mai mici X, și cea potrivită cu valori cheie mai mari decât X... Procesul continuă apoi recursiv pentru părțile din stânga și din dreapta ale matricei până când fiecare parte conține exact un element. Recursiunea poate fi înlocuită cu iterații dacă vă amintiți indicii matricei corespunzători.

Procesul de sortare a unei matrice prin metoda rapidă este prezentat în Tabelul 5.

Tabelul 5 - Exemplu de sortare rapidă

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

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

a ≤ a ≤ ... ≤ a.

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

Cu fiecare pas, partea sortată a matricei crește. Sortarea completă necesită 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 prin metoda includerii directe

1 - pasul

13 6 8 11 3 1 5 9 15 7 Se consideră o parte dintr-un tablou de un element

ment (13). Trebuie să introduceți o secundă în el

un element al matricei (6) astfel încât ordonat

caracterul a fost 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 la primul

6 - Etapa

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

Partea de copil 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 Stabiliți locul penultimului

Elementul 15. Rezultă că acest element

polițistul de matrice este deja pe loc.

9 -Etapa

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

Ultimul articol (7).

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

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

Pentru k: = 2 To n Do

(deoarece începem să sortăm prin găsirea unui loc potrivit pentru a, i se schimbă 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. Este necesar să se vizualizeze elementele a [j], j variază de la k-1 la 1. O astfel de scanare trebuie să se termine atunci când este îndeplinită una dintre următoarele condiții:

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

· S-a ajuns la capătul din stânga părții ordonate a matricei, prin urmare, trebuie să inserați x în primul rând.

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

Program de sortare directă:

programul n3; (Sortează descrescător)

tip ar = matrice de întreg;

procedura sorting3 (var a: ar);

var i, j, x, k: întreg;

pentru k: = 2 la n do

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

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

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

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

writeln ("Matrice sortată:");

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

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 cu i = 2), i-lea element este extras din partea nesortată și plasat în piesa „finisată”, în timp ce este introdus în locul dorit.

Algoritmul text al metodei:

1. Început.

2. Buclă în timp ce 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-lea) și astfel stând în secvența „gata”;

c) dacă А (0) ≥ А (j), atunci elementul А (0) ar trebui plasat în celula А (j + 1), în caz contrar elementul А (j) ar trebui plasat în celula А (j + 1) , reduceți valoarea lui j cu unu și executați din nou elementul c).

În fig. 1 prezintă o diagramă bloc de sortare prin metoda includerii directe.

Metoda funcționează astfel: la pasul i (începând de la i = 2), elementul i este plasat într-o celulă liberă (de exemplu, A (0)). Acest element este comparat cu elementul din stânga acestuia în partea „finisată”. 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) se dovedește a fi nu mai mic decât comparația, atunci este plasat în locul imediat după elementul comparat.

Orez. 1. Schema bloc de sortare prin metoda includerii directe

În fig. 2 prezintă un exemplu de realizare a sortării prin 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. Un exemplu de sortare prin metoda includerii directe

Sortarea directă prin includere este mai potrivită pentru cazul în care datele de sortat vin secvenţial (una după alta).

Sortare după metoda de selecție directă

Esența metodei este următoarea. Cel mai mic element din partea „rămasă” (nesortată) este selectat și schimbat cu primul articol (din aceeași parte nesortată). După aceea, lungimea piesei nesortate se reduce cu un element (de 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 (minim), toate elementele piesei nesortate sunt scanate, iar acest element minim este plasat ca un alt element în partea deja „gata”.

Algoritmul text al metodei:

1. Început.

2. Buclă în timp ce i are valori de la 1 la N - 1,
pas = 1:

a) puneț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 următorul element după i) până la N, pas = +1:

corpul ciclului: dacă X> A (j), atunci punem elementul A (j) în celula X și ne amintim numărul său în celula K;

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

În fig. 3 prezintă un exemplu de realizare a sortării prin metoda selecției directe.

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 metoda selectiei directe