insertion sort c with examples
Hloubkový pohled na třídění vložení s klasickými příklady.
Insertion sort je technika třídění, na kterou lze pohlížet tak, že hrajeme karty po ruce. Způsob, jakým vložíme jakoukoli kartu do balíčku nebo ji odstraníme, funguje podobně.
Technika algoritmu třídění vkládání je efektivnější než techniky třídění Bubble a Selection, ale je méně účinná než ostatní techniky, jako je Quicksort a Merge sort.
=> Podívejte se na nejlepší výukové kurzy C ++ zde.
Co se naučíte:
- Přehled
- Obecný algoritmus
- Pseudo kód
- Ilustrace
- Příklad C ++
- Příklad Java
- Analýza složitosti algoritmu řazení
- Závěr
- Doporučené čtení
Přehled
V technice třídění vkládání začneme od druhého prvku a porovnáme ho s prvním prvkem a umístíme jej na správné místo. Poté provedeme tento proces pro následující prvky.
Porovnáme každý prvek se všemi jeho předchozími prvky a umístíme nebo vložíme prvek do správné polohy. Technika třídění vkládání je proveditelnější pro pole s menším počtem prvků. Je také užitečné pro třídění propojených seznamů.
jak otevřít soubory SWF pomocí Adobe Flash Player
Propojené seznamy mají ukazatel na další prvek (v případě jednotlivě propojeného seznamu) a také ukazatel na předchozí prvek (v případě dvojnásobně propojeného seznamu). Proto je snazší implementovat třídění vložení pro propojený seznam.
Pojďme prozkoumat vše o třídění vložení v tomto kurzu.
Obecný algoritmus
Krok 1 : Opakujte kroky 2 až 5 pro K = 1 až N-1
Krok 2 : nastavená teplota = A (K)
Krok 3 : nastavení J = K - 1
Krok 4 : Opakujte při teplotě<=A(J)
množina A (J + 1) = A (J)
množina J = J - 1
(konec vnitřní smyčky)
Krok 5 : set A (J + 1) = tepl
(konec smyčky)
Krok 6 : výstup
V technice třídění vkládání tedy vycházíme z druhého prvku, protože předpokládáme, že první prvek je vždy seřazen. Potom od druhého prvku k poslednímu prvku porovnáme každý prvek se všemi jeho předchozími prvky a dáme tento prvek do správné polohy.
Pseudo kód
Níže je uveden pseudo kód pro třídění vložení.
procedure insertionSort(array,N ) array – array to be sorted N- number of elements begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array(i) freePosition = i //locate free position to insert the element whilefreePosition> 0 and array(freePosition -1) >insert_val do: array (freePosition) = array (freePosition -1) freePosition = freePosition -1 end while //insert the number at free position array (freePosition) = insert_val end for end procedureVzhledem k výše uvedenému je pseudokód pro třídění Insertion, dále tuto techniku ilustrujeme v následujícím příkladu.
Ilustrace
Pole, které se má třídit, je následující:
Nyní pro každý průchod porovnáme aktuální prvek se všemi jeho předchozími prvky. Takže v prvním průchodu začneme s druhým prvkem.
Proto potřebujeme N počet průchodů, abychom kompletně roztřídili pole obsahující N počet prvků.
Výše uvedený obrázek lze shrnout do tabulky:
jaký je rozdíl mezi linuxem a unixem
| Složit | Nezařazený seznam | srovnání | Seřazený seznam |
|---|---|---|---|
| 1 | {12,3,5,10,8,1} | {12.3} | {3,12,5,10,8,1} |
| dva | {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čneme s 2ndprvek, 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 vyměníme polohu, pokud je druhý prvek menší než první.
Toto srovnání a proces výměny umístí dva prvky na správná místa. Dále porovnáme třetí prvek s jeho předchozími (první a druhý) prvky a provedeme stejný postup, abychom umístili třetí prvek na správné místo.
Tímto způsobem pro každý průchod 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, abychom umístili N prvků na jejich správné místo, potřebujeme průchody N-1.
Dále si ukážeme implementaci techniky třídění Insertion v jazyce C ++.
Příklad C ++
#include using namespace std; int main () { int myarray(10) = { 12,4,3,1,15,45,33,21,10,2}; cout<<'
Input list is
'; for(int i=0;i<10;i++) { cout < Výstup:
Seznam vstupů je
12 4 3 1 15 45 33 21 10 2
Řazený seznam je
1 2 3 4 10 12 15 21 33 45
Dále uvidíme implementaci Javy techniky třídění Insertion.
Příklad 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('Input list of elements ...'); 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('
sorted list of elements ...'); for(int i=0;i<10;i++) { System.out.print(myarray(i) + ' '); } } } Výstup:
Vstupní seznam prvků…
12 4 3 1 15 45 33 21 10 2
seřazený seznam prvků…
1 2 3 4 10 12 15 21 33 45
V obou implementacích vidíme, že začneme třídění od 2ndprvek pole (proměnná smyčky j = 1) a opakovaně porovnávat aktuální prvek se všemi jeho předchozími prvky a poté prvek seřadit tak, aby jej umístil do správné polohy, pokud aktuální prvek není v pořádku se všemi jeho předchozími prvky.
Třídění vložení funguje nejlépe a lze ho dokončit v méně průchodech, pokud je pole částečně tříděno. Ale jak se seznam zvětšuje, jeho výkon klesá. Další výhodou třídění vložení je, že se jedná o stabilní řazení, což znamená, že udržuje pořadí stejných prvků v seznamu.
Analýza složitosti algoritmu řazení
Z pseudokódu a výše uvedeného obrázku je třídění vložení efektivní algoritmus ve srovnání s tříděním podle bublin nebo výběrem. Místo použití pro smyčku a současné podmínky používá smyčku while, která při třídění pole neprovádí žádné další kroky.
I když však předáme seřazené pole do techniky třídění vložení, bude stále vykonávat vnější smyčku for, což vyžaduje n počet kroků k seřazení již seřazeného pole. Díky tomu je nejlepší časová složitost vkládání řadit lineární funkcí N, kde N je počet prvků v poli.
Níže jsou uvedeny různé složitosti techniky třídění vložení:
Nejhorší časová složitost O (n 2) Nejlepší časová složitost Na) Průměrná časová složitost O (n 2) Složitost prostoru O (1)
I přes tyto složitosti můžeme stále dojít k závěru, že řazení Insertion je nejúčinnějším algoritmem ve srovnání s jinými technikami třídění, jako je Bubble sort a Selection sort.
Závěr
Třídění vložení je nejúčinnější ze všech tří dosud diskutovaných technik. Zde předpokládáme, že první prvek je seřazen a poté opakovaně porovnáváme každý prvek se všemi jeho předchozími prvky a poté umístíme aktuální prvek do správné polohy v poli.
V tomto tutoriálu jsme si při diskusi o řazení vložení všimli, že porovnáváme prvky pomocí přírůstku 1 a také jsou souvislé. Výsledkem této funkce je získání více průchodů k získání seřazeného seznamu.
V našem nadcházejícím tutoriálu budeme diskutovat o „Shell sort“, což je zlepšení oproti Selection sort.
V prostředí shellu zavedeme proměnnou známou jako „přírůstek“ nebo „mezera“, pomocí které rozdělíme seznam na podseznamy obsahující nesouvislé prvky, které od sebe „oddělují“. Třídění prostředí vyžaduje ve srovnání s vložením řazení méně průchodů a je také rychlejší.
jaký je nejlepší stahovač hudby mp3
V našich budoucích tutoriálech se dozvíme o dvou technikách třídění, „Quicksort“ a „Mergesort“, které pro třídění seznamů dat používají strategii „Rozděl a panuj“.
=> Zde si všimněte výcvikového průvodce pro začátečníky v C ++.
Doporučené čtení