
Java programátor expert
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:
Dnes sa budeme venovať triedeniu výberom (angl. selection sort).
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.
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.
Praktický príklad si potom ukážeme v Java kóde.
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 |
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.
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.