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.

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ť

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.

O autorovi

Jozef Wagner

Java Developer Senior

Viac ako 10 rokov programujem v Jave, momentálne pracujem v msg life Slovakia ako Java programátor senior a pomáham zákazníkom implementovať ich požiadavky do poistného softvéru Life Factory. Vo voľnom čase si rád oddýchnem v lese, prípadne si zahrám nejakú dobrú počítačovú hru.