Selection sort

15 Dec

Selection sort patří mezi řadící algoritmy s časovou složitostí O(n2). Základní princip jeho fungování je ale velmi jednoduchý. Algoritmus pracuje tak, že projde pole, najde jeho nejmenší prvek tím, že si “označí” první prvek a srovnává ho s každým dalším prvkem, dokud nenajde nějaký menší a tak dále až do konce pole, načež tento nejmenší prvek v poli vymění s prvkem na prvním místě v poli. Následně si vytvoří “zarážku” a dále pracuje pouze s neseřazenou částí pole, která se prvek po prvku zmenšuje.

Hlavní výhodou Selection sortu je jednoduchost jeho implementace. Obecně se dá říct, že většinou funguje lépe než Bubble sort a Gnome sort. Naopak Insertion sort je ve valné většině případů lepší, často provádí jen něco přes polovinu operací, které musí pro srovnání pole provést Selection sort. Selection sort má dál tu vlastnost, že nemá best/worst case – bez ohledu na výchozí pořadí pole (pole může být už seřazené, seřazené pozpátku nebo náhodně) provede vždy stejné množství operací – n2.

Zde je video: které velmi hezky demonstruje funkci Selection sortu:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: