Třídění - selection sort
Postup je pro svoji implementaci kódu jazyka jednoduchý a snadno pochopitelný.
AM
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(n2).
- 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:
Přesné vysvětlení třídění s českými titulky je dostupné ve videu:
Reference:
