Triedenie Selection sort

Triedenie Selectin sort funguje na princípe, že nájde v poli najmenší prvok a dá ho na začiatok (teda vlastne vymení si miesto s prvým prvkom v poli). Následne pracuje len poľom od druhého miesta po koniec. V tejto pravej časti poľa nájde najmenší prvok a vloží ho na začiatok (teda vlastne vymení si miesto s druhým prvkom v poli). Preto, že hľadá vždy najmenšie prvky, niekedy sa volá aj Min sort.

Pri 100 prvkovom poli nájde minimum na 99 porovnaní, potom na 1 výmenu vloží toto minimum na začiatok. Pri 99 prvkovom pravom podpoli nájde minimum na 98 porovnaní, potom na 1 výmenu vloží toto minimum na druhý začiatok. Počet všetkých porovnaní je teda 99+98+97+…+2+1, počet výmen je maximálne 99 (lebo posledný prvok už netreba vymieňať).

 

selection sort