Shrnutí na Řazení vkládáním (insertion sort)
Řazení vkládáním (Insertion Sort): Kompletní průvodce pro studenty
Řazení vkládáním (Insertion Sort)
Řazení vkládáním, známé též pod anglickým názvem Insertion Sort, je jedním z nejjednodušších a nejintuitivnějších řadicích algoritmů. Jeho princip je snadno pochopitelný a často se přirovnává k tomu, jak člověk řadí karty v ruce. Cílem každého řadicího algoritmu je uspořádat prvky v seznamu nebo poli do určitého pořadí, obvykle vzestupného nebo sestupného.
Princip algoritmu
Představte si, že máte v ruce balíček neuspořádaných karet a chcete je seřadit. Vezmete první kartu a považujete ji za již seřazenou (protože je to jediná karta, takže je sama o sobě seřazená). Poté vezmete druhou kartu a porovnáte ji s první. Pokud je menší, vložíte ji před první kartu; pokud je větší, vložíte ji za ni. Nyní máte dvě seřazené karty. Poté vezmete třetí kartu a porovnáte ji s již seřazenými kartami, dokud nenajdete její správné místo, kam ji vložíte. Tento proces opakujete pro všechny zbývající karty, vždy vkládáte aktuální kartu do správné pozice v již seřazené části balíčku.
Algoritmus řazení vkládáním pracuje s polem prvků podobným způsobem. Pole je rozděleno na dvě části: seřazenou a neseřazenou. Na začátku je první prvek pole považován za seřazenou část a zbytek pole tvoří neseřazenou část. Algoritmus postupně prochází neseřazenou částí, bere jeden prvek po druhém a vkládá jej do správné pozice v seřazené části. Aby se vytvořilo místo pro vkládaný prvek, je nutné posunout všechny větší prvky v seřazené části o jednu pozici doprava.
Řazení vkládáním (Insertion Sort) je jednoduchý řadicí algoritmus, který staví konečné seřazené pole (nebo seznam) vždy po jedné položce. Je neefektivní u velkých seznamů, ale efektivní u malých seznamů a téměř seřazených seznamů.
Kroky algoritmu
- Začínáme od druhého prvku pole (index $1$), protože první prvek (index $0$) je považován za již seřazený. Označíme tento prvek jako „klíč“.
- Porovnáváme „klíč“ s prvky v seřazené části pole, které jsou nalevo od něj.
- Pokud je prvek v seřazené části větší než „klíč“, posuneme ho o jednu pozici doprava.
- Tento posun opakujeme, dokud nenarazíme na prvek, který je menší nebo roven „klíči“, nebo dokud nedosáhneme začátku pole.
- Na uvolněné místo vložíme „klíč“.
- Pokračujeme s dalším prvkem v neseřazené části, dokud nejsou všechny prvky vloženy do seřazené části.
Příklad krok za krokem
Uvažujme pole čísel: $[5, 2, 4, 6, 1, 3]$
Krok 1: První prvek je již seřazen.
$[5 | 2, 4, 6, 1, 3]$ (Seřazená část | Neseřazená část)
Krok 2: Zpracování druhého prvku (klíč = $2$).
- Porovnáme $2$ s $5$. Jelikož $2 < 5$, posuneme $5$ doprava.
- Pole se stane: $[_, 5 | 4, 6, 1, 3]$
- Vložíme $2$ na uvolněné místo.
- Pole po vložení: $[2, 5 | 4, 6, 1, 3]$
Krok 3: Zpracování třetího prvku (klíč = $4$).
- Porovnáme $4$ s $5$. Jelikož $4 < 5$, posuneme $5$ doprava.
- Pole se stane: $[2, _, 5 | 6, 1, 3]$
- Porovnáme $4$ s $2$. Jelikož $4 > 2$, $2$ zůstane na místě.
- Vložíme $4$ na uvolněné místo.
- Pole po vložení: $[2, 4, 5 | 6, 1, 3]$
Krok 4: Zpracování čtvrtého prvku (klíč = $6$).
- Porovnáme $6$ s $5$. Jelikož $6 > 5$, $6$ je již na správném místě vzhledem k $5$.
- Pole po vložení: $[2, 4, 5, 6 | 1, 3]$
Krok 5: Zpracování pátého prvku (klíč = $1$).
- Porovnáme $1$ s $6$. Jelikož $1 < 6$, posuneme $6$ doprava.
- Pole: $[2, 4, 5, _, 6 | 3]$
- Porovnáme $1$ s $5$. Jelikož $1 < 5$, posuneme $5$ doprava.
- Pole: $[2, 4, _, 5, 6 | 3]$
- Porovnáme $1$ s $4$. Jelikož $1 < 4$, posuneme $4$ doprava.
- Pole: $[2, _, 4, 5, 6 | 3]$
- Porovnáme $1$ s $2$. Jelikož $1 < 2$, posuneme $2$ doprava.
- Pole: $[_, 2, 4, 5, 6 | 3]$
- Vložíme $1$ na uvolněné místo.
- Pole po vložení: $[1, 2, 4, 5, 6 | 3]$
Krok 6: Zpracování šestého prvku (klíč = $3$).
- Porovnáme $3$ s $6$. Jelikož $3 < 6$, posuneme $6$ doprava.
- Pole: $[1, 2, 4, 5, _, 6]$
- Porovnáme $3$ s $5$. Jelikož $3 < 5$, posuneme $5$ doprava.
- Pole: $[1, 2, 4, _, 5, 6]$
- Porovnáme $3$
Zaregistruj se pro celé shrnutíUž máš účet? Přihlásit se
Řazení vkládáním
Klíčová slova: Řazení vkládáním, Řazení vkládáním a simulace algoritmu
Klíčové pojmy: Insertion Sort je intuitivní algoritmus, podobný řazení karet v ruce., Pole se dělí na seřazenou a neseřazenou část., Algoritmus postupně bere prvky z neseřazené části a vkládá je do správné pozice v seřazené části., Během vkládání se větší prvky v seřazené části posouvají doprava., Nejlepší časová složitost je $\mathrm{O(n)}$ (již seřazené pole)., Nejhorší a průměrná časová složitost je $\mathrm{O(n^2)}$ (obráceně seřazené nebo náhodné pole)., Prostorová složitost je $\mathrm{O(1)}$ (in-place algoritmus)., Insertion Sort je stabilní algoritmus, zachovává relativní pořadí stejných prvků., Je efektivní pro malé datové sady nebo téměř seřazená pole., Nevhodný pro velké, neseřazené datové sady kvůli kvadratické složitosti., Pseudokód pomáhá pochopit implementaci algoritmu., Nezaměňovat s Bubble Sort nebo Selection Sort, přestože mají podobnou složitost.