Metóda priameho vkladania. Metódy triedenia polí. Efektívnosť algoritmu priamej inklúzie

Inclusion sort funguje na zozname neusporiadaných kladných celých čísel (bežne nazývaných kľúče), pričom ich triedi vzostupne. Robí sa to takmer rovnakým spôsobom, ako väčšina hráčov usporiada karty, ktoré im boli rozdané, pričom si zbierajú jednu kartu po druhej. Ukážme si, ako funguje všeobecný postup, na príklade nasledujúceho nezoradeného zoznamu ôsmich celých čísel:

27 412 71 81 59 14 273 87.

Zoradený zoznam sa vytvorí znova; najprv je prázdny. Pri každej iterácii sa z neho odstráni prvé číslo nezoradeného zoznamu a umiestni sa na zodpovedajúcu pozíciu v zoradenom zozname. Na tento účel sa skenuje zoradený zoznam, počnúc najmenším číslom, až kým sa nenájde vhodné miesto pre nové číslo, t.j. kým nebudú všetky zoradené čísla s nižšími hodnotami pred ním a všetky čísla s veľkými hodnotami za ním. Nasledujúca postupnosť zoznamov ukazuje, ako sa to robí:

Iterácia 0

Zoradené 27

Iterácia 1 Nezaradené 412 71 81 59 14 273 87

Zoradené podľa 27 412

Iterácia 2 Nezaradené 71 81 59 14 273 87

Roztriedené 27 71 412

Iterácia 3 Nezaradené 81 59 14 273 87

Roztriedené 27 71 81 412

Iterácia 4 Netriedené 59 14 273 87

Roztriedené 27 59 71 81 412

Iterácia 5 Netriedené 14 273 87

Zoradené 14 27 59 71 81 412

Iterácia 6 Netriedené 273 87

Triedené 14 27 59 71 81 273 412

Iterácia 7 Netriedené 87

Zoradené 14 27 59 71 81 87 273 412

V nasledujúcom algoritme sa spustí iba jeden zoznam a čísla sa preusporiadajú v starom zozname.

Algoritmus SIS(Zoradiť podľa priameho zaradenia). Zoraďte postupnosť celých čísel I (1), I (2) na starom mieste. ... ... , I (N) vo vzostupnom poradí.

Krok 1.[Hlavná iterácia]

Pre J ← 2 do N urobiť cez krok 4 od ;a STOP.

Krok 2.[Vybrať ďalšie celé číslo] Set K←I (J); a L ← J − 1.

Krok 3[Porovnanie so zoradenými celými číslami] Zatiaľ čo K

A L≥1 nastaviť ja (L + 1) ← I (L); a L ← L − 1 od.

Krok 4[ Zapínanie ] Set I (L + 1) ← K.

QUICKSORT:Algoritmus triedenia s priemernou dobou chodu O (N ln N)

Hlavným dôvodom pomalého fungovania algoritmu SIS je, že všetky porovnávania a výmeny medzi kľúčmi v sekvencii a 1, a 2,. ... ... a N vyskytujú pre dvojice susedných prvkov. Táto metóda vyžaduje pomerne veľké

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

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

1 38 47 pokles j

5 04 38 výmena

6 08 38 zvýšenie i

10 38 79 výmena

14 02 38 výmena

15 76 38 zvýšenie i,>

16 38 76 výmena

17 38 56 pokles j

19 24 38 výmena

20 57 38 zvýšenie i,>

21 38 57 výmena, úbytok

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)

čas umiestniť nemiestny kľúč na správnu pozíciu v poradí, v akom sa má triediť. Je prirodzené pokúsiť sa tento proces urýchliť porovnávaním dvojíc prvkov, ktoré sú v postupnosti od seba ďaleko.

K. Hoore vynašiel a veľmi efektívne aplikoval túto myšlienku (algoritmus QUICKSORT), čím sa znížil priemerný čas chodu algoritmu SIS z rádu O (N 2) na rád O (N ln N). Vysvetlime si tento algoritmus na nasledujúcom príklade.

Predpokladajme, že chceme zoradiť postupnosť čísel z prvého riadku na obrázku 1. 15. Začnime s predpokladom, že najprv kľúč v tejto sekvencii (38) slúži ako dobrá aproximácia kľúča, ktorý sa nakoniec objaví v strede zoradeného poradia. Túto hodnotu použijeme ako pivot, vzhľadom na ktorý možno kľúče prehodiť, a postupujeme nasledovne. Nastavíme dva ukazovatele I a J, z ktorých I začína zľava (I = 1) a J - zľava v poradí (J = N). Porovnaním ja a a J... Ak a I ≤a J, nastavte J ← J − 1 a vykonajte nasledujúce porovnanie. Pokračujeme ďalej znížiť J, kým nedosiahneme a I> a J. Potom sa vymeníme a I ↔a J(obr. 15, riadok 5, výmena kľúčov 38 a 04), nastavte I ← I + 1 a pokračujte zvýšiť Ja kým sa nedostaneme a I> a J. Po ďalšej výmene (riadok 10, 79↔38) opäť znížime J. Striedavo medzi znižovaním J a zvyšovaním I pokračujeme v tomto procese z oboch koncov postupnosti do „stredu“, kým nedostaneme I = J.

Teraz sú tu dve skutočnosti. Po prvé, kľúč (38), ktorý bol pôvodne na prvej pozícii, je v tomto čase na svojom správnom mieste v zoradenom poradí. Po prvé, všetky klávesy naľavo od tejto položky budú menšie a všetky klávesy napravo budú veľké.

Rovnaký postup možno aplikovať na ľavú a pravú podsekvenciu na konečné zoradenie celej sekvencie. Posledný riadok (očíslovaný 22) na obr. 15 ukazuje, že keď sa prijme I = J, potom I = 7. Potom sa postup opäť aplikuje na podsekvencie (1,6) a (8,16).

Rekurzívna povaha algoritmu naznačuje, že hodnoty indexov najvzdialenejších prvkov väčšej z dvoch nezoradených podsekvencií (8,16) by sa mali vložiť do zásobníka a potom pristúpiť k triedeniu menšej podsekvencie (1,6). ).

V riadku 4 na obr. 15 sa číslo 04 presunulo na pozíciu 2 a podsekvencie (1, 1) a (3, 6) sa majú zoradiť. Keďže (1,1) je už zoradené (číslo 02), zoradíme (3,6), čo zase vedie k riadku 6, v ktorom sa majú zoradiť (3,4) a (6,6). Na riadku 7 je triedená podsekvencia (1,6). Teraz vyberieme (8,16) zo zásobníka a začneme triediť túto podsekvenciu. Riadok 13 obsahuje podsekvencie (8,11) a (13,16), ktoré je potrebné zoradiť. Dáme (13,16) na zásobník, triedime (8,11) atď. Na riadku 20 sa zoradí celá sekvencia.

Predtým, ako formálne popíšete algoritmus QUICKSORT, musíte presne ukázať, ako funguje. Zásobník [LEFT (K), RIGHT (K)] používame na uloženie indexov prvkov najviac vľavo a vpravo v nezoradených podsekvenciách. Keďže krátke podsekvencie sa pomocou bežného algoritmu triedia rýchlejšie, algoritmus QUICKSORT má vstupný parameter M, ktorý určuje, aká krátka musí byť podsekvencia, aby sa triedila bežným spôsobom.Na tento účel používame Simple Inclusion Sort (SIS).

Vyhľadávanie

Teraz prejdime k štúdiu niektorých hlavných problémov súvisiacich s vyhľadávaním informácií o dátových štruktúrach. Rovnako ako v predchádzajúcej časti o triedení budeme predpokladať, že všetky informácie sú uložené v záznamoch, ktoré možno identifikovať podľa kľúčových hodnôt, t.j. záznam R i zodpovedá kľúčovej hodnote označenej Ki.

Predpokladajme, že súbor obsahuje N záznamov náhodným spôsobom vo forme lineárneho poľa. Jednoznačná metóda vyhľadávania daný záznam bude sekvenčný pohľad na klávesy. Ak sa nájde požadovaný kľúč, vyhľadávanie sa úspešne skončí; v opačnom prípade budú všetky kľúče naskenované a vyhľadávanie bude neúspešné Ak sú všetky možné poradia kľúčov rovnako pravdepodobné, potom takýto algoritmus vyžaduje O (N) základných operácií v najhoršom aj priemernom prípade. Čas vyhľadávania možno výrazne skrátiť predobjednávkou súboru pomocou kľúčov. Táto prípravná práca má zmysel, ak je súbor dostatočne veľký a často sa k nemu pristupuje.

