Közvetlen beillesztési módszer. Tömbrendezési módszerek. A közvetlen beillesztési algoritmus hatékonysága

A befogadás rendezése a rendezetlen pozitív egész számok (általános nevén kulcsok) listáján működik, és növekvő sorrendbe rendezi őket. Ez nagyjából ugyanúgy történik, mint ahogy a legtöbb játékos elrendezi a nekik kiosztott lapokat, és egyszerre csak egy lapot vesz fel. Mutassuk meg, hogyan működik az általános eljárás a következő, nyolc egész számból álló rendezetlen lista példáján:

27 412 71 81 59 14 273 87.

A rendezett lista újra létrejön; eleinte üres. Minden iterációnál a rendezetlen lista első száma kikerül belőle, és a rendezett lista megfelelő pozíciójába kerül. Ehhez a rendezett listát a legkisebb számmal kezdve szkenneljük, amíg az új számnak megfelelő helyet nem találunk, pl. amíg minden kisebb értékű rendezett szám előtte, és minden nagy értékű szám utána nem található. A következő listasor mutatja meg, hogyan történik ez:

Iteráció 0

Rendezett 27

1. iteráció Rendezés nélkül 412 71 81 59 14 273 87

Rendezett 27 412

2. iteráció Rendezés nélkül 71 81 59 14 273 87

Válogatott 27 71 412

3. iteráció Rendezés nélkül 81 59 14 273 87

Válogatott 27 71 81 412

4. iteráció Rendezés nélkül 59 14 273 87

Válogatott 27 59 71 81 412

5. iteráció Rendezés nélkül 14 273 87

Rendezett 14 27 59 71 81 412

6. iteráció Rendezés nélkül 273 87

Rendezett 14 27 59 71 81 273 412

7. iteráció Rendezés nélkül 87

Rendezett 14 27 59 71 81 87 273 412

A következő algoritmusban csak egy lista indul, és a számok átrendeződnek a régi listában.

Algoritmus SIS(Rendezés a közvetlen befogadás szerint). Rendezze az I (1), I (2) egész számok sorozatát a régi helyre. ... ... , I (N) növekvő sorrendben.

1. lépés.[Fő iteráció]

J számára ← 2 nak nek N végigcsinálni 4. lépés od ;ésÁLLJON MEG.

2. lépés.[Következő egész szám kiválasztása] Készlet K ← I (J); és L ← J - 1.

3. lépés[Összehasonlítás rendezett egész számokkal] Míg K

ÉS L≥1 állítsd be I (L + 1) ← I (L); és L ← L - 1 od.

4. lépés.[ Bekapcsolni ] Készlet I (L + 1) ← K.

QUICKSORT:Rendezési algoritmus átlagos futási idővel O (N ln N)

A SIS algoritmus lassú működésének fő oka az, hogy a szekvenciában a kulcsok közötti összes összehasonlítás és csere a 1, a 2,. ... ... és N szomszédos elempárok esetén fordul elő. Ez a módszer viszonylag nagy

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

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

1 38 47 csökkenés a j

5 04 38 csere

6 08 38 növekedés i

10 38 79 csere

14 02 38 csere

15 76 38 növelése i,>

16 38 76 csere

17 38 56 csökkenés j

19 24 38 csere

20 57 38 növelése i,>

21 38 57 csere, csökkenés

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)

ideje egy nem helyén lévő kulcsot a megfelelő pozícióba helyezni a rendezendő sorrendben. Természetes, hogy megpróbáljuk felgyorsítani ezt a folyamatot a sorozatban egymástól távol eső elempárok összehasonlításával.

K. Hoore találta ki és nagyon hatékonyan alkalmazta ezt az ötletet (a QUICKSORT algoritmust), amivel a SIS algoritmus átlagos futási idejét O (N 2) nagyságrendről O (N ln N) nagyságrendre csökkentette. Magyarázzuk meg ezt az algoritmust a következő példával.

Tegyük fel, hogy az 1. ábra első sorából szeretnénk egy számsort rendezni. 15. Kezdjük azzal a feltételezéssel, hogy első a kulcs ebben a sorozatban (38) jó közelítését szolgálja annak a kulcsnak, amely végül a rendezett sorozat közepén fog megjelenni. Ezt az értéket pivotként használjuk, amelyhez képest a kulcsok felcserélhetők, és a következőképpen járunk el. Két I és J mutatót állítottunk be, amelyek közül I balról indul (I = 1), J - pedig balról a sorozatban (J = N). Összehasonlítva a Iés egy J... Ha a I ≤a J, állítsa be a J ← J − 1 értéket, és végezze el a következő összehasonlítást. Folytatjuk csökkenteni J amíg elérjük a I> a J. Akkor cseréljünk a I ↔a J(15. ábra, 5. sor, a 38-as és 04-es billentyűk cseréje), állítsa be az I ← I + 1-et és folytassa növekedésÉn, amíg meg nem érjük a I> a J. A következő csere után (10. sor, 79↔38) ismét csökkentjük a J-t. A csökkenő J és az I között váltakozva folytatjuk ezt a folyamatot a sorozat mindkét végétől a „középig”, amíg I = J-t nem kapunk.

Most két tény van. Először is, a kulcs (38), amely kezdetben az első pozícióban volt, ekkorra már a megfelelő helyén van a rendezett sorrendben. Először is, az elem bal oldalán lévő összes billentyű kisebb lesz, a jobb oldali billentyűk pedig nagyok.

Ugyanez az eljárás alkalmazható a bal és a jobb oldali részsorozatokra a teljes sorozat végső rendezéséhez. A 15. ábra utolsó sora (22-es számmal) azt mutatja, hogy ha I = J érkezik, akkor I = 7. Ezt követően az eljárást ismét alkalmazzuk az (1,6) és (8,16) részsorozatokra.

Az algoritmus rekurzív jellege azt sugallja, hogy a két rendezetlen részsorozat (8,16) közül a nagyobbik legkülső elemeinek indexeinek értékeit be kell tolni a verembe, majd folytatni kell a kisebb részsorozat rendezését (1,6). ).

A 15. ábra 4. sorában a 04-es szám a 2-es pozícióba került, és az (1,1) és (3,6) részsorozatokat rendezni kell. Mivel (1,1) már rendezve van (02-es szám), rendezzük (3,6), ami viszont a 6. sorhoz vezet, amelyben (3,4) és (6,6) rendezendő. A 7. sorban az (1,6) részsorozat rendezve van. Most kiemeljük (8,16) a veremből, és elkezdjük rendezni ezt a részsorozatot. A 13. sor tartalmazza a (8,11) és (13,16) részsorozatokat, amelyeket rendezni kell. A veremre rakjuk (13,16), rendezzük (8,11) stb. A 20. sorban a teljes sorozat rendezve van.

Mielőtt hivatalosan leírná a QUICKSORT algoritmust, pontosan meg kell mutatnia, hogyan működik. A [LEFT (K), RIGHT (K)] verem segítségével tároljuk a rendezetlen részsorozatok bal és jobb szélső elemeinek indexeit. Mivel a rövid részsorozatok a normál algoritmussal gyorsabban rendeződnek, a QUICKSORT algoritmusnak van egy M bemeneti paramétere, amely meghatározza, hogy milyen rövidnek kell lennie a részsorozatnak ahhoz, hogy a szokásos módon rendezhető legyen.

Keresés

Most térjünk rá az adatstruktúrák információ-visszakeresésével kapcsolatos néhány fő probléma vizsgálatára. A rendezésről szóló előző részhez hasonlóan azt feltételezzük, hogy minden információt olyan rekordokban tárolunk, amelyek kulcsértékekkel azonosíthatók, pl. az R i rekord a K i-vel jelölt kulcsértéknek felel meg.

Tegyük fel, hogy a fájl N rekordot tartalmaz véletlenszerűen, lineáris tömb formájában. Egyértelmű keresési módszer adott rekord a billentyűk egymás utáni nézete lesz. Ha megtalálják szükséges kulcs, a keresés sikeresen befejeződik; Ellenkező esetben az összes kulcsot átvizsgálja, és a keresés sikertelen lesz, ha a kulcsok összes lehetséges sorrendje egyformán valószínű, akkor egy ilyen algoritmus O (N) alapműveletet igényel a legrosszabb és átlagos esetekben is. A keresési idő érezhetően csökkenthető a fájl kulcsonkénti előrendelésével. Ennek az előkészítő munkának akkor van értelme, ha a fájl elég nagy és gyakran hozzáfér.

Tegyük fel, hogy a fájl közepére mentünk, és ott találtuk a K i kulcsot. Hasonlítsuk össze K-t és K i-t. Ha K = K i, akkor a kívánt rekordot megtaláltuk. Ha K<К i ,то ключ К должен находиться в части файла, предшествующей К i (если запись с ключом К вообще существует) . Аналогично, если К i <К, то дальнейший поиск следует вести в части файла, следующей за К i . Если повторять эту процедуру проверки ключа К i из середины непросмотренной части файла, тогда каждое безуспешное сравнение К с К i будет исключать из рассмотрения приблизительно половину непросмотренной части.

Ennek az eljárásnak a folyamatábrája, az úgynevezett bináris keresés, amely a 16. ábrán látható

Algoritmus BSEARCH (Bináris keresés) rekord keresése a K kulccsal egy N≥2 rekordot tartalmazó fájlban, amelyek kulcsai növekvő sorrendben vannak K 1<К 2 …<К N .

0. lépés.[Inicializálás] Készlet ELSŐ ← 1; UTOLSÓ ← ​​N. (FIRST és LAST a fájl még meg nem nézett részének első és utolsó kulcsára mutat.)

1. lépés.[Fő hurok] Míg UTOLSÓ≥ELSŐ végigcsinálni 4. lépés od.

2. lépés.[Központi kulcs beszerzése] Készlet I ← | _ (ELSŐ + UTOLSÓ) / 2_ | (A K i egy kulcs, amely a fájl még meg nem nézett részének közepén vagy a közepétől balra található.)

3. lépés[Sikeres befejezés ellenőrzése] Ha K = K I azután NYOMTATÁS "Sikeres befejezés, a kulcs a K I"; ésÁLLJON MEG fi.

4. lépés.[Összehasonlítás] Ha K < K I majd állítsa be UTOLSÓ ← ​​I-1 más meg ELSŐ ← I + 1 fi.

5. lépés.[A keresés sikertelen] PRINT "sikertelen"; ésÁLLJON MEG.

A 17. ábrán a BSEARCH algoritmus segítségével találjuk meg a K = 42 értéket.

A bináris keresés arra is használható, hogy egy rendezett fájlt bináris faként ábrázoljon. A 2. lépés első végrehajtása során talált kulcsérték (K (8) = 53) a fa gyökere. Az ettől az értéktől balra (1,7) és jobbra (9,16) lévő kulcsintervallumok a verembe kerülnek. A felső rekesz lekerül a kötegről, és a 2. lépés megkeresi a középső elemet (vagy a középsőtől balra lévő elemet). Ez a kulcs (K (4) = 33) lesz a következő elem a gyökér után balra, ha értéke kisebb, mint a gyökér értéke, ellenkező esetben pedig a jobbra következő elem. Ennek az intervallumnak az újonnan hozzáadott kulcstól jobbra és balra eső részintervallumai [(1,3), (5,7)] most a verembe kerülnek, és ezt az eljárást addig ismételjük, amíg a verem ki nem ürül. A 18. ábra egy bináris fát mutat, amely a 17. ábra 16 rendezett kulcsához készülne.

A bináris keresés most úgy értelmezhető, hogy a fát a gyökértől a kívánt rekordig bejárja. Ha elérjük a végső csúcsot, és a megadott kulcs nem található, akkor a fájlból hiányzik a szükséges bejegyzés. Vegye figyelembe, hogy a gyökértől egy adott K kulcsig tartó egyetlen útvonal csúcsainak száma megegyezik a BSEARCH algoritmus által végrehajtott összehasonlítások számával, amikor megpróbálja megtalálni K-t.

Igen

A befogadás rendezése, az egyszerű kijelölési rendezéshez hasonlóan, általában olyan tömbökhöz használatos, amelyek nem tartalmaznak ismétlődő elemeket.

Az ezzel a módszerrel történő rendezés lépésről lépésre, egymás után történik. Tovább k-A lépésben a tömb azon részét tekintjük, amely az elsőt tartalmazza k– 1 darab már megrendelt, azaz.

Következő, meg kell venni k–Az elemet, és keress neki helyet a tömb rendezett részében, hogy a beillesztése után ne sérüljön meg a sorrend, vagyis olyat kell találni, hogy. Ezután be kell illesztenie az elemet a (k) a talált helyre.

Minden lépéssel növekszik a tömb rendezett része. A teljes rendezés végrehajtásához meg kell tennie n- 1. lépés.

Továbbra is meg kell válaszolni azt a kérdést, hogyan lehet megfelelő helyet találni egy elem számára NS... A következőképpen járunk el: megtekintjük a bal oldalán található elemeket NS(vagyis azok, amelyek már meg vannak rendelve), a tömb elejére lépve. Meg kell nézni az elemeket a (j), j között változik k– l-től 1-ig. Ez a vizsgálat akkor fejeződik be, ha az alábbi feltételek egyike teljesül:

Olyan elemet találtunk, amely beszúrás szükségességét jelzi NS között és a (j).

Elérte a tömb rendezett részének bal végét, ezért be kell szúrni NS az első helyre.

Amíg ezen feltételek valamelyike ​​nem teljesül, a megtekintett elemeket 1 pozícióval jobbra toljuk, aminek eredményeként a rendezett részben hely szabadul fel NS.

A válogatás technikáját a 2. táblázat szemlélteti:

2. táblázat - Példa a rendezésre közvetlen beszámítással

Az eredetileg rendezett sorozat az 1. elemből áll, 9. Elem a( 2) = 5 a rendezetlen sorozat első része, az 5 pedig< 9, поэтому ставится на его место, а 9 сдвигается вправо. Теперь упорядоченная последовательность состоит из двух элементов 5, 9. Элемент a( 3) A rendezetlen sorozat = 15 értéke nagyobb, mint a rendezett sorozat összes eleme, ezért a rendezett sorozat a helyén marad és a következő lépésben a rendezett sorozat 5, 9, 15, a vizsgált elem pedig 6. A folyamat addig folytatódik, amíg a szekvencia rendezettné nem válik.

Shaker válogatás

A buborékmódszernek három egyszerű fejlesztése van. Először is, ha egy lépésben egyetlen csere sem történt, akkor az algoritmus végrehajtása megszakítható. Másodszor, megjegyezheti annak a tömbindexnek a legkisebb értékét, amelyhez az aktuális lépésben a permutációt végrehajtották. Nyilvánvalóan a tömb teteje az ezzel az indexszel rendelkező elemig már rendezve van, és a következő lépésben leállíthatja a szomszédos elemek értékeinek összehasonlítását, ha elérte ezt az indexértéket. Harmadszor, a buborékos módszer egyenlőtlenül működik „könnyű” és „nehéz” értékek esetén. A light érték egy lépésben a megfelelő helyre kerül, a nehéz pedig minden lépésnél egy pozíciót a megfelelő helyre esik.

A ShakerSort módszer ezeken a megfigyeléseken alapul. Amikor alkalmazza, minden következő lépésnél a szekvenciális megtekintés iránya megváltozik. Ennek eredményeként az egyik lépésben a következő legkönnyebb elem "felugrik", a másiknál ​​pedig a következő legnehezebb elem "süllyed". A 3. táblázatban látható egy példa rázógépre.

3. táblázat - Példa rázógépre

Tömb rendezése zárványok használatával csökkenő távolsággal (Shell módszer)

