Selection sort

Selection sort je jedným z najjednoduchších radiacich algoritmov. Jeho myšlienka spočíva v nájdení minima, ktoré sa presunie na začiatok poľa (alebo môžeme hľadať aj maximum a to dávať na koniec). V prvom kroku teda nájdeme najmenší prvok v poli a ten potom presunieme na začiatok. V druhom kroku už nebudeme pri hľadaní minima brať do úvahy skôr nájdenej minimum. Po dostatočnom počte krokov dostaneme pole zoradené. Algoritmus má nepríliš výhodnú časovú zložitosť a nie je stabilný. Je však veľmi jednoduchý na pochopenie aj implementáciu.

Vlastnosti algoritmu

časová zložitosť	(n ²⁾
stabilita	nie
rýchlosť	pomalý

Pozn. je myslená časová zložitosť priemerného prípadu a rýchlosť vzhľadom ku všetkým triediacim algoritmom.

Priebeh

Máme pole nasledujúcich prvkov:

Teraz cyklom prejdeme poľa od prvého do posledného prvku (rozsah cyklu je zvýraznený farebne) a vyberieme to najmenšie číslo (tu 1).

Toto číslo prehodíme s prvým číslom (tu s 3):

Týmto krokom sme dostali prvý prvok v poľa klasifikované. Teraz cyklom opäť prejdeme poľa a nájdeme najmenší prvok. Ale pretože ten úplne najmenší už máme na začiatku, nebudeme ho zahŕňať a prejdeme teda pole od druhého do posledného prvku a opäť vyberieme najmenší prvok (2):

Prvok si opäť zatriedime, pretože už máme 1 prvok klasifikované z minula, prehodíme ho s druhým prvkom (5).

Teraz máme už 2 prvej prvky správne. Takto budeme pokračovať ďalej, budeme vyberať minimum zo zvyšných prvkov a zatřizovat ho tak dlho, kým nebudeme mať pole celej zotriedené. Ďalšie kroky algoritmu by vyzerali nasledovne:

Posledný prvok je už logicky klasifikované, preto si môžeme tento krok ušetriť. A je hotovo.

Vizualizácia

Video ukážka

Zdrojový kód

Java
C #
Delphi
Ruby

public static void selectionSort(int[] list) {
  int temp, min;
  for (int i = 0; i < (list.length - 1); i++) {
    min = list.length - 1;
    // hledani minima
    for (int j = i; j < (list.length - 1); j++)
      if (list[min] > list[j])
        min = j;
    // prohozeni prvku
    temp = list[min];
    list[min] = list[i];
    list[i] = temp;
  }
}

public static void selectionSort(int[] list) {
  int temp, min;
  for (int i = 0; i < (list.Length - 1); i++) {
    min = list.Length - 1;
    // hledani minima
    for (int j = i; j < (list.Length - 1); j++)
      if (list[min] > list[j])
        min = j;
    // prohozeni prvku
    temp = list[min];
    list[min] = list[i];
    list[i] = temp;
  }
}

// setridi vlozene pole, predpoklada indexovani od 0
procedure selection_sort(var list: array of integer);
var i, j, min, temp: integer;
begin
  for i:=0 to (length(list) - 2) do begin
    min:=length(list) - 1;
    // hledani minima
    for j:=i to (length(list) - 1) do
      if (list[min] > list[j]) then
        min:=j;
    // prohozeni prvku
    temp:=list[min];
    list[min]:=list[i];
    list[i]:=temp;
  end;
end;

# vraci setridene pole
def selection_sort(list)
  (list.length - 1).times do |i|
    min = list.length - 1
    # hledani minima
    i.upto(list.length - 1) do |j|
      min = j if (list[min] > list[j])
    end
    # prohozeni prvku
    temp = list[min]
    list[min] = list[i]
    list[i] = temp
  end
end

Článok pre vás napísal David Hartinger

Užívateľské hodnotenie:

Ešte nikto nehodnotil, buď prvý!

David je zakladatelem ITnetwork a programování se profesionálně věnuje 15 let. Má rád Nirvanu, nemovitosti a svobodu podnikání.

David sa informačné technológie naučil na Unicorn University - prestížnej súkromnej vysokej škole IT a ekonómie.

Aktivity