Tato metoda je široce používána při hraní karet. Prvky (karty) jsou myšlenkově rozděleny na již „připravenou“ sekvenci A 1 , A 2 ,…, A i -1 a „zbývající“ (neroztříděnou) část: A i , A i +1 ,…, A N .

Podstata metody spočívá v tom, že v každém i-tém kroku (počínaje i = 2) je i-tý prvek odstraněn z netříděné části a umístěn do „připravené“ části, přičemž je vložen do Správné místo.

Textový algoritmus metody:

1. Začátek.

2. Smyčku, dokud i nebude mít hodnoty od 2 do N,
krok = 1:

a) umístěte i-tý prvek (A(i)) do buňky A(0);

b) přiřaďte j = -1, to znamená, že j se rovná číslu prvku umístěného vlevo od předmětu (i-tý) a stojí tedy v pořadí „připraveno“;

c) pokud A(0) ≥ A(j), umístěte prvek A(0) do buňky A(j+1), jinak umístěte prvek A(j) do buňky A(j+1), snižte hodnotu z j o jednu a proveďte krok c znovu.

Na Obr. 1 ukazuje blokové schéma způsobu třídění přímé spojení.

Metoda funguje následovně: v i-tém kroku (počínaje i = 2) se i-tý prvek umístí do volné buňky (například A(0)). Tento prvek je porovnáván s prvkem stojícím v „hotové“ části nalevo od něj. Pokud je prvek A(0) menší, pak se porovnávaný (j-tý prvek) posune doprava o jednu pozici, načež se pro srovnání vezme další prvek. Pokud prvek A(0) není při porovnávání menší, pak se umístí na místo bezprostředně za porovnávaným prvkem.

Rýže. 1. Vývojový diagram třídění metodou přímého zařazení

Na Obr. Obrázek 2 ukazuje příklad provádění třídění pomocí metody přímého zařazení.

Původní sekvence
	A (0)
já = 2
já = 3
já = 4
já = 5
já = 6
já = 7
já = 8
Výsledek

Rýže. 2. Příklad třídění přímého zařazení

Přímé řazení je vhodnější pro případ, kdy setříděná data přicházejí postupně (jeden za druhým).

Třídění přímého výběru

Podstata metody je následující. Nejmenší prvek ve "zbývající" (netříděné) části je vybrán a zaměněn s prvním prvkem (ve stejné neseřazené části). Poté se délka neseřazené části zkrátí o jeden prvek (první) a celý proces pokračuje s (n – 1) prvky, poté s (n – 2) prvky atd., dokud nezůstane pouze jeden. vlevo.největší prvek.

Tato metoda je v některých ohledech opakem metody přímé inkluze. V metodě přímého začlenění je v každém kroku uvažován pouze jeden další prvek a všechny prvky již „připravené“ části sekvence, mezi nimiž je nalezen inkluzní bod tohoto dalšího prvku. A při metodě přímého výběru se pro nalezení jednoho (minimálního) prvku prohlédnou všechny prvky neseřazené části a tento minimální prvek se umístí jako další prvek do již „připravené“ části.

Textový algoritmus metody:

1. Začátek.

2. Smyčku, dokud i nebude mít hodnoty od 1 do N – 1,
krok = 1:

a) umístěte aktuální (i-tý) prvek do nějaké paměťové buňky (X) a zapamatujte si sériové číslo i) aktuální prvek (v proměnné K);

b) proveďte smyčku, zatímco j má hodnoty od i + 1 (tj. od prvku vedle i) do N, krok = +1:

tělo smyčky: pokud X > A(j), pak umístěte prvek A(j) do buňky X a zapamatujte si jeho číslo v buňce K;

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

Na Obr. Obrázek 3 ukazuje příklad provádění třídění metodou přímého výběru.

Rýže. 3. Příklad třídění přímého výběru

Tato metoda je široce používána při hraní karet. Prvky (karty) jsou myšlenkově rozděleny na již „připravenou“ sekvenci A1 ... An a původní sekvenci Ai ... An. V každém kroku, počínaje od i=2 a zvýšením I pokaždé o jednu, vyjmeme z původní sekvence i-tý prvek a přenese se do hotové sekvence, přičemž se vloží na správné místo.

Výše je jako příklad ukázán proces řazení zahrnutím osmi náhodně vybraných čísel: Algoritmus pro toto řazení je následující:

PRO i:=2 DO n DO

