Selection sort je jednoduchý třídící algoritmus. Tento třídící algoritmus je srovnávací algoritmus založený na místě, ve kterém je seznam rozdělen na dvě části, tříděnou část na levém konci a netříděnou část na pravém konci. Zpočátku je tříděná část prázdná a netříděná část je celý seznam.
nejmenší prvek je vybrán z netříděného pole a vyměněn za prvek zcela vlevo a tento prvek se stává součástí tříděného pole. Tento proces pokračuje v pohybu netříděné hranice pole o jeden prvek doprava.
tento algoritmus není vhodný pro velké datové soubory, protože jeho průměrná a nejhorší složitost je Ο(n2), kde n je počet položek.
Jak Funguje Řazení Výběru?
zvažte jako příklad následující zobrazené pole.
pro první pozici v seřazeném seznamu je celý seznam skenován postupně. První pozice, kde je 14 uloženo v současné době, prohledáme celý seznam a zjistíme, že 10 je nejnižší hodnota.
takže nahradíme 14 10. Po jedné iteraci 10, která se stane minimální hodnotou v seznamu, se objeví na první pozici seřazeného seznamu.
pro druhou pozici, kde sídlí 33, začneme lineárně skenovat zbytek seznamu.
zjistíme, že 14 je druhá nejnižší hodnota v seznamu a měla by se objevit na druhém místě. Vyměníme tyto hodnoty.
po dvou iteracích jsou dvě nejmenší hodnoty umístěny na začátku seřazeným způsobem.
stejný postup se použije na ostatní položky v poli.
následuje obrazové zobrazení celého procesu třídění –
nyní se Naučme některé programovací aspekty selection sort.
algoritmus
Step 1 − Set MIN to location 0Step 2 − Search the minimum element in the listStep 3 − Swap with value at location MINStep 4 − Increment MIN to point to next elementStep 5 − Repeat until list is sorted
pseudokód
procedure selection sort list : array of items n : size of list for i = 1 to n - 1 /* set current element as minimum*/ min = i /* check the element to be minimum */ for j = i+1 to n if list < list then min = j; end if end for /* swap the minimum element with the current element*/ if indexMin != i then swap list and list end if end forend procedure
Chcete-li vědět o implementaci selection sort v programovacím jazyce C, klikněte zde.