Gruntle Software & Testing

Vložení třídění v C++ s příklady

Od Stewart TristianZveřejněno Zveřejněno v Průvodci

Podrobný pohled na třídění vkládání s klasickými příklady.

Vkládací třídění je technika třídění, na kterou lze nahlížet způsobem, jakým hrajeme karty v ruce. Stejně jako vkládáme libovolnou kartu do balíčku nebo ji odebíráme, funguje vkládací třídění podobným způsobem.

Technika algoritmu Insertion sort je efektivnější než techniky Bubble sort a Selection sort, ale je méně efektivní než ostatní techniky, jako je Quicksort a Merge sort.

Přehled

Při technice třídění vkládáním začínáme od druhého prvku, porovnáme ho s prvním prvkem a umístíme ho na správné místo. Tento postup pak provedeme pro následující prvky.

Každý prvek porovnáme se všemi předchozími prvky a prvek umístíme nebo vložíme na správné místo. Technika třídění vložením je schůdnější pro pole s menším počtem prvků. Je také užitečná pro třídění spojovaných seznamů.

Propojené seznamy mají ukazatel na další prvek (v případě jednosvazkového seznamu) a ukazatel na předchozí prvek (v případě dvojsvazkového seznamu). Proto je pro propojený seznam snazší implementovat třídění vkládáním.

Prozkoumejme v tomto tutoriálu vše o třídění vkládání.

Obecný algoritmus

Krok 1 : Opakujte kroky 2 až 5 pro K = 1 až N-1.

Krok 2 : set temp = A[K]

Krok 3 : množina J = K - 1

Krok 4 : Repeat while temp <=A[J]

nastavit A[J + 1] = A[J]

nastavte J = J - 1

[konec vnitřní smyčky]

Krok 5 : set A[J + 1] = temp

[konec smyčky]

Krok 6 : exit

V technice třídění vkládáním tedy začínáme od druhého prvku, protože předpokládáme, že první prvek je vždy seřazen. Poté od druhého prvku k poslednímu prvku porovnáváme každý prvek se všemi předchozími prvky a tento prvek umístíme na správnou pozici.

Pseudokód

Pseudokód pro třídění vložením je uveden níže. 

 procedura insertionSort(array,N ) array - pole, které se má třídit N- počet prvků begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array[i] freePosition = i //určete volnou pozici pro vložení prvku whilefreePosition> 0 and array[freePosition -1]>insert_val do: array [freePosition] = array [freePosition -1] freePosition = freePosition -1 end while //vložení prvkučíslo na volné pozici pole [freePosition] = insert_val end for end procedure

Výše je uveden pseudokód pro Insertion sort, dále si tuto techniku ukážeme na následujícím příkladu.

Ilustrace

Pole, které se má seřadit, je následující:

Nyní při každém průchodu porovnáváme aktuální prvek se všemi jeho předchozími prvky. V prvním průchodu tedy začínáme druhým prvkem.

K úplnému setřídění pole obsahujícího N prvků tedy potřebujeme N průchodů.

Výše uvedený obrázek lze shrnout do tabulky:

Předat Netříděný seznam porovnání Tříděný seznam
1 {12,3,5,10,8,1} {12,3} {3,12,5,10,8,1}
2 {3,12,5,10,8,1} {3,12,5} {3,5,12,10,8,1}
3 {3,5,12,10,8,1} {3,5,12,10} {3,5,10,12,8,1}
4 {3,5,10,12,8,1} {3,5,10,12,8} {3,5,8,10,12,1}
5 {3,5,8,10,12,1} {3,5,8,10,12,1} {1,3,5,8,10,12}
6 {} {} {1,3,5,8,10,12}

Jak je znázorněno na výše uvedeném obrázku, začínáme 2. prvkem, protože předpokládáme, že první prvek je vždy seřazen. Začneme tedy porovnáním druhého prvku s prvním a prohodíme pozici, pokud je druhý prvek menší než první.

Tímto porovnáním a prohozením umístíme dva prvky na jejich správná místa. Dále porovnáme třetí prvek s jeho předchozími (prvním a druhým) prvky a provedeme stejný postup, abychom třetí prvek umístili na správné místo.

Takto při každém průchodu umístíme jeden prvek na jeho místo. Při prvním průchodu umístíme na jeho místo druhý prvek. Obecně tedy k umístění N prvků na jejich správné místo potřebujeme N-1 průchodů.

Dále si ukážeme implementaci techniky Insertion sort v jazyce C++.

Příklad jazyka C++ 

 #include using namespace std; int main () { int myarray[10] = { 12,4,3,1,15,45,33,21,10,2}; cout<<"\nInput list is \n"; for(int i=0;i<10;i++) { cout < ="" 
 Výstup: 
 Vstupní seznam je 
 12 4 3 1 15 45 33 21 10 2 
 Tříděný seznam je 
 1 2 3 4 10 12 15 21 33 45 
 Dále se podíváme na implementaci techniky Insertion sort v jazyce Java. 
 Příklad jazyka Java 
 public class Main { public static void main(String[] args) { int[] myarray = {12,4,3,1,15,45,33,21,10,2}; System.out.println("Vstupní seznam prvků ..."); for(int i=0;i<10;i++) { System.out.print(myarray[i] + " "); } for(int k=1; k=0 && temp <= myarray[j]) { myarray[j+1] = myarray[j]; j = j-1; } myarray[j+1] = temp; } System.out.println("\tříděný seznam prvků ..."); for(inti=0;i<10;i++) { System.out.print(myarray[i] + " "); } } } 
 Výstup: 
 Vstupní seznam prvků ... 
 12 4 3 1 15 45 33 21 10 2 
 setříděný seznam prvků ... 
 1 2 3 4 10 12 15 21 33 45 
 V obou implementacích vidíme, že začínáme třídit od 2. prvku pole (proměnná cyklu j = 1) a opakovaně porovnáváme aktuální prvek se všemi jeho předchozími prvky a poté prvek seřadíme tak, abychom jej umístili na správnou pozici, pokud aktuální prvek není seřazen se všemi jeho předchozími prvky. 
 Insertion sort funguje nejlépe a lze jej dokončit v menším počtu průchodů, pokud je pole částečně setříděné. S rostoucím seznamem však jeho výkonnost klesá. Další výhodou Insertion sort je, že se jedná o Stabilní třídění, což znamená, že zachovává pořadí stejných prvků v seznamu. 
 Analýza složitosti algoritmu pro řazení vkládáním 
 Z výše uvedeného pseudokódu a obrázku vyplývá, že insertion sort je efektivnější algoritmus ve srovnání s bubble sort nebo selection sort. Místo cyklu for a present conditions používá cyklus while, který neprovádí žádné další kroky navíc, když je pole seřazeno. 
 Nicméně i když technice Insertion sort předáme setříděné pole, stále bude provádět vnější smyčku for, čímž bude vyžadovat n kroků k setřídění již setříděného pole. Díky tomu je nejlepší časová složitost insertion sort lineární funkcí N, kde N je počet prvků v poli. 
 Níže jsou tedy uvedeny různé složitosti pro techniku Insertion sort: 
 Časová složitost v nejhorším případě  O(n 2 ) 
 Časová složitost v nejlepším případě  O(n) 
 Průměrná časová složitost  O(n 2 ) 
 Složitost prostoru  O(1) 
 I přes tyto složitosti můžeme konstatovat, že Insertion sort je nejefektivnějším algoritmem ve srovnání s ostatními třídicími technikami, jako je Bubble sort a Selection sort. 
 Závěr 
 Vložené třídění je nejefektivnější ze všech tří dosud probíraných technik. Zde předpokládáme, že první prvek je setříděn, a pak opakovaně porovnáváme každý prvek se všemi jeho předchozími prvky a následně umístíme aktuální prvek na jeho správnou pozici v poli. 
 V tomto tutoriálu jsme si při probírání třídění vložením všimli, že prvky porovnáváme pomocí přírůstku 1 a také jsou sousední. Tato vlastnost má za následek, že k získání setříděného seznamu je třeba více průchodů. 
 V nadcházejícím tutoriálu se budeme zabývat tříděním "Shell sort", které je vylepšením třídění Selection sort. 
 Při shell sort zavádíme proměnnou známou jako "přírůstek" nebo "mezera", pomocí které rozdělíme seznam na podseznamy obsahující nesousedící prvky, které jsou od sebe "vzdáleny". Shell sort vyžaduje méně průchodů ve srovnání s Insertion sort a je také rychlejší. 
 V dalších lekcích se seznámíme se dvěma technikami třídění, "Quicksort" a "Mergesort", které pro třídění seznamů dat používají strategii "Rozděl a panuj".
Posunout nahoru