Neposredno razvrščanje. Algoritmi in podatkovne strukture Funkcija preproste inkluzijske metode c

Ta metoda se pogosto uporablja pri igranju kart. Elementi (karte) so mentalno razdeljeni na že "pripravljeno" zaporedje A1 ... An in izvirno zaporedje Ai ... An. Pri vsakem koraku, začenši od i=2 in povečanju I vsakič za eno, se i-ti element izloči iz prvotnega zaporedja in prenese v končano zaporedje ter se vstavi na pravo mesto.

Zgoraj je kot primer prikazan postopek razvrščanja z vključitvijo osmih naključno izbranih števil: Algoritem za to razvrščanje je naslednji:

ZA i:=2 DO n NAREDI

vključitev x na ustrezno mesto med a ... a[j];

V resničnem procesu iskanja primernega mesta je priročno z izmeničnimi primerjavami in premikanjem po zaporedju tako rekoč presejati X, tj. X primerjati z naslednjim elementom aj, nato pa bodisi X vstaviti v prazno presledek, ali pa se aj premakne (prenese) v desno, proces pa »gre« v levo. Upoštevajte, da se lahko postopek sejanja konča, če je izpolnjen eden od naslednjih dveh različnih pogojev:

1. Najden je element aj s ključem, ki je manjši od ključa X.

2. Dosežen je levi konec končanega zaporedja.

Ta tipičen primer ponavljajočega se procesa z dvema zaključnima pogojema nam omogoča uporabo dobro znane pregradne tehnike (sentinel). Tu ga je mogoče enostavno uporabiti z nastavitvijo pregrade a0 z vrednostjo X. (Upoštevajte, da je za to potrebno razširiti obseg indeksa v opisu spremenljivke a na 0 ... n.)

Analiza metode neposredne vključitve. Število ključnih primerjav (Ci) med i-tim presejanjem je največ enako i - 1, najmanj 1; Če predpostavimo, da so vse permutacije n ključev enako verjetne, potem je povprečno število primerjav i/2. Število prenosov (dodelitev elementov) Mi je enako Ci + 2 (vključno s pregrado). Zato je skupno število primerjav in število prenosov sledeče:

Shrani = (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.

Najmanjše ocene nastanejo v primeru že urejenega začetnega zaporedja elementov, najslabše ocene pa nastanejo, ko so na začetku urejeni v obratnem vrstnem redu. Na nek način ima inkluzivna sorta resnično naravno vedenje. Jasno je, da zgornji algoritem opisuje postopek stabilnega razvrščanja: vrstni red elementov z enakimi ključi ostane nespremenjen.

Algoritem z neposrednimi vključitvami je mogoče enostavno izboljšati, če ste pozorni na dejstvo, da je končano zaporedje (a1 ... ai-1, v katerega morate vstaviti nov element, samo po sebi že urejeno. Naravno je, da se osredotočite na binarno iskanje, pri katerem se poskuša primerjati s sredino končanega zaporedja, nato pa se postopek razpolovitve nadaljuje, dokler ni najdena točka vstavljanja. Ta spremenjen algoritem razvrščanja se imenuje metoda binarnega vstavljanja.

Ta metoda se pogosto uporablja pri igranju kart. Elemente (karte) mentalno razdelimo na že »pripravljeno« zaporedje A 1 , A 2 ,…, A i -1 in »preostali« (nerazvrščeni) del: A i , A i +1 ,…, A N .

Bistvo metode je, da se na vsakem i-tem koraku (začenši z i = 2) i-ti element odstrani iz nerazvrščenega dela in postavi v "pripravljen" del ter se vstavi na pravo mesto.

Besedilni algoritem metode:

1. Začetek.

2. Zankajte, dokler i nima vrednosti od 2 do N,
korak = 1:

a) postavite i-ti element (A(i)) v celico A(0);

b) dodelite j = -1, to je, da je j enak številki elementa, ki se nahaja levo od subjekta (i-th) in tako stoji v "pripravljenem" zaporedju;

c) če je A(0) ≥ A(j), potem element A(0) postavite v celico A(j+1), drugače postavite element A(j) v celico A(j+1), zmanjšajte vrednost od j za eno in znova izvedite korak c.

