Selection sort – triedenie výberom 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.

Dnes sa budeme venovať triedeniu výberom (angl. selection sort).

Selection sort algoritmus

Triedenie výberom je jednoduchý algoritmus triedenia dát, ktorý rozdeľuje vstupné pole na dve časti: na zotriedenú a na nezotriedenú. Potom opakovane vyberá najmenší (najväčší) element z nezotriedenej časti a presunie do zotriedenej. Algoritmus je veľmi neefektívny pre veľké množstvo prvkov na vstupe, avšak používa sa často v situáciách keď je prvkov na vstupe pomerne málo a to najčastejšie v kombináciách s inými algoritmami triedenia.

Princíp fungovania algoritmu Selection sort

Predpokladajme, že chceme zotriediť vstupné vektor od najmenšieho po najväčší element. Pre opačné zotriedenie sa celá logika algoritmu prevráti. Zotriedená časť poľa je na začiatku algoritmu vždy prázdna.

1. Na začiatku algoritmu predpokladáme, že prvý element (nezotriedenej časti) je minimum (teda najmenší).
2. Porovnáme tento prvok zo zvyšnými prvkami v nezotriedenej časti poľa a hľadáme naozajstný najmenší prvok.
3. Ak sme našli v nezotriedenej časti menší prvok, tak vymeníme prvky.
4. Vymenený prvok sa stáva súčasťou zotriedenej množiny dát, jej index sa zväčší o 1 a nezotriedená časť sa zmenší.
5. Opakujeme kroky 1 až 4, až kým sa celé pole nezotriedi.

Praktický príklad si potom ukážeme v Java kóde.

Výhody algoritmu Selection sort

• Je ľahký na pochopenie aj implementáciu,
• funguje dobre pre malé zoznamy dát.

Nevýhody algoritmu Selection sort

• Časová náročnosť je O(n²), čo z neho robí pomalý algoritmus pre veľkú sadu dát,
• nie je stabilný.

Selection sort časová náročnosť

Selection sort animácie, vizualizácia, gif

Vizualizácia Selection sort algoritmu 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.

Implementácia Selection Sort  – Java program

Po zoznámení sa s princípmi fungovania algoritmu si ho teraz môžeme naprogramovať v Jave.

SelectionSort.java

package sorting;

public class SelectionSort {
    private boolean change;
    private int temp;

    public void sort(int data[])
    {
        for (int i = 0; i < data.length - 1; i++) {
            System.out.println(i + 1 + ". iteration");
            // Find the index of the minimum in unsorted part of array
            int minIndex = i;
            for (int j = i + 1; j < data.length; j++) {
                if (data[j] < data[minIndex])
                    minIndex = j;
            }

            // Swap the minimum element with first element from unsorted part, unless they are the same
            if(i != minIndex) {
                System.out.print("Found minimum: " + data[minIndex] + ", swapping with " + data[i] + " => ");
                temp = data[minIndex];
                data[minIndex] = data[i];
                data[i] = temp;
            }
            else
                System.out.print("Minimum: " + data[minIndex] + " is on the right spot, no swapping => ");
            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.SelectionSort;

public class Main {
    public static void main(String[] args) {
        int dataToSort[] = { 6, 5, 4, 2, 3, 1, 7 };
        SelectionSort selectionSort = new SelectionSort();
        System.out.print("Input: ");
        selectionSort.printArray(dataToSort);
        selectionSort.sort(dataToSort);
        System.out.print("Sorted: ");
        selectionSort.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 SelectionSort Java 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.