Jdi na obsah Jdi na menu

Třídění - selection sort

Selection sort je univerzální řadící algoritmus, který se používá prakticky k seřazení malé skupiny prvků.

Program nastaví první prvek pole na minimum a dále jej porovnává s dalším prvkem dokud nenarazí na menší, který zase porovnává. Pokud je tento prvek skutečně nejmenší - algoritmu ho přiřadí do pole sorted, přičemž se tento postup opakuje dokud pole unsorted je rovná nule.

Výhody:

  • Pro svoji implementaci je velmi jednoduchý.
  • ​Nevyžaduje paměť.

Nevýhody:

  • ​​Jeho asymptotická časová složitost je velká O(n​2​).
  • ​Nestabilita.

Máme 10 čísel. Červená barva představuje neseřazenou skupinu (unsorted) a seřazená modrou (sorted).

Proces řazení výběrem:

​Algoritmus bychom si mohli polopatě představit třeba takto:

73 03 26 46 43 67 35 07 02 99 : Neseřazená čísla.

 

02   73 03 26 46 43 67 35 07 99 : Nastav ,.i" na první číslo, pokud je nějaké menší, nastav minimum - poté přiřaď ,,i" do seřazených. V našem případě je 02.

02 03   73 26 46 43 67 35 07 99 : Takto postupuj dokud neseřazená = 0.

02 03 07   73 26 46 43 67 35 99

02 03 07 26   73 46 43 67 35 99

02 03 07 26 35   73 46 43 67 99

02 03 07 26 35 43   73 46 67 99

02 03 07 26 35 43 46   73 67 99

02 03 07 26 35 43 46 67   73 99

02 03 07 26 35 43 46 67 73   99

02 03 07 26 35 43 46 67 73 99

 

Vzestupný graf ze zdroje wikipedie.

 

Program aplikovaný ve Scratchi:

select.jpg

 

Přesné vysvětlení třídění s českými titulky je dostupné ve videu:

 

 

 

Reference:

cs.wikipedia.org

scratch.mit.edu

 

Komentáře

Přidat komentář

Přehled komentářů

Zatím nebyl vložen žádný komentář