D. Schell a válogatás javítását javasolta a közvetlen bevonással.

A módszer ötlete: az összes tömbelemet csoportokra osztják úgy, hogy minden csoportba olyan elemek tartoznak, amelyek egymástól bizonyos számú pozícióval el vannak választva. L... Az egyes csoportok elemei rendezve vannak. Ezt követően az összes elemet újra egyesítik és csoportokba rendezik, miközben az elemek közötti távolság csökken. A folyamat az elemek sorrendjének végrehajtása után ér véget, a távolság 1.

A Shell rendezésre egy példa látható a 4. táblázatban.

4. táblázat - Példa a Shell rendezésre

Először is, fontolja meg a lehetőséget, amikor a kezdeti érték L egyenlő a tömb elemeinek számának felével, és minden következő érték az előző felével. Vegye figyelembe, hogy az egymástól bizonyos távolságra lévő elemek cseréje történik. Ha 2 elem összehasonlításakor a csere nem történt meg, akkor az összehasonlított elemek helyei egy pozícióval jobbra tolódnak el. Ha a csere megtörtént, akkor a megfelelő összehasonlított elemek eltolódnak L.

Osztott rendezés (gyors rendezés)

Az osztott válogatás módszerét Charles Hoare javasolta. Ez a módszer az egyszerű cseremódszer továbbfejlesztése, és annyira hatékony, hogy „Quicksort” módszerként vált ismertté.

Az algoritmus fő gondolata az, hogy a tömb egyes elemeit véletlenszerűen választják ki x, ami után a tömb balról vizsgálódik, amíg egy elemet nem talál a (i) oly módon, hogy a (i) > x majd a tömböt jobbról szkenneljük, amíg meg nem találjuk az elemet a (i) oly módon, hogy a (i)< x... Ez a két elem felcserélődik, és a megtekintés, az összehasonlítás és a csere folyamata folytatódik, amíg el nem jutunk az elemhez x... Ennek eredményeként a tömb két részre lesz osztva - a bal oldali részre, amelyben a kulcsok értéke kisebb lesz x, és a megfelelő kulcsértékek nagyobbak, mint x... A folyamat ezután rekurzív módon folytatódik a tömb bal és jobb oldalán, amíg minden rész pontosan egy elemet nem tartalmaz. A rekurzió helyettesíthető iterációkkal, ha emlékszel a megfelelő tömbindexekre.

A tömb gyorsmódszerrel történő rendezésének folyamata az 5. táblázatban látható.

5. táblázat – Példa a gyorsválogatásra

A befogadás rendezése, az egyszerű kijelölési rendezéshez hasonlóan, általában olyan tömbökhöz használatos, amelyek nem tartalmaznak ismétlődő elemeket.

A közvetlen beillesztési módszerrel történő rendezés a fent leírtakhoz hasonlóan 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 válasszunk neki egy helyet a tömb rendezett részében, hogy a beillesztése után ne zavarják a sorrendet, azaz meg kell találni egy ilyen j-t (1 ≤ j ≤ k -1) úgy, hogy a [j] ≤ a [ k]< a. Затем вставить элемент а [k] на найденное место.

Minden lépéssel növekszik a tömb rendezett része. A teljes rendezés n-1 lépést igényel.

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 szeretne 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 Tekintsük egy elemből álló tömb egy részét

ment (13). Be kell szúrni egy másodikat

a tömb (6) egy eleme úgy, hogy a rendezett

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

6 az első helyen. Rendezett rész

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

3 - lépés

6 8 13 11 3 1 5 9 15 7 A következő elem a 11. A tömb rendezett részére íródik a harmadik helyre, mivel 11> 8, de 11< 13.

5- lépés

3 6 8 11 13 1 5 9 15 7 Ugyanebből az okból írunk 1-et 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 gyermek ré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ömbzsaru 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ó tétel (7).

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

Most röviden leírhatjuk a rendezési algoritmus egy töredékét a közvetlen beillesztési módszerrel:

k esetén: = 2 - n Do