Predpokladajme, že sme išli do stredu súboru a našli sme tam kľúč K i. Porovnajme K a K i. Ak K = K i, požadovaný záznam bol nájdený. Ak K<К i ,то ключ К должен находиться в части файла, предшествующей К i (если запись с ключом К вообще существует) . Аналогично, если К i <К, то дальнейший поиск следует вести в части файла, следующей за К i . Если повторять эту процедуру проверки ключа К i из середины непросмотренной части файла, тогда каждое безуспешное сравнение К с К i будет исключать из рассмотрения приблизительно половину непросмотренной части.

Vývojový diagram tohto postupu, známy ako binárne vyhľadávanie 16

Algoritmus BSEARCH (Binárne vyhľadávanie) vyhľadávanie záznamu s kľúčom K v súbore s N≥2 záznamami, ktorých kľúče sú zoradené vzostupne K 1<К 2 …<К N .

Krok 0.[Inicializácia] Set PRVÁ ← 1; LAST ← N. (FIRST a LAST sú ukazovatele na prvý a posledný kľúč v ešte nezobrazenej časti súboru.)

Krok 1.[Hlavná slučka] Zatiaľ čo POSLEDNÝ≥PRVÝ urobiť cez krok 4 od.

Krok 2.[Získanie centrálneho kľúča] Set I ← | _ (PRVÝ + POSLEDNÝ) / 2_ | (K i je kláves umiestnený v strede alebo naľavo od stredu časti súboru, ktorá ešte nebola zobrazená.)

Krok 3[Skontrolujte úspešné dokončenie] Ak K = K I potom TLAČ "Úspešné dokončenie, kľúčom je K I"; a STOP fi.

Krok 4[Porovnanie] Ak K < K I potom nastavte POSLEDNÉ ← I-1 inak nastavený PRVÝ ← I + 1 fi.

Krok 5.[Hľadanie neúspešné] PRINT "neúspešné"; a STOP.

Algoritmus BSEARCH sa používa na nájdenie K = 42 na obrázku 17.

Binárne vyhľadávanie možno použiť aj na reprezentáciu usporiadaného súboru ako binárneho stromu. Hodnota kľúča nájdená v prvom vykonaní kroku 2 (K (8) = 53) je koreň stromu. Intervaly kľúčov naľavo (1,7) a napravo (9,16) od tejto hodnoty sa vložia do zásobníka. Horný zásobník sa vysunie zo stohu a krok 2 nájde stredný prvok (alebo prvok naľavo od stredu). Tento kľúč (K (4) = 33) sa stane ďalším prvkom po odmocnení vľavo, ak je jeho hodnota menšia ako hodnota odmocnina, a v opačnom prípade ďalším prvkom vpravo. Podintervaly tohto intervalu napravo a naľavo od novo pridaného kľúča [(1,3), (5,7)] sa teraz vložia do zásobníka.Tento postup sa opakuje, kým zásobník nie je prázdny. Obrázok 18 zobrazuje binárny strom, ktorý by sa vytvoril pre 16 usporiadaných kľúčov na obrázku 17.

Binárne vyhľadávanie možno teraz interpretovať ako prechádzanie týmto stromom od koreňa k požadovanému záznamu. Ak sa dosiahne konečný vrchol a zadaný kľúč sa nenájde, požadovaný záznam v tomto súbore chýba. Všimnite si, že počet vrcholov na jednej ceste od koreňa k danému kľúču K sa rovná počtu porovnaní vykonaných algoritmom BSEARCH pri pokuse nájsť K.

Áno

Triedenie zahrnutia, podobne ako jednoduché triedenie výberu, sa zvyčajne používa pre polia, ktoré neobsahujú duplicitné prvky.

Triedenie touto metódou sa vykonáva krok za krokom postupne. Na k-Tý krok sa považuje za časť poľa, ktorá obsahuje prvý k– 1 tovar je už objednaný, tzn.

Ďalej musíte vziať k–Prvok a nájdite preň miesto v triedenej časti poľa tak, aby sa po jeho vložení neporušilo zoradenie, to znamená, že je potrebné nájsť také, že. Potom musíte vložiť prvok a (k) na nájdené miesto.

S každým krokom triedená časť poľa rastie. Ak chcete vykonať úplné triedenie, musíte to urobiť n– Krok 1.

Zostáva odpovedať na otázku, ako nájsť vhodné miesto pre prvok X... Budeme postupovať nasledovne: pozrieme si prvky umiestnené vľavo od X(teda tie, ktoré sú už zoradené), presun na začiatok poľa. Musíte si pozrieť položky a (j), j sa líši od k– l až 1. Toto skenovanie sa skončí, ak je splnená jedna z nasledujúcich podmienok:

Bol nájdený prvok, ktorý naznačuje potrebu vloženia X medzi a a (j).

