Što je sortiranje odabira?
SELECTION SORT je algoritam sortiranja za usporedbu koji se koristi za sortiranje slučajnog popisa predmeta u rastućem redoslijedu. Usporedba ne zahtijeva puno dodatnog prostora. Potreban je samo jedan dodatni prostor memorije za vremensku varijablu.
To je poznato kao in-mjestu sortiranje. Razvrstavanje odabira ima vremensku složenost O (n 2 ) gdje je n ukupan broj stavki na popisu. Složenost vremena mjeri broj ponavljanja potrebnih za sortiranje popisa. Popis je podijeljen na dvije particije: Prvi popis sadrži razvrstane stavke, dok drugi popis sadrži nerazvrstane stavke.
Prema zadanim postavkama razvrstani popis je prazan, a nerazvrstani popis sadrži sve elemente. Nerazvrstani popis zatim se skenira za minimalnu vrijednost, koja se zatim stavlja na sortirani popis. Taj se postupak ponavlja sve dok se sve vrijednosti ne usporede i razvrstaju.
U ovom vodiču iz algoritma naučit ćete:
- Što je sortiranje odabira?
- Kako funkcionira sortiranje odabira?
- Definicija problema
- Rješenje (algoritam)
- Vizualni prikaz
- Program sortiranja odabira pomoću Pythona 3
- Objašnjenje koda
- Složenost vremena odabira sortiranja
- Kada koristiti sortiranje odabira?
- Prednosti sortiranja odabira
- Mane sortiranja odabira
Kako funkcionira sortiranje odabira?
Prva stavka na nerazvrstanoj particiji uspoređuje se sa svim vrijednostima s desne strane kako bi se provjerilo je li to minimalna vrijednost. Ako to nije minimalna vrijednost, tada se njezin položaj zamijeni s minimalnom vrijednošću.
Primjer:
- Na primjer, ako je indeks minimalne vrijednosti 3, tada se vrijednost elementa s indeksom 3 postavlja na indeks 0, dok se vrijednost koja je bila na indeksu 0 stavlja na indeks 3. Ako je prvi element na nerazvrstanoj particiji minimalnu vrijednost, a zatim vraća svoje pozicije.
- Element koji je određen kao minimalna vrijednost premješta se na particiju s lijeve strane, a to je sortirani popis.
- Pregrađena strana sada ima jedan element, dok nepodijeljena strana ima (n - 1) elemente gdje je n ukupan broj elemenata na popisu. Taj se postupak ponavlja iznova i iznova dok se sve stavke ne usporede i razvrstaju na temelju njihovih vrijednosti.
Definicija problema
Popis elemenata koji su slučajnim redoslijedom potrebno je sortirati u rastućem redoslijedu. Uzmimo za primjer sljedeći popis.
[21,6,9,33,3]
Gornji popis treba sortirati da bi se dobili sljedeći rezultati
[3,6,9,21,33]
Rješenje (algoritam)
Korak 1) Dobijte vrijednost n koja je ukupna veličina polja
Korak 2) Podijelite popis na razvrstane i nesortirane odjeljke. Sortirani odjeljak u početku je prazan, a nerazvrstani odjeljak sadrži cijeli popis
Korak 3) Odaberite najmanju vrijednost iz nepodijeljenog odjeljka i stavite je u razvrstani odjeljak.
Korak 4) Ponovite postupak (n - 1) puta dok se svi elementi na popisu ne sortiraju.
Vizualni prikaz
S obzirom na popis od pet elemenata, sljedeće slike ilustriraju kako se algoritam za sortiranje odabirom prevlači kroz vrijednosti prilikom njihovog razvrstavanja.
Sljedeća slika prikazuje nesortirani popis
Korak 1)
Prva vrijednost 21 uspoređuje se s ostalim vrijednostima kako bi se provjerilo je li to minimalna vrijednost.
3 je minimalna vrijednost, pa se pozicije 21 i 3 zamjenjuju. Vrijednosti sa zelenom pozadinom predstavljaju razvrstanu particiju popisa.
Korak 2)
Vrijednost 6 koja je prvi element na nerazvrstanoj particiji uspoređuje se s ostalim vrijednostima kako bi se utvrdilo postoji li niža vrijednost
Vrijednost 6 je minimalna vrijednost, pa zadržava svoj položaj.
Korak 3)
Prvi element nesortiranog popisa s vrijednošću 9 uspoređuje se s ostalim vrijednostima kako bi se provjerilo je li to minimalna vrijednost.
Vrijednost 9 je minimalna vrijednost, pa zadržava svoj položaj u razvrstanoj particiji.
Korak 4)
Vrijednost 33 uspoređuje se s ostalim vrijednostima.
Vrijednost 21 niža je od 33, pa se mjesta zamjenjuju kako bi se dobio gornji novi popis.
Korak 5)
Na nepodijeljenom popisu preostala nam je samo jedna vrijednost. Stoga je već sortirano.
Konačni popis je poput onog prikazanog na gornjoj slici.
Program sortiranja odabira pomoću Pythona 3
Sljedeći kod prikazuje implementaciju sortiranja odabira pomoću Pythona 3
def selectionSort( itemsList ):n = len( itemsList )for i in range( n - 1 ):minValueIndex = ifor j in range( i + 1, n ):if itemsList[j] < itemsList[minValueIndex] :minValueIndex = jif minValueIndex != i :temp = itemsList[i]itemsList[i] = itemsList[minValueIndex]itemsList[minValueIndex] = tempreturn itemsListel = [21,6,9,33,3]print(selectionSort(el))
Pokretanje gornjeg koda daje sljedeće rezultate
[3, 6, 9, 21, 33]
Objašnjenje koda
Objašnjenje koda je sljedeće
Evo objašnjenja koda:
- Definira funkciju koja se naziva selectionSort
- Dobiva ukupan broj elemenata na popisu. To nam treba za određivanje broja prolaza koje treba izvršiti prilikom usporedbe vrijednosti.
- Vanjska petlja. Koristi petlju za itiranje kroz vrijednosti popisa. Broj ponavljanja je (n - 1). Vrijednost n je 5, pa nam (5 - 1) daje 4. To znači da će se vanjske iteracije izvesti 4 puta. U svakoj se iteraciji vrijednost varijable i dodjeljuje varijabli minValueIndex
- Unutarnja petlja. Koristi petlju za usporedbu krajnje lijeve vrijednosti s ostalim vrijednostima s desne strane. Međutim, vrijednost za j ne započinje s indeksom 0. Počinje s (i + 1). Ovo isključuje vrijednosti koje su već sortirane tako da se usredotočujemo na stavke koje još nisu sortirane.
- Pronalazi minimalnu vrijednost na nesortiranom popisu i postavlja je na pravi položaj
- Ažurira vrijednost minValueIndex kada je uvjet zamjene istinit
- Uspoređuje vrijednosti indeksnih brojeva minValueIndex i i da vidi jesu li jednake
- Vrijednost krajnje lijevo pohranjena je u vremensku varijablu
- Donja vrijednost s desne strane zauzima prvo mjesto u položaju
- Vrijednost koja je bila pohranjena u vremenskoj vrijednosti pohranjena je u položaju koji je prethodno zauzimala minimalna vrijednost
- Vraća razvrstani popis kao rezultat funkcije
- Stvara popis koji sadrži slučajne brojeve
- Ispišite razvrstani popis nakon poziva odabira Funkcija sortiranja koja se kao parametar predaje el.
Složenost vremena odabira sortiranja
Složenost sortiranja koristi se za izražavanje broja puta izvršavanja potrebnih za sortiranje popisa. Implementacija ima dvije petlje.
Vanjska petlja koja bira vrijednosti jednu po jednu sa popisa izvršava se n puta, gdje je n ukupan broj vrijednosti na popisu.
Unutarnja petlja, koja uspoređuje vrijednost iz vanjske petlje s ostatkom vrijednosti, također se izvršava n puta, gdje je n ukupan broj elemenata na popisu.
Stoga je broj izvršenja (n * n), koji se također može izraziti kao O (n 2 ).
Sorta odabira ima tri kategorije složenosti;
- Najgori slučaj - ovdje je navedeni popis u padajućem redoslijedu. Algoritam izvodi maksimalan broj izvršavanja koji se izražava kao [Big-O] O (n 2 )
- Najbolji slučaj - to se događa kada je navedeni popis već sortiran. Algoritam izvodi minimalni broj izvršavanja koji se izražava kao [Big-Omega] Ω (n 2 )
- Prosječni slučaj - to se događa kada je popis slučajnim redoslijedom. Prosječna složenost izražava se kao [Big-theta] ⊝ (n 2 )
Razvrstavanje odabira ima složenost prostora O (1) jer zahtijeva jednu vremensku varijablu koja se koristi za zamjenu vrijednosti.
Kada koristiti sortiranje odabira?
Sortiranje odabira najbolje se koristi kada želite:
- Morate sortirati mali popis predmeta u rastućem redoslijedu
- Kad je trošak zamjene vrijednosti beznačajan
- Također se koristi kada trebate provjeriti jesu li provjerene sve vrijednosti na popisu.
Prednosti sortiranja odabira
Slijede prednosti odabira
- Izvršava se vrlo dobro na malim popisima
- To je algoritam na mjestu. Ne zahtijeva puno prostora za sortiranje. Za zadržavanje vremenske varijable potreban je samo jedan dodatni prostor.
- Dobro se izvodi na već razvrstanim stavkama.
Mane sortiranja odabira
Slijede nedostaci vrste odabira.
- Loše se snalazi kada radi na ogromnim popisima.
- Broj ponavljanja izvršenih tijekom sortiranja je n-kvadrat, gdje je n ukupan broj elemenata na popisu.
- Ostali algoritmi, poput brzog sortiranja, imaju bolje performanse u usporedbi s odabirom sortiranja.
Sažetak:
- Sortiranje odabira algoritam je usporedbe na mjestu koji se koristi za sortiranje slučajnog popisa u poredani popis. Ima vremensku složenost od O (n 2 )
- Popis je podijeljen u dva odjeljka, sortirani i nerazvrstani. Minimalna vrijednost odabire se iz nerazvrstanog odjeljka i stavlja u razvrstani odjeljak.
- Ova se stvar ponavlja sve dok se sve stavke ne sortiraju.
- Implementacija pseudokoda u Python 3 uključuje upotrebu dvije for petlje i if naredbi za provjeru je li zamjena potrebna
- Složenost vremena mjeri broj koraka potrebnih za sortiranje popisa.
- Složenost vremena u najgorem slučaju događa se kada je popis u padajućem redoslijedu. Ima vremensku složenost od [Big-O] O (n 2 )
- Složenost vremena u najboljem slučaju događa se kada je popis već u rastućem redoslijedu. Ima vremensku složenost od [Big-Omega] Ω (n 2 )
- Složenost vremena u prosječnom slučaju događa se kada je popis slučajnim redoslijedom. Ima vremensku složenost od [Big-theta] ⊝ (n 2 )
- Razvrstavanje odabira najbolje se koristi kada imate mali popis predmeta za sortiranje, trošak zamjene vrijednosti nije važan, a provjera svih vrijednosti je obavezna.
- Razvrstavanje odabira nema dobru izvedbu na ogromnim popisima
- Ostali algoritmi za sortiranje, poput brzog sortiranja, imaju bolje performanse u usporedbi s sortiranjem odabira.