Ezt a módszert széles körben használják kártyázáskor. Az elemek (térképek) mentálisan fel vannak osztva a már „kész” sorozatra A 1 , A 2 ,…, A i -1 , és a „fennmaradó” (nem rendezett) részre: A i , A i +1 ,…, A N .

A módszer lényege, hogy minden i-edik lépésnél (i = 2-től kezdve) az i-edik elemet kivonják a nem rendezett részből és a "kész" részbe helyezik, miközben beillesztik Jó helyen.

Szöveges algoritmus módszer:

1. Indítsa el.

2. Hurok, amíg i értékei 2 és N között vannak,
lépés = 1:

a) az i-edik elem (A(i)) az A(0) cellába kerül;

b) adjunk hozzá j = -1-et, azaz j egyenlő az alanytól balra található (i-edik) elem számával, amely így a „kész” sorozatban áll;

c) ha A(0) ≥ A(j), akkor helyezze az A(0) elemet az A(j+1) cellába, ellenkező esetben helyezze az A(j) elemet az A(j+1) cellába, csökkentse az értéket j-ből egyet, és ismételje meg a c) lépést.

ábrán. Az 1. ábra a rendezési módszer blokkdiagramját mutatja közvetlen kapcsolat.

A módszer a következőképpen működik: az i-edik lépésnél (i = 2-től kezdve) az i-edik elem egy szabad cellába kerül (például A(0)). Ezt az elemet összehasonlítja a tőle balra lévő „kész” részben található elemmel. Ha az A(0) elem kisebb, akkor az összehasonlított (j-edik elem) egy pozícióval jobbra tolódik, majd a következő elemet veszik összehasonlításra. Ha az A(0) elem nem kisebb, mint összehasonlításkor, akkor közvetlenül az összehasonlított elem utáni helyre kerül.

Rizs. 1. A közvetlen befogadás szerinti rendezés blokkdiagramja

ábrán. A 2. ábra a közvetlen befogadás szerinti rendezésre mutat példát.

Forrás sorozat
	A (0)
i = 2
i = 3
i = 4
I=5
i = 6
i = 7
I = 8
Eredmény

Rizs. 2. Példa a közvetlen befogadás szerinti rendezésre

A közvetlen befoglalási rendezés arra az esetre alkalmasabb, ha a rendezendő adatok szekvenciálisan (egymás után) érkeznek.

Közvetlen kiválasztás rendezés

A módszer lényege a következő. A "fennmaradó" (nem rendezett) rész legkisebb elemét kiválasztja és felcseréli az első elemmel (ugyanabban a rendezetlen részben). Ezt követően a rendezetlen rész hosszát egy elemmel csökkentjük (az elsővel), és az egész folyamat folytatódik (n - 1) elemmel, majd (n - 2) elemmel stb., amíg egy marad, a legnagyobb elem.

Ez a módszer bizonyos értelemben ellentéte a közvetlen befogadás módszerének. A közvetlen beillesztési módszerben minden lépésben csak egy következő elemet és a sorozat már „kész” részének összes elemét veszik figyelembe, amelyek között megtaláljuk ennek a következő elemnek a beillesztési pontját. A közvetlen kiválasztási módszernél pedig egy (minimális) elem megtalálásához a rendezetlen rész összes elemét átnézik, és ez a minimális elem kerül a következő elemként a már „kész” részbe.

Szöveges algoritmus módszer:

1. Indítsa el.

2. Hurok, miközben i értékei 1 és N - 1 között vannak,
lépés = 1:

a) tedd az aktuális (i-edik) elemet valamelyik memóriacellába (X) és emlékezz sorozatszám(i) az aktuális elem (a K változóban);

b) hurok, míg j értékei i + 1-től (vagyis az i-t követő elemtől N-ig), lépés = +1:

huroktest: ha X > A(j), akkor helyezzük az A(j) elemet az X cellába, és jegyezzük meg a számát a K cellában;

c) A(K) = A(i) és A(i) = X hozzárendelése.

ábrán. A 3. ábra a közvetlen kijelölés szerinti rendezésre mutat példát.