Na sl. Slika 1 prikazuje blokovni diagram razvrščanja z metodo neposredne vključitve.

Metoda deluje na naslednji način: v i-tem koraku (začenši z i = 2) se i-ti element postavi v prosto celico (na primer A(0)). Ta element se primerja z elementom, ki stoji v "končanem" delu levo od njega. Če je element A(0) manjši, se primerjani (j-ti element) premakne v desno za en položaj, po katerem se za primerjavo vzame naslednji element. Če element A(0) pri primerjavi ni manjši, se postavi na mesto takoj za primerjanim elementom.

riž. 1. Diagram poteka razvrščanja z metodo neposredne vključitve

Na sl. Slika 2 prikazuje primer izvajanja sortiranja z metodo neposredne vključitve.

Izvirno zaporedje
	A (0)
jaz = 2
jaz = 3
jaz = 4
jaz = 5
jaz = 6
jaz = 7
jaz = 8
Rezultat

riž. 2. Primer razvrščanja z neposrednim vključevanjem

Neposredno razvrščanje je primernejše za primer, ko razvrščeni podatki prihajajo zaporedno (drug za drugim).

Razvrščanje z neposrednim izborom

Bistvo metode je naslednje. Najmanjši element v "preostalem" (nesortiranem) delu je izbran in zamenjan s prvim elementom (v istem nesortiranem delu). Nato se dolžina nerazvrščenega dela zmanjša za en element (prvi), celoten proces pa se nadaljuje z (n – 1) elementi, nato z (n – 2) elementi itd., dokler ne ostane samo en levo največji element.

Ta metoda je na nek način nasprotna metodi neposredne vključitve. Pri metodi neposrednega vključevanja se na vsakem koraku upošteva samo en naslednji element in vsi elementi že »pripravljenega« dela zaporedja, med katerimi se najde točka vključevanja tega naslednjega elementa. In pri metodi neposredne izbire, da bi našli en (minimalni) element, se pregledajo vsi elementi nerazvrščenega dela in ta minimalni element se postavi kot drug element v že "pripravljen" del.

Besedilni algoritem metode:

1. Začetek.

2. Zanka, dokler i nima vrednosti od 1 do N – 1,
korak = 1:

a) postavi trenutni (i-ti) element v neko pomnilniško celico (X) in si zapomni zaporedno številko (i) trenutnega elementa (v spremenljivki K);

b) izvedite zanko, medtem ko ima j vrednosti od i + 1 (to je od elementa poleg i) do N, korak = +1:

telo zanke: če je X > A(j), potem element A(j) postavi v celico X in si zapomni njegovo številko v celici K;

c) priredite A(K) = A(i) in A(i) = X.

Na sl. Na sliki 3 je prikazan primer izvajanja razvrščanja z metodo neposrednega izbora.

Izvirno zaporedje	44						06
jaz = 1		55	12
jaz = 2			55			18
jaz = 3				42		55
jaz = 4					94		44
jaz = 5						55	94
jaz = 6							94	67
jaz = 7

riž. 3. Primer razvrščanja z neposrednim izborom

Razvrščanje z neposredno vključitvijo, tako kot preprosto razvrščanje z izbiro, se običajno uporablja za nize, ki ne vsebujejo podvojenih elementov.

Razvrščanje po metodi neposredne vključitve, tako kot vse zgoraj opisane, poteka v korakih. Pri k-tem koraku velja, da je del niza, ki vsebuje prvih k-1 elementov, že urejen, tj.

a ≤ a ≤ ... ≤ a .

Nato morate vzeti k-ti element in zanj izbrati mesto v razvrščenem delu matrike, tako da po njegovi vstavitvi vrstni red ni porušen, to je, da morate najti j (1 ≤ j ≤ k -1) tako da je a [j] ≤ a[ k]< a. Затем вставить элемент а [k] на найденное место.

Z vsakim korakom se razvrščeni del matrike poveča. Če želite izvesti popolno razvrščanje, boste morali izvesti n-1 korak.

Oglejmo si ta postopek na primeru. Recimo, da želite razvrstiti matriko 10 elementov v naraščajočem vrstnem redu z metodo neposredne vključitve

1 - th korak

13 6 8 11 3 1 5 9 15 7 Del matrike obravnavamo iz enega elementa

