Insertion sort – triedenie vkladaním v Java
Triediace algoritmy sa používajú na vzostupné alebo zostupné preusporiadanie prvkov poľa alebo zoznamu podľa numerického alebo lexikografického poradia. Triedenie je veľmi dôležité pre optimálny výkon iných algoritmov, ktoré vyžadujú triedené vstupné dáta.
V článku sa dozvieš:
Existuje množstvo rozličných triediacich algoritmov. Výber vhodného algoritmu závisí na faktoroch ako veľkosť a vlastnosti vstupných dát, dostupná pamäť a požiadavky na časovú a priestorovú náročnosť.
Aby sme ti uľahčili výber, predstavíme si v našom seriáli postupne najznámejšie algoritmy triedenia dát, vysvetlíme si ich princípy, výhody a nevýhody a naprogramujeme si ich v Jave.
Doteraz sme sa venovali nasledujúcim triediacim algoritmom:
- Triediace algoritmy: úvod do triedenia dát,
- Bubble sort – bublinkové triedenie,
- Comb sort – hrebeňové triedenie,
- Big O notácia: analýza zložitosti algoritmov,
- Selection sort – triedenie výberom.
Dnes sa budeme venovať triedeniu vkladaním (angl. insertion sort).
Insertion sort
Insertion Sort je jednoduchý a intuitívny algoritmus na triedenie poľa alebo zoznamu prvkov. Funguje podobne ako metóda, ktorou si ľudia triedia hracie karty na ruke. Svoje obdržané karty si udržiavajú zotriedené a každú novú kartu, ktorú dostanú si vložia na miesto, aby zachovávala svoje relatívne poradie.
Insertion sort vs selection, quick, merge sort
Insertion Sort sa často používa ako súčasť komplexnejších triediacich algoritmov (napríklad pri malých podmnožinách v Quick Sorte alebo Merge Sorte), pretože jeho výkon je pre malé množiny údajov dobrý. V porovnaní so Selection Sort, ktorý sme rozoberali minule, ponúka stabilný algoritmus.
Insertion sort algoritmus – princíp fungovania
Algoritmus začína rozdelením vstupného vektora na zotriedenú a nezotriedenú časť. Prvý prvok poľa sa automaticky považuje za zotriedený a zvyšné prvky sa ešte musia zotriediť. Pre každý prvok v netriedenej časti (od druhého po posledný prvok poľa) sa tento prvok vyberie a vloží na správne miesto v triedenej časti poľa tak, aby bola triedená časť stále usporiadaná. Tento krok zahŕňa porovnávanie vybraného prvku s ostatnými prvkami v zotriedenej časti a popresúvanie prvkov, aby sa uvoľnilo miesto pre vybraný prvok. Presúvaniu sa dá vyhnúť, ak si zvolíme dátový typ zoznam miesto poľa.
Praktický príklad si potom ukážeme v Java kóde.
Výhody algoritmu Insertion sort
- Ľahký na pochopenie aj implementáciu,
- efektívny pre malé množiny údajov alebo takmer usporiadané poľa,
- vhodný pre prichádzajúce prvky, ktoré musia byť priebežne triedené,
- nevyžaduje dodatočnú pamäť pri triedení,
- stabilný.
Nevýhoda algoritmu Insertion sort
- Časová náročnosť je však stále O(n²), čo z neho robí pomalý algoritmus pre veľkú sadu dát.
Insertion sort časová náročnosť
| Algoritmus | Metóda | Časová náročnosť | Pamäť | Stabilný | ||
| najhoršia | priemer | najlepšia | ||||
| Insertion sort | vkladanie | O(n²) | O(n²) | n | O(1) | áno |
Insertion sort animácie, vizualizácia, gif
Vizualizácia Insertion sort vyzerá nasledovne:
Zdroj: commons.wikimedia.org/wiki/Category:Animations_of_sort_algorithms
Animáciu algoritmu nájdeš napríklad na stránke Toptal. Nachádza sa tam 8 typov algoritmov, animáciu si môžeš pustiť aj pozadu.
Na tejto stránke si môžeš prejsť jednotlivými krokmi algoritmu, vďaka čomu si vieš overiť časovú náročnosť algoritmu.
Insertion sort implementácia, Java kód
Teraz si ukážeme jednoduchú implementáciu algoritmu Insertion sort v Jave.
InsertionSort.java
package sorting;
public class InsertionSort {
private int key, j;
public void sort(int data[])
{
// Start with 2nd element, as 1st is considered to be sorted
for (int i = 1; i < data.length - 1; i++) {
System.out.println(i + ". iteration (key = " + data[i] + ")");
// Element that needs to be inserted into sorted part
key = data[i];
j = i - 1;
// Move all elements > key one position to the right
while (j >= 0 && key < data[j]) {
data[j + 1] = data[j];
j--;
}
// Insert the key in its correct spot
data[j + 1] = key;
printArray(data);
}
}
// Function to print an array
public void printArray(int data[])
{
for (int i = 0; i < data.length; i++)
System.out.print(data[i] + " ");
System.out.println();
}
}
Main.java
import sorting.InsertionSort;
public class Main {
public static void main(String[] args) {
int dataToSort[] = { 6, 5, 4, 2, 3, 1, 7 };
InsertionSort insertionSort = new InsertionSort();
System.out.print("Input: ");
insertionSort.printArray(dataToSort);
insertionSort.sort(dataToSort);
System.out.print("Sorted: ");
insertionSort.printArray(dataToSort);
}
}Výstup z tohto príkladu je:
Pripravili sme pre teba súbory so spomínaným príkladom vo forme kódu, ktorý si môžeš spustiť priamo v Jave. Stiahni si Java Insertion Sort kód.
Ak si Java programátor a hľadáš prácu, pozri si naše benefity pre zamestnancov a reaguj na najnovšie ponuky práce.
