Kako uporabiti sortiranje izbora

Izbirno razvrščanje je tehnika razvrščanja, ki izbere element seznama in nato mesto zamenja z drugim. Izbere največji element in ga nato zamenja z elementom v najvišjem indeksu seznama.

Algoritem to počne večkrat, dokler seznam ni razvrščen. Če niste povsem prepričani, kako deluje sortiranje izbora, ste prišli na pravo mesto. Spodaj bomo to podrobneje razložili in vam pokazali primer.

Razvrstitev izbora: natančnejši pogled

Recimo, da imate seznam: [39, 82, 2, 51, 30, 42, 7]. Če želite seznam razvrstiti z razvrščanjem po izbiri, morate najprej najti največje število v njem.

Z navedenim seznamom je to število 82. Zamenjajte 82 s številko v najvišjem indeksu (to je 7).

Po prvem prehodu bo nov vrstni red seznama: [39, 7, 2, 51, 30, 42, 82]. Vsakič, ko algoritem prečka celoten seznam, se to imenuje "pass".

Upoštevajte, da seznam med razvrščanjem vsebuje razvrščeni in nesortirani podlist.

Sorodno: Kaj je zapis Big-O?

Prvotni seznam se začne z razvrščenim seznamom nič elementov in nerazvrščenim seznamom vseh elementov. Po prvem prehodu ima razvrščen seznam, ki ima samo številko 82.

Pri drugem prehodu bo največje število na nesortiranem podlistku 51. To številko bomo zamenjali z 42, da dobimo nov vrstni red spodaj:

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

Postopek se ponavlja, dokler ni razvrščen celoten seznam. Spodnja slika povzema celoten postopek:

Številke v krepki črni barvi prikazujejo najvišjo vrednost seznama v tistem času. Tisti v zeleni barvi prikažejo razvrščeni podlist.

Analiza algoritma

Če želite dobiti zapletenost (z uporabo zapisa Big-O) tega algoritma, sledite spodaj:

Ob prvem prehodu so narejene (n-1) primerjave. Pri drugem podajanju (n-2). Pri tretjem prehodu (n-3) in tako naprej do (n-1) th prehoda, ki naredi samo eno primerjavo.

Če povzamemo primerjave spodaj, dobimo:

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

Zato je sorta izbire O (n²).

Izvajanje kodeksa

Koda prikazuje funkcije, ki jih lahko uporabite za izvajanje razvrščanja izbir s pomočjo Python in Java.

Python:

def selectionSort (mylist):
za x v območju (len (moj seznam) - 1, 0, -1):
max_idx = 0
za posn v območju (1, x + 1):
če je moj seznam [posn]> moj seznam [max_idx]:
max_idx = posn
temp = moj seznam [x]
moj seznam [x] = moj seznam [max_idx]
moj seznam [max_idx] = temp

Java:

void selectionSort (int my_array []) { 
za (int x = 0; x { 
indeks int = x; 
za (int y = x + 1; y if (my_array [y] indeks = y; // najdemo najnižji indeks 
} 
} 
int temp = my_array [indeks]; // temp je začasno shranjevanje
my_array [indeks] = my_array [x]; 
my_array [x] = temp; 
}}

Premik od izbirnega razvrščanja do razvrščenega razvrščanja

Kot je pokazala zgornja analiza algoritma, je algoritem za razvrščanje izbire O (n²). Je eksponentno zapleten in je zato za zelo velike nabore podatkov neučinkovit.

Veliko boljši algoritem za uporabo bi bilo združevanje z zapletenostjo O (nlogn). Zdaj veste, kako deluje razvrščanje razvrščanja, naslednje na seznamu študij za algoritme za razvrščanje mora biti razvrščanje med spajanjem.

O avtorju