Kaip naudoti pasirinkimo rūšiavimą

Pasirinkimo rūšiavimas yra rūšiavimo technika, kuri parenka sąrašo elementą ir pakeičia vietą kitu. Jis parenka didžiausią elementą ir tada pakeičia jį aukščiausio sąrašo indekso elementu.

Algoritmas tai daro pakartotinai, kol sąrašas sutvarkomas. Jei nesate tikri, kaip veikia atrankos rūšiavimas, patekote į reikiamą vietą. Toliau paaiškinsime tai išsamiau kartu su pavyzdžiu.

Pasirinkimo rūšiavimas: iš arčiau

Tarkime, kad turite sąrašą: [39, 82, 2, 51, 30, 42, 7]. Norėdami rūšiuoti sąrašą naudodami pasirinkimo rūšiavimą, pirmiausia turėtumėte rasti didžiausią skaičių jame.

Pateikus pateiktą sąrašą, šis skaičius yra 82. Pakeiskite 82 su aukščiausio indekso skaičiumi (tai yra 7).

Po pirmojo leidimo sąrašo tvarka bus tokia: [39, 7, 2, 51, 30, 42, 82]. Kiekvieną kartą, kai algoritmas pereina visą sąrašą, tai vadinama „leidimu“.

Atkreipkite dėmesį, kad rūšiavimo proceso metu sąraše yra surūšiuotas antrinis sąrašas ir nerūšiuotas antrinis sąrašas.

Susijęs: Kas yra „Big-O“ žymėjimas?

Pradinis sąrašas prasideda surūšiuotu nulinių elementų sąrašu ir nerūšiuotu visų elementų sąrašu. Tada po pirmojo leidimo jis turi surūšiuotą sąrašą, kuriame yra tik skaičius 82.

Antrojo leidimo metu didžiausias skaičius nerūšiuotame sąraše bus 51. Šis numeris bus pakeistas su 42, kad būtų pateikta nauja sąrašo tvarka:

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

Procesas kartojamas tol, kol bus surūšiuotas visas sąrašas. Žemiau pateiktame paveikslėlyje apibendrinamas visas procesas:

Pusjuodžiu šriftu paryškinti skaičiai rodo didžiausią sąrašo vertę tuo metu. Žalios spalvos rodo išrūšiuotą antrinį sąrašą.

Algoritmo analizė

Norėdami gauti šio algoritmo sudėtingumą (naudodami „Big-O“ žymėjimą), atlikite toliau pateiktus veiksmus:

Pirmojo leidimo metu atliekami (n-1) palyginimai. Antrą kartą, (n-2). Trečią kartą (n-3) ir t. T., Kol bus atliktas (n-1) trečiasis leidimas, kuris leidžia palyginti tik vieną.

Apibendrinant toliau pateiktus palyginimus, gaunama:

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

Todėl pasirinkimo rūšis yra O (n²).

Kodo įgyvendinimas

Kodas rodo funkcijas, kurias galite naudoti atliekant pasirinkimo rūšiavimą naudojant „Python“ ir „Java“.

„Python“:

def selectionSort (mano sąrašas):
x diapazone (len (mano sąrašas) - 1, 0, -1):
max_idx = 0
posn diapazone (1, x + 1):
jei mano sąrašas [posn]> mano sąrašas [max_idx]:
max_idx = pozn
temp = mylist [x]
mano sąrašas [x] = mano sąrašas [max_idx]
mylist [max_idx] = temp

„Java“:

void selectionSort (int my_array []) { 
už (int x = 0; x { 
int indeksas = x; 
už (int y = x + 1; y jei (my_array [y] indeksas = y; // rasti žemiausią indeksą 
} 
} 
int temp = my_array [rodyklė]; // temp yra laikina saugykla
my_array [rodyklė] = my_array [x]; 
my_array [x] = temp; 
}}

Pereinama nuo pasirinkimo rūšiavimo iki sujungimo rūšiavimo

Kaip parodė aukščiau pateikta algoritmo analizė, atrankos rūšiavimo algoritmas yra O (n²). Jis turi eksponentinį sudėtingumą, todėl yra neefektyvus labai dideliems duomenų rinkiniams.

Daug geriau naudoti algoritmą būtų suliejimo rūšiavimas su O (nlogn) sudėtingumu. Ir dabar jūs žinote, kaip veikia atrankos rūšiavimas, šalia jūsų rūšiavimo algoritmų tyrimo sąrašo turėtų būti sujungimo rūšiavimas.

Apie autorių