Rizs. 3. Példa a közvetlen kiválasztással történő rendezésre

Ezt a módszert széles körben használják kártyázáskor. Az elemek (térképek) mentálisan fel vannak osztva a már „kész” A1 … An sorozatra és az eredeti Ai … An sorozatra. Minden lépésben i=2-től kezdve és I-t minden alkalommal eggyel növelve kivonjuk az eredeti sorozatból i-edik elemés eltolva a kész sorozatra, miközben a megfelelő helyre kerül.

A fenti példaként bemutatja a rendezés folyamatát nyolc véletlenszerűen kiválasztott szám felvételével: Ennek a rendezésnek az algoritmusa a következő:

FOR i:=2 TO n DO

x beillesztése a megfelelő helyre a ... a[j] közé;

A megfelelő hely megtalálásának valós folyamatában kényelmes, az összehasonlítások és a mozgások egymás utáni váltakozása során az X-et szitáljuk, azaz X-et összehasonlítjuk a következő aj elemmel, majd vagy X-et illesztünk be. szabad hely, vagy az aj jobbra tolódik (átkerül), és a folyamat balra "elmegy". Vegye figyelembe, hogy a szitálási folyamat véget érhet, ha a következő két különböző feltétel egyike teljesül:

1. Olyan aj elemet találunk, amelynek kulcsa kisebb, mint X kulcsa.

2. Elérte a kész sorozat bal végét.

Ez a tipikus eset, amikor egy ismétlődő folyamat két befejezési feltétellel történik, lehetővé teszi számunkra a jól ismert barrier trükk (sentinel) alkalmazását. Itt egyszerűen alkalmazható az a0 gát X értékű beállításával. (Megjegyzendő, hogy ehhez az a változó leírásában az index tartományát 0 ... n-re kell bővíteni.)

A közvetlen befogadás módszerének elemzése. A kulcsösszehasonlítások száma (Ci) az i-edik szitálásban legfeljebb i - 1, legalább - 1; ha feltételezzük, hogy n kulcs minden permutációja egyformán valószínű, akkor az összehasonlítások átlagos száma i/2. Az átvitelek (elem-hozzárendelések) száma Mi egyenlő Ci + 2-vel (beleértve a sorompót is). Ezért teljes szám az összehasonlítások és az átutalások száma a következő:

Mentés = (n2 + n - 2)/4,

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

M min \u003d Z * (n - 1),

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

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

A minimális becslések már rendezett kezdeti elemek sorozata esetén fordulnak elő, míg a legrosszabb becslések akkor, ha kezdetben fordított sorrendben vannak elrendezve. Bizonyos értelemben a zárványok szerinti válogatás valóban természetes viselkedést mutat. Jól látható, hogy a fenti algoritmus a stabil rendezési folyamatot írja le: az egyenlő kulcsú elemek sorrendje változatlan marad.