ment (13). Vanj morate vstaviti drugo

element niza (6), tako da je urejen

nost se je ohranila. Od 6< 13, вставляем

6 do prvega mesta. Urejen del

matrika vsebuje dva elementa (6 13).

3 - th korak

6 8 13 11 3 1 5 9 15 7 Naslednji element je 11. Zapisan je v urejeni del matrike na tretjem mestu, saj je 11 > 8, vendar 11< 13.

5- korak

3 6 8 11 13 1 5 9 15 7 Iz istega razloga pišemo 1 kot prvo

6 - korak

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

Končani del je tretji.

7 -korak

1 3 5 6 8 11 13 9 15 7 Število 9 je na šestem mestu.

8 -korak

1 3 5 6 8 9 11 13 15 7 Določitev mesta za predzadnjega

Element 15. Izkazalo se je, da ta element

Niz je že nameščen.

9 -korak

1 3 5 6 8 9 11 13 15 7 Ostane le še najti primeren prostor za

Zadnji element (7).

1 3 5 6 7 8 9 11 13 15 Matrika je popolnoma razvrščena.

Zdaj lahko na kratko opišemo del algoritma za razvrščanje z metodo neposredne vključitve:

Za k: = 2 Za n Naredi

(ker začnemo razvrščati z iskanjem primernega mesta za a, se i spreminja od 2 do n)

'vstavi x na primerno mesto v a, ..., a[k]'

Ostaja še odgovor na vprašanje, kako najti primerno mesto za element x. Nadaljujmo na naslednji način: pogledali bomo elemente, ki se nahajajo levo od x (torej tiste, ki so že urejeni), premaknili se bomo na začetek niza. Pregledati morate elemente a[ j ], j se spreminja od k-1 do 1. Ta pregled se mora končati, ko je izpolnjen eden od naslednjih pogojev:

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

· levi konec urejenega dela matrike je bil dosežen, zato moramo na prvo mesto vstaviti x.

Dokler eden od teh pogojev ni izpolnjen, bomo ogledovane elemente premikali na prvo pozicijo desno, zaradi česar se bo v razvrščenem delu sprostil prostor pod x.

Program neposrednega sortiranja:

program n3; (Razvrsti v padajočem vrstnem redu)

tip ar=matrika celih števil;

postopek razvrščanja3(var a:ar);

var i,j,x,k:celo število;

za k:=2 do n naredi

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

medtem ko (j>0)in(x>=a[j]) naredita

writeln("Vnesite izvorno polje:");

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

writeln("Razvrščena matrika:");

for i:=1 to n do write(a[i]," ");

Cilj dela Raziščite matrično razvrščanje z metodo neposredne vključitve in ocenite učinkovitost tega algoritma.

Splošne informacije

