Home-theater-designers
Razvrščanje po izbiri je tehnika razvrščanja, ki izbere element seznama in nato svoje mesto zamenja z drugim. Izbere največji element in ga nato zamenja z elementom v najvišjem indeksu seznama.
Algoritem to ponavlja večkrat, dokler se seznam ne razvrsti. Če niste povsem prepričani, kako deluje razvrščanje, ste prišli na pravo mesto. Spodaj bomo podrobneje razložili skupaj s primerom.
Razvrstitev izbora: natančnejši pogled
Recimo, da imate seznam: [39, 82, 2, 51, 30, 42, 7]. Če želite razvrstiti seznam z razvrščanjem izbir, morate najprej najti najvišje število v njem.
Pri danem seznamu 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 gre algoritem skozi celoten seznam, se to imenuje 'prehod'.
Upoštevajte, da seznam med razvrščanjem vzdržuje razvrščen in nerazvrščen podnapis.
ugotovite, kdo vas ni spremljal na instagramu
Povezano: Kaj je zapis Big-O?
Prvotni seznam se začne z razvrščenim seznamom nič elementov in nerazvrščenim seznamom vseh elementov. Potem ima po prvem prehodu razvrščen seznam samo s številko 82.
Na drugem prehodu bo največje število na nerazvrščanem podnapisu 51. To številko bomo zamenjali s 42, da dobimo nov vrstni red spodaj:
kako posneti pogovor na iphone
[39, 7, 2, 42, 30, 51, 82].
Postopek se ponavlja, dokler se ne razvrsti celoten seznam. Spodnja slika povzema celoten postopek:
Krepko črne številke kažejo najvišjo vrednost seznama v tistem času. Tisti v zeleni barvi prikazujejo razvrščeni podnapis.
Algoritemska analiza
Za zapletenost (z zapisom Big-O) tega algoritma sledite spodaj:
Na prvem prehodu so narejene primerjave (n-1). Na drugem prehodu, (n-2). Na tretjem prehodu (n-3) in tako naprej do (n-1) -tega prehoda, kar naredi samo eno primerjavo.
Če povzamemo spodnje primerjave, dobimo:
(n-1)+ (n-1)+ (n-1)+ ...+ 1 = ((n-1) n)/2.
Zato je vrsta izbire O (n2).
Izvajanje kodeksa
Koda prikazuje funkcije, ki jih lahko uporabite za izvajanje razvrščanja izbir z uporabo Pythona in Jave.
Python:
def selectionSort(mylist):
for x in range(len(mylist) - 1, 0, -1):
max_idx = 0
for posn in range(1, x + 1):
if mylist[posn] > mylist[max_idx]:
max_idx = posn
temp = mylist[x]
mylist[x] = mylist[max_idx]
mylist[max_idx] = tempJava:
void selectionSort(int my_array[]){
for (int x = 0; x {
int index = x;
for (int y = x + 1; y if (my_array[y] index = y; // find lowest index
}
}
int temp = my_array[index]; // temp is a temporary storage
my_array[index] = my_array[x];
my_array[x] = temp;
}} Premikanje iz razvrščanja izbire v razvrščanje združevanja
Kot je pokazala zgornja analiza algoritma, je algoritem sortiranja izbire O (n2). Ima eksponentno kompleksnost in je zato neučinkovit za zelo velike nabore podatkov.
kako narediti, da google chrome ne porabi toliko pomnilnika
Veliko boljši algoritem za uporabo bi bilo združevanje z zapletenostjo O (nlogn). In zdaj veste, kako deluje selekcijsko razvrščanje, naslednja na seznamu študij za razvrščanje algoritmov bi morala biti razvrščanje.
Deliti Deliti Cvrkutati E-naslov 8 najboljših spletnih mest za brezplačen prenos zvočnih knjigZvočne knjige so odličen vir zabave in so veliko lažje prebavljive. Tu je osem najboljših spletnih mest, kjer jih lahko brezplačno prenesete.
Preberite Naprej Sorodne teme- Programiranje
- Programiranje
- Algoritmi
Jerome je osebni pisatelj pri MakeUseOf. Zajema članke o programiranju in Linuxu. Je tudi navdušenec nad kripto kripto in vedno spremlja kripto industrijo.
Več od Jeroma DavidsonaNaročite se na naše novice
Pridružite se našemu glasilu za tehnične nasvete, ocene, brezplačne e -knjige in ekskluzivne ponudbe!
Kliknite tukaj, če se želite naročiti