A közvetlen zárványokkal rendelkező algoritmus könnyen javítható, ha odafigyelünk arra, hogy az elkészült sorozat (a1 ... ai-1 , amelybe be akarunk szúrni új elem, maga már megrendelt. Természetes, hogy megállunk a bináris keresésnél, amelyben a kész sorozat közepével próbálnak összehasonlítani, majd a felezés folyamata addig tart, amíg meg nem találjuk a befogadási pontot. Az ilyen módosított rendezési algoritmust bináris beillesztési módszernek nevezzük.

A rendezés a memóriában lévő adatok szabályos elrendezése a kiválasztott paraméter szerint. A szabályszerűséget a paraméterérték növekedésének (csökkenésének) tekintjük az adattömb elejétől a végéig.

Az adatok feldolgozása során fontos ismerni az adatok információs mezőjét és a gépben való elhelyezését.

Különbséget kell tenni a belső és a külső rendezés között:

Belső rendezés – rendezés véletlen hozzáférésű memória;

Külső rendezés - rendezés külső memóriában.

Ha a rendezendő iratok nagy mennyiségű memóriát foglalnak el, az áthelyezésük költséges. Csökkentésük érdekében válogatás történik kulcscímtáblázat, vagyis elvégzik a mutatók permutációját, és maga a tömb nem mozdul. Ez- címtábla rendezési módszer.

Rendezéskor ugyanazok a kulcsok fordulhatnak elő. Ebben az esetben kívánatos a rendezés után ugyanazokat a kulcsokat a forrásfájlban megadott sorrendbe rendezni.Ez- stabil fajta.

Csak azokat a fajtákat vesszük figyelembe, amelyek nem használnak további RAM-ot. Az ilyen fajtákat ún "ugyanazon a helyen".

A válogatás hatékonyságát több szempont szerint is figyelembe lehet venni:

A válogatásra fordított idő;

A rendezéshez szükséges RAM mennyisége;

A programozó által a programírással töltött idő.

Az első kritériumot emeljük ki. A válogatásra fordított idő megfelelője tekinthető összehasonlítások számaés mozgások száma válogatáskor.

A rendezés során az összehasonlítások és mozgások számának sorrendje belül van

O-tól (n log n) O-ig (n 2);

O(n) ideális és elérhetetlen eset.

A következő válogatási módszerek vannak:

Szigorú (közvetlen) módszerek;

Továbbfejlesztett módszerek.

Szigorú módszerek:

Közvetlen csatlakozási mód;

Közvetlen kiválasztási módszer;

közvetlen cseremódszer.

A szigorú módszerek hatékonysága kb.

Közvetlen befogadás rendezése

Az elemek gondolatilag kész sorozatra vannak osztva: 1,...,a i-1 és az eredeti sorozatra.

Minden lépésnél, i = 2-től kezdve, és i-t minden alkalommal eggyel növelve, az i-edik elemet kiemeljük az eredeti sorozatból, és átkerül a kész sorozatba, miközben beillesztjük a megfelelő helyre.

Az algoritmus lényege a következő:

i = 2 és n között

X = a(i)

Találunk egy helyet az (1) ... a (i) között, ahol x szerepel

következő i

Két közvetlen befogadási rendezési algoritmus létezik. Először is - nincs akadály

Akadálymentes Közvetlen Befoglalás-rendezési Algoritmus

i = 2 és n között

X = a(i)

j = i-1 esetén 1-ig

Ha x< a(j)

Ekkor a(j + 1) = a(j)

Különben menj L-hez

endif

Következő j

L: a(j + 1) = x

következő i

Visszatérés

A fenti algoritmus hátránya a technológia megsértése strukturált programozás, amelynél nem kívánatos a feltétel nélküli ugrások alkalmazása. Ha a belső hurok while hurokként van megszervezve, akkor szükség van egy „korlátra”, amely nélkül a kulcsok negatív értékeinél jelentőségvesztés és a számítógép „lefagyása” következik be.

Barrier Direct Inclusion Sorting Algorithm

i = 2 és n között

X = a(i)

A(0) = x (a(0) – akadály)

J = i-1

Míg x< a(j) do

A(j+1) = a(j)

J = j-1

Vége

A(j+1) = x

következő i

Visszatérés

A közvetlen befogadás algoritmusának hatékonysága

A kulcsösszehasonlítások Ci száma az i-edik szűrésnél legfeljebb i-1, legalább -1; ha feltételezzük, hogy N kulcs minden permutációja egyformán valószínű, akkor az összehasonlítások átlagos száma = i/2. Az átszállások száma Mi=Ci+3 (a sorompót is beleértve). A minimális becslések már rendezett kezdeti elemek sorozata esetén fordulnak elő, míg a legrosszabb becslések akkor, ha kezdetben fordított sorrendben vannak elrendezve. Bizonyos értelemben a befogadás szerinti válogatás valóban természetes viselkedést mutat. Jól látható, hogy a fenti algoritmus a stabil rendezési folyamatot írja le: az egyenlő kulcsú elemek sorrendje változatlan marad.

Az összehasonlítások száma a legrosszabb esetben, ha a tömb ellentétes módon van rendezve, C max = n (n - 1) / 2, azaz - O (n 2). A permutációk száma M max = C max + 3(n-1), azaz. - O (n 2). Ha a tömb már rendezve van, akkor az összehasonlítások és permutációk száma minimális: C min = n-1; Mmin = 3(n-1).

Rendezés közvetlen csere szerint (buborékos rendezés)

NÁL NÉL ez a szekció olyan módszert írunk le, ahol két elem helycseréje a folyamat legjellemzőbb jellemzője. Az alábbiakban felvázolt közvetlen csere algoritmus egy pár helyének összehasonlításán és megváltoztatásán alapul szomszédos elemekés ezt a folyamatot addig folytatva, amíg az összes elemet el nem rendezik.

Iterálunk a tömbön, minden alkalommal eltolva a maradék sorozat legkisebb elemét a tömb bal végére. Ha a tömböket inkább függőlegesnek, mint vízszintesnek tekintjük, akkor az elemek egy víztartályban lévő buborékokként értelmezhetők, amelyek súlya a kulcsának felel meg. Ebben az esetben minden lépésnél egy buborék mintegy a súlyának megfelelő szintre emelkedik (lásd az alábbi ábrán látható ábrát).

C min = n - 1, O(n) sorrend,

és egyáltalán nincs mozgás.

A közvetlen válogatási módszerek összehasonlító elemzése azt mutatja, hogy a csere "válogatás" klasszikus formájában a zárványok és a szelekciók segítségével történő válogatás keresztezése. Ha a fenti fejlesztéseket végrehajtják rajta, akkor kellően rendezett tömböknél buborék fajta sőt előnye is van.

Ezt a módszert "buborékos rendezésnek" nevezik.

Közvetlen cseremódszer-algoritmus

j = n-re -1 lépés

ha a(j)< a(j - 1) then

A mi esetünkben egy passzot kaptunk „tétlen”. Annak érdekében, hogy az elemeket ne láthassa újra, és ezért összehasonlításokat végezhessen, időt szánva erre, beírhatja a jelölőnégyzetet fl, ami az értékben marad hamis, ha a következő menet során nem történik csere. Az alábbi algoritmusban a kiegészítések félkövérrel vannak jelölve.

fl = igaz

ha fl = false, akkor térjen vissza

fl=hamis

j = n-re -1 lépés

ha a(j)< a(j - 1) then

fl = igaz

A buborékos rendezés továbbfejlesztése a rázós rendezés, ahol minden egyes lépés után az irány megfordul egy belső hurokban.

A közvetlen csererendezési algoritmus hatékonysága

Összehasonlítások száma C max = n(n-1)/2, O(n 2) sorrend.

A mozgások száma M max \u003d 3C max \u003d 3n (n-1) / 2, O (n 2) sorrendben.

Ha a tömb már rendezve van és a zászlóalgoritmus alkalmazva van, akkor csak egy lépés elég, és akkor megkapjuk a minimális számú összehasonlítást

A közvetlen befoglalási rendezést, az egyszerű kiválasztási rendezéshez hasonlóan, általában olyan tömbökhöz használják, amelyek nem tartalmaznak ismétlődő elemeket.

A közvetlen beillesztés módszerével történő rendezés, mint az összes fent leírt, lépésenként történik. A k-edik lépésben azt tekintjük, hogy a tömb első k-1 elemét tartalmazó része már rendezett, azaz

a ≤ a ≤ ... ≤ a .

Ezután vegyük a k-edik elemet, és találjunk neki egy helyet a tömb rendezett részében, hogy a beillesztése után ne sérüljön meg a sorrend, azaz meg kell találni egy ilyen j-t (1 ≤ j ≤ k -1) hogy a [j] ≤ a[ k]< a. Затем вставить элемент а [k] на найденное место.

Minden lépéssel növekszik a tömb rendezett része. A teljes rendezés végrehajtásához n-1 lépés szükséges.

Nézzük meg ezt a folyamatot egy példán keresztül. Tegyük fel, hogy egy 10 elemből álló tömböt kell növekvő sorrendbe rendezni a közvetlen beillesztés módszerével

1 - lépés

13 6 8 11 3 1 5 9 15 7

menta (13). Be kell rakni egy másodikat.

tömbelem (6) úgy, hogy a

ség megmaradt. 6 óta< 13, вставляем

6 az első helyen. Rendezett rész

tömb két elemet tartalmaz (6 13).

3 - lépés

6 8 13 11 3 1 5 9 15 7 Következő elem- 11. A tömb rendezett részébe írják a harmadik helyre, hiszen 11 > 8 , de 11< 13.

5- lépés

3 6 8 11 13 1 5 9 15 7 Ugyanebből az okból kifolyólag 1-et írunk az elsőre

6 - lépés

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

A lányrész a harmadik.

7 -lépés

1 3 5 6 8 11 13 9 15 7 A 9-es szám helye a hatodik.

8 -lépés

1 3 5 6 8 9 11 13 15 7 Határozza meg az utolsó előtti helyét!

15. elem. Kiderül, hogy ez az elem

A tömb eleme már a helyén van.

9 -lépés

1 3 5 6 8 9 11 13 15 7 Már csak megfelelő helyet kell találni

Az utolsó elem (7).

1 3 5 6 7 8 9 11 13 15 A tömb teljesen rendezve van.

Most röviden leírhatjuk a közvetlen befogadás-rendezési algoritmus egy töredékét:

k:= 2 To n Do

(mivel úgy kezdem a válogatást, hogy jó helyet keresek a-nak, 2-ről n-re megyek)

'szúrja be az x-et a megfelelő helyre a , ..., a[k]-ba'

Meg kell válaszolni azt a kérdést, hogy hogyan keressünk megfelelő helyet az x elem számára. Tegyük a következőket: megnézzük az x-től balra található elemeket (vagyis azokat, amelyek már rendezve vannak), haladva a tömb elejére. Meg kell vizsgálni az a[ j ] , j elemeket k-1-ről 1-re változik. Az ilyen vizsgálatnak akkor kell véget érnie, ha az alábbi feltételek valamelyike ​​teljesül:

talált elem a[j]< x, что говорит о необходимости вставки x между a и a[j].

· a tömb rendezett részének bal végét elértük, ezért először x-et kell beszúrni.

Amíg ezen feltételek valamelyike ​​nem teljesül, addig a megtekintett elemeket az első pozícióba toljuk jobbra, aminek eredményeként x alatti hely szabadul fel a rendezett részben.

Közvetlen befogadás válogató program:

program n3; (Rendezés csökkenő sorrendben)

type ar=egész számok tömbje;

eljárás rendezés3(var a:ar);

var i,j,x,k:integer;

k:=2-hez n do

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

míg (j>0) és (x>=a[j]) igen

writeln("Adja meg a forrástömböt:");

mert i:=1-től n-ig olvass(a[i]);

writeln("Rendezett tömb:");

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

Célkitűzés Vizsgálja meg a tömbrendezést a közvetlen beillesztési módszerrel, és értékelje ennek az algoritmusnak a hatékonyságát.

Általános információ

A közvetlen befoglalási rendezést, az egyszerű kiválasztási rendezéshez hasonlóan, általában olyan tömbökhöz használják, amelyek nem tartalmaznak ismétlődő elemeket. Az ezzel a módszerrel történő rendezés lépésről lépésre szekvenciálisan történik. A k-edik lépésúgy tekintjük, hogy a tömb első k-1 elemeit tartalmazó része már rendezett, azaz. Ezután venni kell kth elemés úgy válasszunk neki helyet a tömb rendezett részében, hogy a beillesztése után a sorrendet ne zavarják meg, vagyis ilyet kell találni. Ezután be kell szúrni az a[k] elemet a talált helyre. Minden lépéssel növekszik a tömb rendezett része. A teljes rendezés végrehajtásához n-1 lépés szükséges. Meg kell válaszolni azt a kérdést, hogy hogyan keressünk megfelelő helyet az x elem számára. A következőképpen járunk el: megnézzük az x-től balra található elemeket (vagyis a már rendezetteket), haladva a tömb elejére. Szükséges az a[j], j elemek pásztázása k-l-ről 1-re változik. Az ilyen keresés akkor fejeződik be, ha az alábbi feltételek valamelyike ​​teljesül: az a[j] elemet megtaláltuk Példa Röviden írjuk le a rendezési algoritmus közvetlen beillesztéssel: k:= 2-től n-ig csináld beginx:= a[k]; j:=k-1; (szúrja be az x-et megfelelő helyre a, ..., a[k]-ba) (ehhez egy ciklust szervezünk, amely miközben fut) ( j > 0 és x

Ellenőrző feladat

Írjon programot, amely beilleszti egy tömb utolsó elemét ugyanannak a tömbnek az első negatív eleme után.

Feladat opciók

FIGYELEM!!! Hacsak nincs kifejezetten másképp jelezve, a bemeneti adatok (forrástömb) és a kimeneti adatok (rendezett tömb) a következőképpen vannak kialakítva szöveges fájl, egész számokat tartalmaz! Minden feladathoz előzetesen írjon egy eljárást egy tömb rendezésére a közvetlen beillesztés módszerével. 1. Adott egy n elemet tartalmazó sorozat. Rendezze őket növekvő sorrendbe, miközben elveti az összes ismétlődő elemet. 2. Határozza meg a divatot ezt a sort- elemei között leggyakrabban előforduló érték. 3. Az eredeti adatkészlet a vezetéknévből, életkorból és szolgálati időből álló rekordok sorozata. Nyomtassa ki ezt a listát: 1) ABC sorrendben; 2) az életkor növekedésének sorrendjében; 3) a munkatapasztalat növekedésének sorrendjében. 4. Írjon egy eljárást a csökkenő sorrendbe rendezéshez! 5. Adott egész számok sorozata. Mindent növekvő sorrendben különféle számok szerepel ebben a sorozatban. 6. n különböző egész számból álló sorozatot kapsz. Kapjon különálló egész számokat úgy, hogy 7. Adott egész számok Find legmagasabb érték ebben a sorrendben, miután eltávolított belőle minden tagot az értékkel 8. Adott természetes A számok n sportoló eredménye századmásodpercben mérve a 100 méteres távon A négy legjobb futóból alkoss csapatot a 4x100-as váltóban való részvételre, azaz jelöld meg a négy természetes szám egyikét i, j, k , l olyan, hogy az összeg a legkisebb értéke van. 9. Adott n független véletlen pont, koordinátákkal (xi; yi), egyenletesen elosztva egy 1 sugarú körben, amelynek középpontja az origóban van. Írjon programot, amely a pontokat a középponttól való növekvő távolság szerint rendezi! 10. Kapsz n pozitív kétjegyű egész számot. Ha az egyes számokat 0 és 9 közötti számjegypárként kezeli, rendezze őket (számokat) növekvő sorrendbe. 11. Adott n pont a síkon. Adjon meg egy (n-1)-link nem önmagát metsző zárt vonalláncot, amely átmegy ezeken a pontokon. (A vonallánc szomszédos szakaszai ugyanazon az egyenesen fekszenek.) Tipp. Vegyük a bal szélső pontot (azaz a legkisebb x-koordinátájú pontot), és onnan rajzoljunk sugarakat az összes többi pontba. Most rendezzük ezeket a sugarakat alulról felfelé, és az egyik sugáron lévő pontokat a sugár kezdetétől mért távolság szerint rendezzük (ez az alsó és a felső kivételével minden sugárra vonatkozik). A vonallánc elhagyja a kiválasztott (bal szélső) pontot az alsó sugár mentén, majd az összes többi sugár mentén (a leírt sorrendben), és a felső sugár mentén tér vissza. 12. Adott n pont a síkon. Szerkessze meg domború testüket - az őket tartalmazó minimális konvex alakzatot. (Deszkába vert szögekre feszített gumigyűrű a domború héjuk.) Javallat. Vegyük sorba a pontokat. Ezután a pontokat sorra figyelembe véve megszerkesztjük a már figyelembe vett pontok konvex héját.