A Selection Sort használata

A Selection sort egy válogatási technika, amely kiválaszt egy listaelemet, majd helyet cserél egy másikkal. Kiválasztja a legnagyobb elemet, majd felcseréli a lista legmagasabb indexében szereplő tétellel.

Az algoritmus ezt a lista rendezéséig ismételten elvégzi. Ha nem biztos abban, hogy a kiválasztás rendezése hogyan működik, akkor jó helyre került. Az alábbiakban részletesebben elmagyarázzuk, egy példával együtt.

Válogatás rendezése: Közelebb néz

Tegyük fel, hogy megvan a lista: [39, 82, 2, 51, 30, 42, 7]. A lista kiválasztási rendezéssel történő rendezéséhez először meg kell találnia a legmagasabb számot benne.

A megadott listával ez a szám 82. Cserélje a 82-et a legmagasabb index számával (azaz 7-el).

Az első lépés után az új listarend a következő lesz: [39, 7, 2, 51, 30, 42, 82]. Valahányszor az algoritmus végigjárja a teljes listát, ezt "átengedésnek" nevezik.

Figyelje meg, hogy a lista rendezett allistát és rendezetlen allistát tart fenn a rendezési folyamat során.

Összefüggő: Mi a Big-O jelölés?

Az eredeti lista egy nulla elemből álló rendezett listával és az összes elem rendezetlen listájával kezdődik. Ezután az első menet után rendezett listája van, amelynek csak a 82-es száma van.

A második menetnél a válogatás nélküli listán a legnagyobb szám 51 lesz. Ezt a számot 42-re cseréljük, hogy az alábbi új sorrendet kapjuk:

[39, 7, 2, 42, 30, 51, 82].

A folyamatot addig ismételjük, amíg a teljes lista rendezésre nem kerül. Az alábbi ábra az egész folyamatot összefoglalja:

A félkövéren fekete számok az akkori legmagasabb listaértéket mutatják. A zöld színűek a rendezett allistát mutatják.

Algoritmuselemzés

Az algoritmus bonyolultságának (Big-O jelölés használatával) megismeréséhez kövesse az alábbi lépéseket:

Az első menetben (n-1) összehasonlításokat végeznek. A második meneten (n-2). A harmadik menetben (n-3) és így tovább az (n-1). Passzig, amely csak egy összehasonlítást végez.

Az összehasonlítások összegzése az alábbiak szerint:

(n-1) + (n-1) + (n-1) +... + 1 = ((n-1) n) / 2.

Ezért a szelekció rendezése O (n²).

Kód végrehajtása

A kód megmutatja azokat a funkciókat, amelyeket a szelektálás rendezéséhez használhat Python és Java használatával.

Piton:

def selectionSort (listám):
x-re a tartományban (len (listám) - 1, 0, -1):
max_idx = 0
Posn tartományban (1, x + 1):
ha mylist [posn]> mylist [max_idx]:
max_idx = posn
temp = listám [x]
mylist [x] = mylist [max_idx]
mylist [max_idx] = temp

Jáva:

void selectionSort (int my_array []) { 
for (int x = 0; x { 
int index = x; 
for (int y = x + 1; y ha (my_array [y] index = y; // megtalálja a legalacsonyabb indexet 
} 
} 
int temp = my_array [index]; A // temp ideiglenes tároló
my_array [index] = my_array [x]; 
my_array [x] = hőmérséklet; 
}}

Tovább lépés a kijelölés rendezéséről a rendezés egyesítésére

Amint a fenti algoritmuselemzés megmutatta, a szelekció rendezési algoritmus O (n²). Exponenciálisan összetett, ezért nagyon nagy adatkészletek esetén nem hatékony.

Sokkal jobb algoritmus lenne az egyesítés rendezése az O (nlogn) összetettségével. És most már tudja, hogyan működik a válogatás rendezése, az algoritmusok rendezéséhez a tanulmányi listán a következő az egyesítés rendezése legyen.

A szerzőről