Řazení vkládáním (insertion sort)

Podcast

Řadicí algoritmy: Od karet po kód0:00 / 11:16

0:001:00 zbývá

1x

Řazení vkládáním, známé pod anglickým názvem Insertion Sort, je jedním z nejzákladnějších a nejintuitivnějších řadicích algoritmů. Jeho princip je snadno pochopitelný a často se přirovnává k tomu, jak lidé přirozeně ř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.

Co je to řazení vkládáním (Insertion Sort) a jak funguje?

Řazení vkládáním je metoda uspořádání prvků, která postupně prochází neseřazenou částí pole a vkládá každý prvek na správné místo do již seřazené části. Funguje na principu postupné výstavby seřazeného seznamu, vždy po jednom prvku.

Základní princip algoritmu Insertion Sort

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. 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.

Kroky algoritmu řazení vkládáním

1. 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íč“.
2. Porovnáváme „klíč“ s prvky v seřazené části pole, které jsou nalevo od něj.
3. Pokud je prvek v seřazené části větší než „klíč“, posuneme ho o jednu pozici doprava.
4. Tento posun opakujeme, dokud nenarazíme na prvek, který je menší nebo roven „klíči“, nebo dokud nedosáhneme začátku pole.
5. Na uvolněné místo vložíme „klíč“.
6. Pokračujeme s dalším prvkem v neseřazené části, dokud nejsou všechny prvky vloženy do seřazené části.

Příklad řazení vkládáním krok za krokem

Podívejme se na konkrétní příklad řazení vkládáním pro 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 s 4. Jelikož 3 < 4, posuneme 4 doprava.
• Pole: [1, 2, _, 4, 5, 6]
• Porovnáme 3 s 2. Jelikož 3 > 2, 2 zůstane na místě.
• Vložíme 3 na uvolněné místo.
• Pole po vložení: [1, 2, 3, 4, 5, 6]

Pole je nyní seřazeno.

Složitost algoritmu řazení vkládáním

Pro pochopení výkonu Insertion Sort je klíčové znát jeho časovou a prostorovou složitost.

Časová složitost Insertion Sort

Časová složitost algoritmu popisuje, jak se doba běhu algoritmu mění s velikostí vstupních dat (n). Pro řazení vkládáním rozlišujeme tři případy:

• Nejlepší případ (Best Case): Nastává, když je vstupní pole již seřazené. V tomto případě algoritmus pro každý prvek provede pouze jedno porovnání (s posledním prvkem seřazené části) a žádné posuny. Celková časová složitost je lineární, tedy O(n). Například pro pole [1, 2, 3, 4, 5] algoritmus pouze ověří, že každý prvek je větší než ten předchozí, a nemusí provádět žádné posuny.
• Nejhorší případ (Worst Case): Nastává, když je vstupní pole seřazeno v opačném pořadí (sestupně pro vzestupné řazení). V tomto případě musí být každý prvek porovnán se všemi prvky v seřazené části a všechny tyto prvky musí být posunuty. Pro n prvků to znamená přibližně n porovnání a n posunů pro každý z n prvků. Celková časová složitost je kvadratická, tedy O(n²). Například pro pole [5, 4, 3, 2, 1] vyžaduje vkládání každého prvku posunutí všech předchozích prvků.
• Průměrný případ (Average Case): Pro náhodně uspořádané pole je průměrná časová složitost také O(n²). I když se nejedná o nejhorší scénář, počet porovnání a posunů roste kvadraticky s velikostí vstupu.

Prostorová složitost Insertion Sort

Řazení vkládáním je algoritmus řazení na místě (in-place), což znamená, že k řazení nepotřebuje žádný dodatečný paměťový prostor, kromě několika proměnných pro uložení klíče a indexů. Jeho prostorová složitost je proto konstantní, O(1).

Stabilita algoritmu Insertion Sort

Stabilita řadicího algoritmu znamená, že pokud existují dva prvky se stejnou hodnotou, jejich relativní pořadí ve výstupním seřazeném poli zůstane stejné jako v původním vstupním poli. Řazení vkládáním je stabilní algoritmus. Důvodem je, že při vkládání klíče do seřazené části se posouvají prvky pouze tehdy, když jsou větší než klíč. Pokud je prvek v seřazené části roven klíči, posun se neprovádí a klíč je vložen za tento roven prvek, čímž se zachová původní pořadí prvků se stejnou hodnotou.

Pseudokód řazení vkládáním (Insertion Sort)

Zde je jednoduchý pseudokód, který ilustruje logiku algoritmu:

PROCEDURA InsertionSort(pole A, délka n)
 PRO i OD 1 DO n-1 KROK 1
 klíč = A[i]
 j = i - 1
 ZATÍMCO j >= 0 A A[j] > klíč
 A[j + 1] = A[j]
 j = j - 1
 KONEC ZATÍMCO
 A[j + 1] = klíč
 KONEC PRO
KONEC PROCEDURY

Výhody a nevýhody řazení vkládáním

