a Selection sort egy egyszerű rendezési algoritmus. Ez a rendezési algoritmus egy helyben összehasonlításon alapuló algoritmus, amelyben a lista két részre oszlik, a rendezett részre a bal végén, a rendezetlen részre a jobb végén. Kezdetben a rendezett rész üres, a rendezetlen rész pedig a teljes lista.
a legkisebb elemet választja ki a rendezetlen tömbből, és a bal szélső elemmel cseréli, és ez az elem a rendezett tömb részévé válik. Ez a folyamat folytatja a rendezetlen tömbhatár mozgatását egy elemmel jobbra.
ez az algoritmus nem alkalmas nagy adathalmazokra, mivel az átlagos és a legrosszabb eset komplexitása(N2), ahol n az elemek száma.
Hogyan Működik A Válogatás?
vegyük példaként a következő ábrázolt tömböt.
a rendezett lista első helyén a teljes lista beolvasása egymás után történik. Az első helyen, ahol jelenleg 14 van tárolva, a teljes listán átkutatjuk, és megállapítjuk, hogy a 10 a legalacsonyabb érték.
tehát a 14-et 10-re cseréljük. Egy iteráció után a 10, amely történetesen a lista minimális értéke, megjelenik a rendezett lista első pozíciójában.
a második pozícióban, ahol a 33 lakik, elkezdjük a lista többi részét lineáris módon beolvasni.
megállapítottuk, hogy a 14 a lista második legalacsonyabb értéke, és a második helyen kell megjelennie. Cseréljük ezeket az értékeket.
két iteráció után két legkisebb érték kerül elhelyezésre az elején rendezett módon.
ugyanez a folyamat a tömb többi elemére is érvényes.
az alábbiakban a teljes rendezési folyamat képi ábrázolása látható −
most tanuljunk meg néhány programozási szempontot a kiválasztás rendezéséről.
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
pszeudokó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
ha tudni szeretne a kiválasztás rendezéséről a C programozási nyelvben, kattintson ide.