Dosiahol sa ľavý koniec objednanej časti poľa, preto ho musíte vložiť X na prvé miesto.

Kým nie je splnená jedna z týchto podmienok, budeme posúvať prezerané prvky o 1 pozíciu doprava, čím sa uvoľní miesto v triedenej časti pre X.

Technika triedenia je znázornená v tabuľke 2:

Tabuľka 2 - Príklad triedenia pomocou priameho zaradenia

Pôvodne usporiadaná postupnosť pozostáva z 1. prvku 9. prvku a( 2) = 5 je prvá z neusporiadanej postupnosti a 5< 9, поэтому ставится на его место, а 9 сдвигается вправо. Теперь упорядоченная последовательность состоит из двух элементов 5, 9. Элемент a( 3) = 15 neusporiadanej postupnosti je väčšie ako všetky prvky usporiadanej postupnosti, preto usporiadaná postupnosť zostáva na svojom mieste a v ďalšom kroku sa usporiadaná postupnosť skladá z 5, 9, 15 a uvažovaný prvok je 6. proces pokračuje, kým sa sekvencia nestane usporiadanou.

Triedenie šejkra

Bublinová metóda má tri jednoduché vylepšenia. Po prvé, ak v niektorom kroku nebola vykonaná ani jedna výmena, potom môže byť vykonanie algoritmu ukončené. Po druhé, môžete si zapamätať najmenšiu hodnotu indexu poľa, pre ktorú boli permutácie vykonané v aktuálnom kroku. Je zrejmé, že horná časť poľa až po prvok s týmto indexom je už zoradená a v ďalšom kroku môžete zastaviť porovnávanie hodnôt susedných prvkov, keď sa dosiahne táto hodnota indexu. Po tretie, bublinková metóda funguje nerovnomerne pre „ľahké“ a „ťažké“ hodnoty. Ľahká hodnota sa dostane na správne miesto v jednom kroku a vysoká hodnota klesne o jednu pozíciu smerom k správnemu miestu pri každom kroku.

Metóda ShakerSort je založená na týchto pozorovaniach. Keď ho použijete, pri každom ďalšom kroku sa zmení smer sekvenčného zobrazenia. Výsledkom je, že v jednom kroku „vyskočí“ ďalší najľahší prvok a v druhom „klesne“ ďalší najťažší prvok. Príklad triedenia trepačky je uvedený v tabuľke 3.

Tabuľka 3 - Príklad triedenia trepačky

Triedenie poľa pomocou inklúzií s klesajúcimi vzdialenosťami (metóda Shell)

D. Schell navrhol zlepšenie triedenia pomocou priameho zaradenia.

Myšlienka metódy: všetky prvky poľa sú rozdelené do skupín takým spôsobom, že každá skupina obsahuje prvky vzdialené od seba určitým počtom pozícií L... Prvky každej skupiny sú zoradené. Potom sa všetky prvky znova kombinujú a triedia do skupín, pričom sa vzdialenosť medzi prvkami zmenšuje. Proces sa skončí po vykonaní zoradenia prvkov so vzdialenosťou medzi nimi rovnajúcou sa 1.

Príklad triedenia Shell je uvedený v tabuľke 4.

Tabuľka 4 - Príklad triedenia škrupín

Najprv zvážte možnosť, keď je počiatočná hodnota L sa rovná polovici počtu prvkov v poli a každá nasledujúca hodnota je polovica predchádzajúcej hodnoty. Všimnite si, že sa vymieňajú prvky, ktoré sú od seba vzdialené. Ak pri porovnávaní 2 prvkov k zámene nedošlo, tak sa miesta porovnávaných prvkov posúvajú doprava o jednu pozíciu. Ak prebehla výmena, potom sa zodpovedajúce porovnávané prvky posunú o L.

Rozdeliť triedenie (rýchle triedenie)

Metódu deleného triedenia navrhol Charles Hoare. Táto metóda je rozvinutím metódy jednoduchej výmeny a je taká účinná, že sa stala známou ako metóda „Quicksort“.

Hlavnou myšlienkou algoritmu je, že niektorý prvok poľa je náhodne vybraný X, po ktorom sa pole skenuje zľava, kým sa nenájde prvok a (i) také že a (i) > X a potom sa pole skenuje sprava, kým nenarazí na prvok a (i) také že a (i)< X... Tieto dva prvky sa vymenia a proces prezerania, porovnávania a výmeny pokračuje, kým sa nedostaneme k prvku X... V dôsledku toho bude pole rozdelené na dve časti - ľavú, v ktorej budú kľúčové hodnoty menšie X a ten správny s kľúčovými hodnotami väčšími ako X... Proces potom pokračuje rekurzívne pre ľavú a pravú časť poľa, kým každá časť neobsahuje presne jeden prvok. Rekurzia môže byť nahradená iteráciami, ak si pamätáte zodpovedajúce indexy poľa.