Každý algoritmus má své silné a slabé stránky. U řazení vkládáním to platí také.

Výhody Insertion Sort

• Jednoduchost: Algoritmus je snadno pochopitelný a implementovatelný, což je skvělé pro studenty.
• Efektivita pro malé sady dat: Pro pole s malým počtem prvků (např. méně než 10-20) je často rychlejší než složitější algoritmy s lepší asymptotickou složitostí, kvůli nižší režii.
• Efektivita pro téměř seřazené sady dat: Pokud je pole již téměř seřazené, řazení vkládáním pracuje velmi efektivně, s časovou složitostí blížící se O(n). To je mýlná představa, že řazení vkládáním je vždy pomalé. V některých případech může být dokonce součástí hybridních řadicích algoritmů (např. Timsort, Introsort), kde se používá pro řazení malých podpolí.
• Na místě (In-place): Nevyžaduje žádnou dodatečnou paměť (O(1)), což šetří zdroje.
• Stabilní: Zachovává relativní pořadí prvků se stejnou hodnotou.

Nevýhody Insertion Sort

• Neefektivní pro velké, neseřazené sady dat: Kvadratická časová složitost O(n²) jej činí nepraktickým pro řazení velkých polí, kde by byly preferovány algoritmy jako QuickSort nebo MergeSort s O(n log n) složitostí.

Běžné chyby a mylné představy o řazení vkládáním

Jednou z častých chyb je záměna řazení vkládáním s řazením výběrem (Selection Sort) nebo bublinkovým řazením (Bubble Sort). Zatímco všechny mají kvadratickou složitost O(n²), jejich mechanismy se liší. Řazení vkládáním aktivně vkládá prvek do již seřazené části, zatímco řazení výběrem hledá nejmenší prvek a přesouvá ho na správnou pozici, a bublinkové řazení opakovaně prochází seznamem a vyměňuje sousední prvky, které jsou ve špatném pořadí. Další chybou může být nesprávné ošetření hranic pole při posouvání prvků, což může vést k chybám indexování.

Interaktivní simulace řazení vkládáním

Interaktivní simulace řazení vkládáním umožňuje studentům vizualizovat a pochopit mechanismus algoritmu krok za krokem. Studenti mohou pozorovat následující aspekty, které jim pomohou s lepším pochopením:

• Krokování vkládání klíče: Simulace názorně ukazuje, jak je každý prvek (klíč) vybrán z neseřazené části a postupně porovnáván s prvky v již seřazené části. Lze sledovat, jak se prvky v seřazené části posouvají doprava, aby se uvolnilo místo pro klíč.
• Růst seřazené části: Studenti uvidí, jak se seřazená část pole postupně rozšiřuje zleva doprava, dokud není celé pole seřazeno.
• Počet porovnání a posunů: Simulace často zobrazuje počítadla porovnání a posunů, což pomáhá pochopit, proč je časová složitost O(n²) v nejhorším případě a O(n) v nejlepším případě. Pro seřazené pole uvidíte minimální počet operací, zatímco pro obráceně seřazené pole bude počet operací maximální.
• Vliv počátečního stavu pole: Studenti mohou experimentovat s různými počátečními stavy pole (náhodné, seřazené, obráceně seřazené, téměř seřazené) a pozorovat, jak se mění rychlost a počet kroků potřebných k dokončení řazení. To pomáhá upevnit pochopení konceptů nejlepšího a nejhoršího případu.
• Stabilita: Pokud simulace používá prvky s duplicitními hodnotami, lze vizuálně ověřit, že řazení vkládáním zachovává jejich původní relativní pořadí.

Cílem simulace je umožnit studentům aktivně se zapojit do procesu učení, vizuálně si představit abstraktní koncepty algoritmů a lépe pochopit, jak a proč se řazení vkládáním chová za různých podmínek.

Často kladené otázky (FAQ) o řazení vkládáním

Kdy je vhodné použít řazení vkládáním?

Řazení vkládáním je ideální pro malé datové sady nebo pro sady dat, které jsou již téměř seřazené. Díky své jednoduchosti a nízké režii je v těchto případech často efektivnější než složitější algoritmy.

Je řazení vkládáním stabilní algoritmus?

Ano, řazení vkládáním je stabilní algoritmus. To znamená, že zachovává relativní pořadí prvků, které mají stejnou hodnotu, což je důležitá vlastnost pro některé aplikace.

Jaká je časová složitost řazení vkládáním v nejhorším případě?

V nejhorším případě, například pro obráceně seřazené pole, má řazení vkládáním časovou složitost O(n²). To z něj činí nevhodný algoritmus pro velké, náhodně uspořádané datové sady.

Jak se liší řazení vkládáním od bublinkového řazení nebo řazení výběrem?

Všechny tři algoritmy mají kvadratickou složitost O(n²), ale liší se mechanismem. Řazení vkládáním vkládá prvky do seřazené části, bublinkové řazení opakovaně porovnává a prohazuje sousední prvky, a řazení výběrem opakovaně nachází minimum a umisťuje ho na správné místo.