Razvrščanje z neposredno vključitvijo, tako kot preprosto razvrščanje z izbiro, se običajno uporablja za nize, ki ne vsebujejo podvojenih elementov. Razvrščanje po tej metodi se izvaja zaporedno, korak za korakom. Pri k-tem koraku velja, da je del niza, ki vsebuje prvih k-1 elementov, že urejen, tj. Nato morate vzeti k-ti element in zanj izbrati mesto v razvrščenem delu matrike tako, da po njegovi vstavitvi vrstni red ni moten, to pomeni, da morate najti takšno mesto. Nato morate na najdeno mesto vstaviti element a[k]. Z vsakim korakom se razvrščeni del matrike poveča. Če želite izvesti popolno razvrščanje, boste morali izvesti n-1 korak. Ostaja še odgovor na vprašanje, kako najti primerno mesto za element x. Nadaljujmo na naslednji način: pogledali bomo elemente, ki se nahajajo levo od x (torej tiste, ki so že urejeni), premaknili se bomo na začetek niza. Pregledati morate elemente a[j], j se spremeni iz k-l v 1. Takšno skeniranje se konča, ko je izpolnjen eden od naslednjih pogojev: najden je element a[j] Primer Na kratko opišemo del algoritma za razvrščanje z uporabo neposredne vključitve: Za k:= ​​2 do n naredite začetek x:= a[k]; j:= k-1; ( vstavite x na primerno mesto v a, ..., a[k] ) (za to organiziramo zanko, ki teče medtem ) ( j > 0 in x

Preizkusna naloga

Napišite program za vstavljanje zadnjega elementa matrike za prvim negativnim elementom iste matrike.

Možnosti nalog

POZOR!!! Če ni izrecno navedeno drugače, morajo biti vhodni podatki (izvirna matrika) in izhodni podatki (razvrščena matrika) generirani kot besedilna datoteka, ki vsebuje cela števila! Za vsa opravila najprej napišite postopek za razvrščanje matrike z metodo neposredne vključitve. 1. Podana je vrsta, ki vsebuje n elementov. Razvrstite jih v naraščajočem vrstnem redu in zavrzite vse podvojene elemente. 2. Določite način dane serije - vrednost, ki se najpogosteje pojavlja med njenimi elementi. 3. Izvirni niz podatkov je zaporedje zapisov, sestavljenih iz priimka, starosti in delovne dobe. Natisnite ta seznam: 1) po abecednem vrstnem redu; 2) po naraščajoči starosti; 3) po vrstnem redu naraščanja delovne dobe. 4. Napišite postopek za razvrščanje v padajočem vrstnem redu. 5. Podana vrsta celih števil. V naraščajočem vrstnem redu poiščite vsa različna števila v tej seriji. 6. Podana je vrsta n različnih celih števil. Pridobite različna cela števila, tako da 7. Dana cela števila Poiščite največjo vrednost v tem zaporedju, potem ko iz njega izločite vse člene z vrednostjo 8. Dano naravno Številke so rezultati n tekmovalcev v teku na 100 m, merjeni v stotinkah sekunde.Iz štirih najboljših tekmovalcev sestavite ekipo za nastop v štafetnem teku 4x100, torej označite eno od štirih naravnih števil i, j, k, l tako, da je vsota ima najmanjši pomen. 9. Danih je n neodvisnih naključnih točk s koordinatami (xi; yi), enakomerno porazdeljenih v krogu polmera 1 s središčem v izhodišču. Napišite program, ki razporedi točke po naraščajoči oddaljenosti od središča. 10. Danih je n pozitivnih dvomestnih celih števil. Vsako število obravnavajte kot par števk iz intervala 0–9 in jih (števila) razvrstite v naraščajočem vrstnem redu. 11. Danih je n točk na ravnini. Poiščite (n-1)-členovo zaprto poličrto, ki se ne seka sama s seboj, ki poteka skozi vse te točke. (Sosednji segmenti poličrte lahko ležijo na isti ravni črti.) Namig. Vzemimo skrajno levo točko (tj. točko z najmanjšo x-koordinato) in iz nje narišimo žarke do vseh ostalih točk. Zdaj razvrstimo te žarke od spodaj navzgor in razvrstimo točke na enem žarku po razdalji od začetka žarka (to storimo za vse žarke, razen za spodnje in zgornje). Poličrta zapusti izbrano (skrajno levo) točko po spodnjem žarku, nato po vseh ostalih žarkih (v opisanem vrstnem redu) in se vrne po zgornjem žarku. 12. Danih je n točk na ravnini. Konstruirajte njihovo konveksno lupino - minimalno konveksno figuro, ki jih vsebuje. (Gumijasti obroč, napet čez žeblje, zabite v desko – njihovo izbočeno lupino.) Navodilo. Razporedimo točke. Nato bomo z upoštevanjem točk eno za drugo zgradili konveksno lupino že obravnavanih točk.

Razvitih je bilo veliko metod za razvrščanje (razvrščanje) v naraščajočem ali padajočem vrstnem redu vrednosti v matriki [Wirth, Knuth. t 3]. Razmislimo o treh izmed njih, pri čemer za določnost upoštevamo, da je prvih n, n=6, elementov niza X

Pri vsakem naslednjem i-tem koraku, i=2, 3,…,n-1, se vrednost iz (i+1)-te celice matrike premakne proti zmanjševanju indeksa celice z zamenjavo položaja s številko iz prejšnjega celica dokler se ne izkaže, da prejšnja celica vsebuje manjše število.