zahrnutí x na odpovídající místo mezi a ... a[j];

V reálném procesu hledání vhodného místa je vhodné střídavým porovnáváním a pohybem po sekvenci prosít X, tj. X se porovnat s dalším prvkem aj, a pak buď X vložit na volné místo, nebo aj se posune (přenese) doprava a proces „jde“ doleva. Vezměte prosím na vědomí, že proces prosévání může skončit, pokud je splněna jedna z následujících dvou různých podmínek:

1. Je nalezen prvek aj s klíčem menším než je klíč X.

2. Bylo dosaženo levého konce dokončené sekvence.

Tento typický případ opakujícího se procesu se dvěma podmínkami ukončení nám umožňuje použít dobře známou bariérovou techniku ​​(sentinel). Zde lze snadno aplikovat nastavením bariéry a0 s hodnotou X. (Upozorňujeme, že k tomu je nutné rozšířit rozsah indexu v popisu proměnné a na 0 ... n.)

Analýza metody přímé inkluze. Počet klíčových porovnání (Ci) během i-tého prosévání je nejvýše roven i-1, nejméně 1; Pokud předpokládáme, že všechny permutace n klíčů jsou stejně pravděpodobné, pak průměrný počet srovnání je i/2. Počet přenosů (přiřazení prvků) Mi je roven Ci + 2 (včetně bariéry). Proto celkový počet srovnání a počet převodů jsou následující:

Uložit = (n2 + n - 2)/4,

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

M min = З*(n - 1),

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

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

K minimálním odhadům dochází v případě již uspořádané počáteční sekvence prvků, zatímco k nejhorším odhadům dochází, když jsou zpočátku uspořádány v opačném pořadí. V některých ohledech vykazuje třídění inkluze skutečně přirozené chování. Je zřejmé, že výše uvedený algoritmus popisuje proces stabilního třídění: pořadí prvků se stejnými klíči zůstává nezměněno.