Proces triedenia poľa rýchlou metódou je uvedený v tabuľke 5.

Tabuľka 5 - Príklad rýchleho triedenia

Triedenie zahrnutia, podobne ako jednoduché triedenie výberu, sa zvyčajne používa pre polia, ktoré neobsahujú duplicitné prvky.

Triedenie metódou priameho zaradenia, ako všetky vyššie opísané, sa vykonáva v krokoch. V k-tom kroku sa uvažuje, že časť poľa obsahujúca prvých k-1 prvkov je už usporiadaná, t.

a ≤ a ≤ ... ≤ a.

Ďalej musíte zobrať k-tý prvok a vybrať preň miesto v triedenej časti poľa tak, aby po jeho vložení nebolo narušené zoradenie, to znamená, že musíte nájsť také j (1 ≤ j ≤ k -1) tak, že a [j] ≤ a [ k]< a. Затем вставить элемент а [k] на найденное место.

S každým krokom triedená časť poľa rastie. Úplné triedenie vyžaduje n-1 krokov.

Pozrime sa na tento proces na príklade. Predpokladajme, že chcete triediť pole 10 prvkov vo vzostupnom poradí metódou priameho zahrnutia

1 - krok

13 6 8 11 3 1 5 9 15 7 Uvažujme časť poľa jedného prvku

ment (13). Musíte do nej vložiť sekundu

prvok poľa (6) tak, aby usporiadaný

nosť sa zachovala. Od 6< 13, вставляем

6 na prvom mieste. Vytriedená časť

pole obsahuje dva prvky (6 13).

3 - krok

6 8 13 11 3 1 5 9 15 7 Ďalším prvkom je 11. Zapisuje sa do usporiadanej časti poľa na tretie miesto, pretože 11> 8, ale 11< 13.

5- krok

3 6 8 11 13 1 5 9 15 7 Z rovnakého dôvodu napíšeme 1 na prvé miesto

6 - krok

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

Detská časť je tretia.

7 -krok

1 3 5 6 8 11 13 9 15 7 Miesto čísla 9 je šieste.

8 -krok

1 3 5 6 8 9 11 13 15 7 Určte miesto pre predposledného

Prvok 15. Ukazuje sa, že tento prvok

Policajt je už na svojom mieste.

9 -krok

1 3 5 6 8 9 11 13 15 7 Zostáva nájsť vhodné miesto pre

Posledná položka (7).

1 3 5 6 7 8 9 11 13 15 Pole je zoradené úplne.

Teraz môžeme stručne opísať fragment triediaceho algoritmu metódou priameho zaradenia:

Pre k: = 2 To n Do

(keďže začíname triediť hľadaním vhodného miesta pre a, mení sa i z 2 na n)

„Vložte x na vhodné miesto v a, ..., a [k]“

Zostáva zodpovedať otázku, ako nájsť vhodné miesto pre prvok x. Postupujeme nasledovne: prezrieme si prvky umiestnené naľavo od x (teda tie, ktoré sú už usporiadané), pričom sa presunieme na začiatok poľa. Je potrebné zobraziť prvky a [j], j sa mení od k-1 do 1. Takéto skenovanie sa musí skončiť, keď je splnená jedna z nasledujúcich podmienok:

· Nájdený prvok a [j]< x, что говорит о необходимости вставки x между a и a[j].

· Bol dosiahnutý ľavý koniec usporiadanej časti poľa, preto musíte na prvé miesto vložiť x.

Kým nie je splnená jedna z týchto podmienok, budeme posúvať prezerané prvky na prvú pozíciu doprava, čím sa uvoľní miesto v triedenej časti pre x.

Program priameho triedenia:

program n3; (Zoradiť zostupne)

typ ar = pole integer;

triedenie procedúr3 (var a: ar);

var i, j, x, k: celé číslo;

pre k: = 2 až n do

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

zatiaľ čo (j> 0) a (x> = a [j]) áno

writeln ("Zadajte pôvodné pole:");

pre i: = 1 až n čítaj (a [i]);

writeln ("Triedené pole:");

pre i: = 1 až n napíšte (a [i], "");