Iz navedenega sledi, da mora biti pri izvajanju metode neposredne vključitve zunanja zanka izvedena n-1-krat, največje možno število izvedb notranje zanke, v telesu katere je treba izvajati primerjave in preurejanja števil, pa se bo povečalo z 1 na n-1. Vendar mora biti notranja zanka organizirana tako, da se konča ali se sploh ne izvede, ko nastopi pogoj: vrednost v prejšnji celici polja je manjša kot v trenutni.

V našem primeru:

Ko je i=2, številka 15 iz celice X 3 zaporedno zamenja mesta s številko 34 iz celice X 2 in nato s številko 21 iz celice X 1,

Ko je i=4, število 25 iz celice X 5 zamenja mesto s številom 34 iz celice X 3,

Spodaj je delček programa za urejanje v naraščajočem vrstnem redu prvih n elementov matrike X z metodo neposredne vključitve (vključitev ob ohranjanju vrstnega reda).

za i:=1 do n-1 naredi

2. medtem ko (X 0) naredi

3. R:=X[j];

   X[j]:=X;

   X:=R;

Za razporeditev števil v matriki v padajočem vrstnem redu je dovolj, da na vsakem koraku spremenimo pogoj za permutacijo števil v sosednjih celicah matrike v nasprotno, in sicer se zamenjava vrednosti sosednjih celic izvede v primeru, ko je prejšnji manjši od trenutnega.

Metoda neposredne menjave (metoda mehurčkov).

Ta metoda, tako kot prejšnja, temelji na izmenjavi vrednosti sosednjih celic matrike, vendar že od prvega koraka v sekvenčni analizi, ko se premikate z enega konca matrike na drugega, se vsi pari so vključene sosednje celice polja.

V prvem koraku se zaporedno za j = n, n-1, ..., 2 primerjajo vrednosti sosednjih celic matrike in če je izpolnjen pogoj X j<Х j-1 выполняется их перестановка, в результате чего наименьшее число оказывается в ячейке Х 1 .

V našem primeru bodo po zaključku prvega koraka podatki v matriki locirani takole:

Pri vsakem naslednjem koraku se bo število celičnih parov, ki jih je treba preveriti, zmanjšalo za 1. Na splošno bo pri katerem koli koraku i, i=1, 2, 3, ..., n-1, postopek izveden za j od n do i+1, zlasti za i= n-1 – samo enkrat za n-to in (n-1)-to celico.

Iz navedenega sledi, da je treba pri izvajanju metode neposredne izmenjave zunanjo zanko izvesti n-1-krat, zmanjšalo pa se bo število izvedb notranje zanke, v telesu katere je treba izvesti primerjave in preureditve števil. od n-1 do 1.

Izvor izraza "metoda mehurčkov" je razložen na naslednji način: če si predstavljate navpično razporeditev matričnih celic z naraščajočim indeksom od zgoraj navzdol, potem se bo najmanjše število obravnavanih dvignilo kot mehurček v vodi.

V našem primeru

Ko je i=3, bodo permutacije vodile do naslednjega stanja matrike

Pri uporabi metode mehurčkov ni pomembno, ali se analiza parov števil v nizu premika proti naraščajočim ali padajočim indeksom, vrsto razvrščanja (naraščajoče ali padajoče) pa določa le pogoj permutacije števil ( manjši naj bo za večjim ali obratno).

Modificirana metoda neposredne izmenjave (modificirana metoda mehurčkov).

Kot je razvidno iz zgornjega numeričnega primera, se je izkazalo, da je matrika urejena po četrtem koraku, to pomeni, da je mogoče zunanjo zanko izvesti ne n-1-krat, ampak manj, ko postane znano, da je matrika že naročeno. To preverjanje temelji na naslednjem: če med izvajanjem notranje zanke ni bilo permutacij, je matrika že urejena in lahko zapustite zunanjo zanko. Spremenljivka logičnega tipa se uporablja kot znak, ali je bila izvedena permutacija: pred vstopom v notranjo zanko dobi eno vrednost, na primer False, in ko je permutacija izvedena, dobi drugo vrednost, na primer Prav.

Očitno je, da bo učinek uporabe spremenjene metode mehurčkov v primerjavi z nespremenjeno metodo pri pospeševanju postopka razvrščanja opazen, če bo prvotno zaporedje števil skoraj urejeno v želeni smeri. V skrajnem primeru, ko je matrika že urejena na želen način, bo telo zunanje zanke izvedeno le enkrat.