Algoritmus s přímými inkluzemi lze snadno vylepšit, pokud budete věnovat pozornost skutečnosti, že hotová sekvence (a1 ... ai-1, do které je třeba vložit nový prvek, sám je již objednán. Je přirozené spokojit se s binárním vyhledáváním, ve kterém se pokusí porovnat se středem hotové sekvence, a pak proces půlení pokračuje, dokud není nalezen inkluzní bod. Tento modifikovaný třídicí algoritmus se nazývá metoda binárního vkládání.

Třídění je uspořádání dat v paměti pravidelným způsobem podle zvoleného parametru. Pravidelnost je považována za zvýšení (snížení) hodnoty parametru od začátku do konce datového pole.

Při zpracování dat je důležité znát informační pole dat a jejich umístění ve stroji.

Existují interní a externí třídění:

Vnitřní třídění - třídění v paměť s náhodným přístupem;

Externí třídění - třídění v externí paměti.

Pokud tříděné záznamy zabírají velké množství paměti, je jejich přesun drahý. Za účelem jejich snížení se provádí třídění v klíčová tabulka adres, to znamená, že přeuspořádají ukazatele, ale samotné pole se nepohne. Tento - způsob řazení tabulky adres.

Při řazení se mohou objevit stejné klíče. V tomto případě je vhodné po seřazení uspořádat stejné klíče ve stejném pořadí jako ve zdrojovém souboru.Tento - stabilní třídění.

Budeme zvažovat pouze druhy, které nepoužívají další RAM. Takové druhy se nazývají "na stejném místě".

Účinnost třídění lze posuzovat podle několika kritérií:

Čas strávený tříděním;

Množství paměti RAM potřebné pro třídění;

Čas strávený programátorem psaním programu.

Zdůrazněme první kritérium. Lze uvažovat o ekvivalentu času stráveného tříděním počet srovnání A počet pohybů při provádění třídění.

Pořadí počtu srovnání a pohybů při třídění leží uvnitř

od O (n log n) do O (n 2);

O(n) je ideální a nedosažitelný případ.

Rozlišují se následující způsoby řazení:

Přísné (přímé) metody;

Vylepšené metody.

Přísné metody:

Metoda přímé inkluze;

Metoda přímého výběru;

Metoda přímé výměny.

Účinnost přísných metod je přibližně stejná.

Přímé řazení

Prvky jsou mentálně rozděleny na hotovou sekvenci a 1 ,...,a i-1 a původní sekvenci.

V každém kroku, počínaje i = 2 a zvýšením i pokaždé o jednu, se i-tý prvek odstraní z původní sekvence a přenese se do hotové sekvence a vloží se na požadované místo.

Podstata algoritmu je následující:

pro i = 2 až n

X = a(i)

Najdeme místo mezi a(1)…a(i) pro inkluzi x

příště já

Existují dva dopředné algoritmy řazení. První je bez bariéry

Algoritmus přímého řazení bez bariér

pro i = 2 až n

X = a(i)

Pro j = i - 1 dolů na 1

Pokud x< a(j)

Pak a(j + 1) = a(j)

Jinak jdi do L

Endif

Další j

L: a(j + 1) = x

příště já

vrátit se

Nevýhodou výše uvedeného algoritmu je porušení technologie strukturované programování, ve kterém je nežádoucí používat nepodmíněné přechody. Pokud je vnitřní smyčka organizována jako smyčka while, pak je nutné nastavit „bariéru“, bez které při záporných hodnotách klíče dochází ke ztrátě významu a počítač „zamrzne“.

Algoritmus třídění přímého zařazení s bariérou

pro i = 2 až n

X = a(i)

A(0) = x (a(0) - bariéra)

J = i-1

Zatímco x< a(j) do

A(j +1) = a(j)

J = j-1

Na konci

A(j +1) = x

příště já

vrátit se

Efektivita dopředného algoritmu

Počet klíčových srovnání Ci během i-tého prosévání je nejvýše i-1, nejméně 1; Pokud předpokládáme, že všechny permutace N klíčů jsou stejně pravděpodobné, pak průměrný počet srovnání = i/2. Počet převodů Mi=Ci+3 (včetně bariéry). K minimálním odhadům dochází v případě již uspořádané počáteční sekvence prvků, zatímco k nejhorším odhadům dochází, když jsou zpočátku uspořádány v opačném pořadí. V některých ohledech vykazuje třídění inkluze skutečně přirozené chování. Je zřejmé, že výše uvedený algoritmus popisuje proces stabilního třídění: pořadí prvků se stejnými klíči zůstává nezměněno.

Počet srovnání v nejhorším případě, kdy je pole řazeno opačně, C max = n(n - 1)/2, tj. - O (n 2). Počet permutací M max = C max + 3(n-1), tzn. - O (n 2). Pokud je pole již seřazeno, pak je počet srovnání a permutací minimální: C min = n-1; Mmin = = 3 (n-l).

Třídění pomocí přímé výměny (bublinové třídění)

V tato sekce je popsána metoda, kde je charakteristickým rysem procesu výměna míst dvou prvků. Algoritmus přímé výměny uvedený níže je založen na porovnávání a výměně míst pro pár sousední prvky a pokračovat v tomto procesu, dokud nejsou všechny prvky v pořádku.

Opakujeme průchody polem, pokaždé přesuneme nejmenší prvek zbývající sekvence na levý konec pole. Pokud pole považujeme za vertikální spíše než horizontální konstrukce, pak lze prvky interpretovat jako bubliny v kádi s vodou, přičemž hmotnost každého odpovídá jeho klíči. V tomto případě se při každém průchodu jedna bublina zvedne na úroveň odpovídající její hmotnosti (viz obrázek na obrázku níže).

C min = n - 1, řád O(n),

a nejsou tam vůbec žádné pohyby

Srovnávací analýza metod přímého třídění ukazuje, že výměnné „třídění“ ve své klasické podobě je křížencem mezi tříděním pomocí inkluzí a pomocí výběru. Pokud se do něj zavedou výše uvedená vylepšení, pak pro dostatečně uspořádaná pole bublinový druh má dokonce výhodu.

Tato metoda je běžně známá jako bublinové třídění.

Algoritmus metody přímé výměny

pro j = n až i krok -1

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

V našem případě jsme skončili s jednou prázdnou přihrávkou. Abyste prvky znovu neprohlíželi, a proto prováděli srovnání a věnovali tomu čas, můžete zadat zaškrtávací políčko fl, která zůstává na hodnotě Nepravdivé, pokud během dalšího průchodu nedojde k výměně. V níže uvedeném algoritmu jsou doplňky vyznačeny tučně.

fl = pravda

pokud fl = false, pak se vrátí

fl = nepravda

pro j = n až i krok -1

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

fl = pravda

Vylepšením bublinkové metody je třídění na třepačce, kdy se po každém průchodu mění směr ve vnitřní smyčce.

Efektivita algoritmu přímého řazení

Počet srovnání C max = n(n-1)/2, řád O(n 2).

Počet pohybů M max =3C max =3n(n-1)/2, pořadí O(n 2).

Pokud je pole již seřazeno a je použit algoritmus s příznakem, stačí pouze jeden průchod a pak získáme minimální počet porovnání

Přímé řazení zahrnutím, stejně jako jednoduché řazení výběru, se obvykle používá pro pole, která neobsahují duplicitní prvky.

Třídění metodou přímého zařazení, stejně jako všechny výše popsané, se provádí v krocích. V k-tém kroku se uvažuje, že část pole obsahující prvních k-1 prvků je již uspořádaná, tzn.

a ≤ a ≤ ... ≤ a .

Dále musíte vzít k-tý prvek a vybrat pro něj místo v seřazené části pole tak, aby po jeho vložení nebylo porušeno řazení, to znamená, že musíte najít a j (1 ≤ j ≤ k -1) tak, že a [j] ≤ a[ k]< a. Затем вставить элемент а [k] на найденное место.

S každým krokem se seřazená část pole zvětšuje. Chcete-li provést úplné třídění, budete muset provést n-1 kroků.

Podívejme se na tento proces na příkladu. Předpokládejme, že chcete seřadit pole 10 prvků ve vzestupném pořadí pomocí metody přímého zahrnutí

1 - krok

13 6 8 11 3 1 5 9 15 7 Uvažujeme část pole z jednoho prvku

ment (13). Musíte do něj vložit druhý

prvek pole (6) tak, aby byl uspořádán

se zachovalo. Od 6< 13, вставляем

6 na první místo. Seřazená část

pole obsahuje dva prvky (6 13).

3 - krok

6 8 13 11 3 1 5 9 15 7 Další prvek- 11. Zapisuje se do uspořádané části pole na třetím místě, protože 11 > 8, ale 11< 13.

5- krok

3 6 8 11 13 1 5 9 15 7 Ze stejného důvodu píšeme 1 jako první

6 - krok

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

Hotová část je třetí.

7 -krok

1 3 5 6 8 11 13 9 15 7 Místo čísla 9 je šesté.

8 -krok

1 3 5 6 8 9 11 13 15 7 Určení místa pro předposlední

Prvek 15. Ukazuje se, že tento prvek

Pole je již na svém místě.

9 -krok

1 3 5 6 8 9 11 13 15 7 Zbývá jen najít vhodné místo pro

Poslední prvek (7).

1 3 5 6 7 8 9 11 13 15 Pole je kompletně seřazeno.

Nyní můžeme stručně popsat fragment třídícího algoritmu pomocí metody přímého zahrnutí:

Pro k: = 2 To n Do

(protože začínáme třídit hledáním vhodného místa pro a, i se pohybuje od 2 do n)

‚vložte x na vhodné místo v a, ..., a[k]‘

Zbývá odpovědět na otázku, jak najít vhodné místo pro prvek x. Pokračujeme následovně: prohlédneme si prvky umístěné nalevo od x (tedy ty, které jsou již uspořádané) a přesuneme se na začátek pole. Musíte si prohlédnout prvky a[ j], j se pohybuje od k-1 do 1. Tento pohled by měl skončit, když je splněna jedna z následujících podmínek:

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

· byl dosažen levý konec uspořádané části pole, proto musíme na první místo vložit x.

Dokud není jedna z těchto podmínek splněna, posuneme prohlížené prvky na první pozici doprava, čímž se v setříděné části uvolní místo pod x.

Program přímého třídění:

program n3; (Seřadit sestupně)

typ ar=pole celého čísla;

procedura sorting3(var a:ar);

var i,j,x,k:integer;

pro k:=2 až ​​n do

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

zatímco (j>0)a(x>=a[j]) dělají

writeln("Zadejte zdrojové pole:");

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

writeln("Seřazené pole:");

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

Cíl práce Prozkoumejte třídění pole metodou přímého začlenění a vyhodnoťte účinnost tohoto algoritmu.

Obecná informace

Přímé řazení zahrnutím, stejně jako jednoduché řazení výběru, se obvykle používá pro pole, která neobsahují duplicitní prvky. Třídění touto metodou se provádí postupně krok za krokem. Na k-tý krok Předpokládá se, že část pole obsahující prvních k-1 prvků je již uspořádaná, tzn. Dále musíte vzít k-tý prvek a vyberte pro něj místo v seřazené části pole tak, aby po jeho vložení nebylo narušeno řazení, to znamená, že musíte najít takové, že. Poté je třeba vložit prvek a[k] na nalezené místo. S každým krokem se seřazená část pole zvětšuje. Chcete-li provést úplné třídění, budete muset provést n-1 kroků. Zbývá odpovědět na otázku, jak hledat vhodné místo pro prvek x. Pokračujeme následovně: prohlédneme si prvky umístěné nalevo od x (tedy ty, které jsou již uspořádané) a přesuneme se na začátek pole. Musíte procházet prvky a[j], j se mění z k-l na 1. Takové skenování skončí, když je splněna jedna z následujících podmínek: je nalezen prvek a[j] Příklad Stručně si popišme fragment třídícího algoritmu pomocí přímého zahrnutí: Pro k:= 2 až n do begin x:= a[k]; j:= k-1; ( vložte x na vhodné místo v a, ..., a[k] ) ( k tomu zorganizujeme smyčku, která běží while ) ( j > 0 a x

Testovací úkol

Napište program, který vloží poslední prvek pole za první záporný prvek stejného pole.

Možnosti úkolu

POZORNOST!!! Pokud není výslovně uvedeno jinak, jsou vstupní data (počáteční pole) a výstupní data (tříděné pole) tvořena ve tvaru textový soubor obsahující celá čísla! U všech úloh nejprve napište postup pro řazení pole metodou přímého zahrnutí. 1. Je dána řada obsahující n prvků. Seřaďte je vzestupně a zahoďte všechny duplicitní prvky. 2. Definujte módu tato série– význam, který se mezi jeho prvky vyskytuje nejčastěji. 3. Původní datový soubor je posloupnost záznamů skládající se z příjmení, věku a délky služby. Vytiskněte tento seznam: 1) v abecedním pořadí; 2) v pořadí podle rostoucího věku; 3) v pořadí se zvyšující se délkou služby. 4. Napište postup pro řazení v sestupném pořadí. 5. Je dána řada celých čísel. Získejte vše ve vzestupném pořadí různá čísla zahrnuté v této sérii. 6. Je dána řada n různých celých čísel. Získejte různá celá čísla taková, že 7. Daná celá čísla Najít nejvyšší hodnotu v tomto pořadí po odstranění všech členů s hodnotou 8. Přirozeně Čísla jsou výsledky n sportovců v závodě na 100 m měřené v setinách sekundy. Sestavte tým čtyř nejlepších běžců, kteří se zúčastní štafetového závodu 4x100, tj. označte jedno ze čtyř přirozených čísel i, j, k, l takový, že součet má nejmenší význam. 9. Je dáno n nezávislých náhodných bodů se souřadnicemi (xi; yi), rovnoměrně rozmístěných v kružnici o poloměru 1 se středem v počátku. Napište program, který uspořádá body podle rostoucí vzdálenosti od středu. 10. Je dáno n kladných dvouciferných celých čísel. S každým číslem zacházejte jako s dvojicí číslic z intervalu 0–9 a seřaďte je (čísla) ve vzestupném pořadí. 11. Je dáno n bodů na rovině. Najděte (n-1)-spojnici neprotínající uzavřenou křivku procházející všemi těmito body. (Přilehlé segmenty křivky mohou ležet na stejné přímce.) Nápověda. Vezměme krajní levý bod (tedy bod s nejmenší x-ovou souřadnicí) a nakreslíme z něj paprsky do všech ostatních bodů. Nyní seřaďme tyto paprsky zdola nahoru a seřaďme body na jednom paprsku podle vzdálenosti od začátku paprsku (toto se provádí pro všechny paprsky kromě spodního a horního). Křivka opustí vybraný (levý) bod podél spodního paprsku, poté podél všech ostatních paprsků (v popsaném pořadí) a vrátí se podél horního paprsku. 12. Je dáno n bodů na rovině. Sestrojte jejich konvexní trup - minimální konvexní obrazec, který je obsahuje. (Pryžový kroužek natažený přes hřebíky zaražené do desky - jejich vypouklá skořepina.) Instrukce. Pojďme seřadit body. Potom s ohledem na body jeden po druhém sestrojíme konvexní obal z již uvažovaných bodů.