Táto metóda je široko používaná pri hraní kariet. Prvky (karty) sú mentálne rozdelené na už „pripravenú“ sekvenciu A 1, A 2, ..., A i -1 a na „zostávajúcu“ (nezoradenú) časť: A i, A i +1,…, A N.

Podstatou metódy je, že pri každom i-tom kroku (začínajúc i = 2) sa i-tý prvok vytiahne z nevytriedenej časti a umiestni sa do „hotovej“ časti, pričom sa vloží na požadované miesto.

Textový algoritmus metódy:

1. Začiatok.

2. Slučka, zatiaľ čo i má hodnoty od 2 do N,
krok = 1:

a) umiestnite i-tý prvok (A (i)) do bunky A (0);

b) priraďte j = -1, to znamená, že j sa rovná číslu prvku umiestneného naľavo od subjektu (i-tý) a teda stojaceho v poradí „pripravený“;

c) ak А (0) ≥ А (j), potom prvok А (0) by mal byť umiestnený v bunke А (j + 1), inak by mal byť prvok А (j) umiestnený v bunke А (j + 1) , znížte hodnotu j o jeden a znova vykonajte bod c).

Na obr. 1 je znázornená bloková schéma triedenia metódou priameho zaradenia.

Metóda funguje nasledovne: v i-tom kroku (začínajúc od i = 2) sa i-tý prvok umiestni do voľnej bunky (napríklad A (0)). Tento prvok sa porovnáva s prvkom naľavo od neho v „hotovej“ časti. Ak je prvok A (0) menší, potom sa porovnávaný (j-tý prvok) posunie doprava o jednu pozíciu, po ktorej sa na porovnanie vezme ďalší prvok. Ak sa ukáže, že prvok A (0) nie je menší ako porovnanie, umiestni sa na miesto bezprostredne za porovnávaným prvkom.

Ryža. 1. Bloková schéma triedenia metódou priameho zaradenia

Na obr. 2 je znázornený príklad uskutočnenia triedenia metódou priameho zaradenia.

Pôvodná sekvencia
	A (0)
ja = 2
ja = 3
ja = 4
ja = 5
ja = 6
ja = 7
ja = 8
Výsledok

Ryža. 2. Príklad triedenia metódou priameho zaradenia

Priame triedenie je vhodnejšie v prípade, keď údaje, ktoré sa majú triediť, prichádzajú postupne (jeden po druhom).

Triedenie metódou priameho výberu

Podstata metódy je nasledovná. Vyberie sa najmenšia položka v „zostávajúcej“ (netriedenej) časti a zahodí sa s prvou položkou (v tej istej nezoradenej časti). Potom sa dĺžka netriedenej časti skráti o jeden prvok (o prvý) a celý proces pokračuje s (n - 1) prvkami, potom s (n - 2) prvkami atď., až kým nezostane iba jeden. ľavý, najväčší prvok.

Táto metóda je v istom zmysle opakom metódy priamej inklúzie. Pri metóde priameho zaradenia sa v každom kroku berie do úvahy iba jeden ďalší prvok a všetky prvky už "pripravenej" časti sekvencie, medzi ktorými sa nachádza bod zaradenia tohto ďalšieho prvku. A pri metóde priameho výberu na nájdenie jedného (minimálneho) prvku sa naskenujú všetky prvky nevytriedenej časti a tento minimálny prvok sa umiestni ako ďalší prvok do už „pripravenej“ časti.

Textový algoritmus metódy:

1. Začiatok.

2. Slučka, zatiaľ čo i má hodnoty od 1 do N - 1,
krok = 1:

a) vložte aktuálny (i-tý) prvok do nejakej pamäťovej bunky (X) a zapamätajte si poradové číslo (i) aktuálneho prvku (v premennej K);

b) vykonajte cyklus, zatiaľ čo j má hodnoty od i + 1 (to znamená od nasledujúceho prvku po i) do N, krok = +1:

telo cyklu: ak X> A (j), tak prvok A (j) vložíme do bunky X a zapamätáme si jeho číslo v bunke K;

c) priraďte A (K) = A (i) a A (i) = X.

Na obr. 3 je znázornený príklad uskutočnenia triedenia metódou priameho výberu.

Pôvodná sekvencia	44						06
ja = 1		55	12
ja = 2			55			18
ja = 3				42		55
ja = 4					94		44
ja = 5						55	94
ja = 6							94	67
ja = 7

Ryža. 3. Príklad triedenia metódou priameho výberu