(mivel a rendezést úgy kezdjük, hogy megtaláljuk a megfelelő helyet, az i 2-ről n-re változik)

"Szúrjon be x-et megfelelő helyre a, ..., a [k]-ba"

Továbbra is meg kell válaszolni azt a kérdést, hogyan lehet megfelelő helyet találni az x elem számára. A következőképpen járjunk el: végignézzük az x-től balra található elemeket (vagyis a már rendezetteket), haladva a tömb elejére. Meg kell tekinteni az a [j], j elemeket, amelyek k-1 és 1 között változnak. 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].

· Elértük a tömb rendezett részének bal végét, 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 a rendezett részben hely szabadul fel x számára.

Közvetlen válogató program:

program n3; (Csökkenő rendezés)

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

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

var i, j, x, k: egész szám;

k esetén: = 2-től n-ig

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

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

writeln ("Adja meg az eredeti tömböt:");

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

writeln ("Rendezett tömb:");

i esetén: = 1-től n-ig írjon (a [i], "");

Ezt a módszert széles körben használják kártyázáskor. Az elemek (kártyák) gondolatban 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 kezdődően) az i-edik elemet kiemeljük a nem rendezett részből és a „kész” részbe helyezzük, miközben beillesztjük a kívánt helyre.

Módszer szöveges algoritmusa:

1. Kezdet.

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

a) helyezzük az i-edik elemet (A (i)) az A cellába (0);

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 А (0) ≥ А (j), akkor az А (0) elemet az А cellába (j + 1), ellenkező esetben az А (j) elemet az А (j + 1) cellába kell helyezni. , csökkentse j értékét eggyel, és hajtsa végre újra a c) tételt.

ábrán. Az 1. ábra a közvetlen befogadási módszerrel történő rendezés blokkdiagramját mutatja.

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)). Ez az elem összehasonlításra kerül a tőle balra lévő elemmel a "kész" részben. Ha az A (0) elem kisebb, akkor az összehasonlított (j-edik elem) egy pozícióval jobbra tolódik, majd a következő elem kerül összehasonlításra. Ha az A (0) elem nem kisebb, mint az összehasonlítás, akkor közvetlenül az összehasonlított elem utáni helyre kerül.

Rizs. 1. Közvetlen felvételi módszerrel történő rendezés blokkdiagramja

ábrán. A 2. ábra egy példát mutat be a közvetlen befogadási módszerrel történő rendezésre.

Eredeti sorrend
	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ási módszerrel történő rendezésre

A közvetlen befogadó rendezés arra az esetre alkalmasabb, ha a rendezendő adatok szekvenciálisan (egymás után) jönnek.

Rendezés közvetlen kiválasztási módszerrel

A módszer lényege a következő. A "fennmaradó" (nem rendezett) rész legkisebb eleme kiválasztásra kerül, és felcserélődik az első tétellel (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 csak egy marad. bal, legnagyobb elem.

Ez a módszer bizonyos értelemben ellentéte a közvetlen befogadás módszerének. A közvetlen beillesztés módszerében 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 felvételi pontját. Az egy (minimum) elem megtalálásának közvetlen kiválasztási módszerében pedig a rendezetlen rész összes eleme beszkennelésre kerül, és ez a minimális elem újabb elemként kerül a már „kész” részbe.

Módszer szöveges algoritmusa:

1. Kezdet.

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

a) helyezzük az aktuális (i-edik) elemet valamilyen memóriacellába (X), és emlékezzünk az aktuális elem sorszámára (i) (a K változóban);

b) hajtson végre egy ciklust, miközben j értékei i + 1-től (vagyis az i után következő elemtől N-ig), lépés = +1:

a ciklus teste: ha X> A (j), akkor az A (j) elemet tesszük az X cellába, és megjegyezzük a számát a K cellában;

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

ábrán. A 3. ábra egy példát mutat be a közvetlen kiválasztási módszerrel történő rendezésre.

Eredeti sorrend	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

Rizs. 3. Példa közvetlen kiválasztási módszerrel történő rendezésre