Java programátor expert
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.
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.
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.
- Na začiatku algoritmu predpokladáme, že prvý element (nezotriedenej časti) je minimum (teda najmenší).
- Porovnáme tento prvok zo zvyšnými prvkami v nezotriedenej časti poľa a hľadáme naozajstný najmenší prvok.
- Ak sme našli v nezotriedenej časti menší prvok, tak vymeníme prvky.
- Vymenený prvok sa stáva súčasťou zotriedenej množiny dát, jej index sa zväčší o 1 a nezotriedená časť sa zmenší.
- 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ť
| Algoritmus | Metóda | Časová náročnosť | Pamäť | Stabilný | ||
| najhoršia | priemer | najlepšia | ||||
| Selection sort | výber | O(n²) | O(n²) | O(n²) | O(1) | nie |
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.
