Kaj je sorta izbire?
SELECTION SORT je algoritem za primerjalno razvrščanje, ki se uporablja za razvrščanje naključnega seznama elementov v naraščajočem vrstnem redu. Primerjava ne zahteva veliko dodatnega prostora. Zahteva le en dodaten pomnilniški prostor za časovno spremenljivko.
To je znano kot sortiranje na mestu . Razvrstitev izbora ima časovno zapletenost O (n 2 ), kjer je n skupno število elementov na seznamu. Zapletenost časa meri število ponovitev, potrebnih za razvrščanje seznama. Seznam je razdeljen na dve particiji: prvi seznam vsebuje razvrščene elemente, drugi seznam pa nesortirane elemente.
Razvrščeni seznam je privzeto prazen, nesortiran pa vsebuje vse elemente. Nato je nesortirani seznam skeniran za najnižjo vrednost, ki se nato postavi na razvrščeni seznam. Ta postopek se ponavlja, dokler se vse vrednosti ne primerjajo in razvrstijo.
V tej vadnici Algoritma boste izvedeli:
- Kaj je sorta izbire?
- Kako deluje sortiranje izbora?
- Opredelitev težave
- Rešitev (algoritem)
- Vizualna predstavitev
- Program za razvrščanje izbir z uporabo Pythona 3
- Razlaga kode
- Časovna zapletenost izbora razvrstitve
- Kdaj uporabiti razvrščanje izbora?
- Prednosti sorte izbire
- Slabosti sorte izbire
Kako deluje sortiranje izbora?
Prvi element na nesortirani particiji se primerja z vsemi vrednostmi na desni, da se preveri, ali je to najmanjša vrednost. Če to ni najmanjša vrednost, se njen položaj zamenja z najmanjšo vrednostjo.
Primer:
- Če je na primer indeks najmanjše vrednosti 3, je vrednost elementa z indeksom 3 postavljena na indeks 0, vrednost, ki je bila na indeksu 0, pa na indeks 3. Če je prvi element v nesortirani particiji najmanjšo vrednost, nato vrne svoje položaje.
- Element, ki je bil določen kot najmanjša vrednost, se nato premakne na particijo na levi strani, ki je razvrščen seznam.
- Predeljena stran ima zdaj en element, medtem ko ima nerazdeljena stran (n - 1) elemente, kjer je n skupno število elementov na seznamu. Ta postopek se ponavlja vedno znova, dokler niso vsi elementi primerjani in razvrščeni glede na njihove vrednosti.
Opredelitev težave
Seznam elementov v naključnem vrstnem redu je treba razvrstiti po naraščajočem vrstnem redu. Kot primer si oglejte naslednji seznam.
[21,6,9,33,3]
Zgornji seznam je treba razvrstiti, da dobimo naslednje rezultate
[3,6,9,21,33]
Rešitev (algoritem)
Korak 1) Pridobite vrednost n, ki je skupna velikost matrike
Korak 2) Seznam razdelite na razvrščene in nesortirane odseke. Razvrščeni odsek je sprva prazen, nerazvrščen pa vsebuje celoten seznam
Korak 3) Iz nerazdeljenega odseka izberite najmanjšo vrednost in jo postavite v razvrščeni odsek.
Korak 4) Ponovite postopek (n - 1) krat, dokler niso razvrščeni vsi elementi na seznamu.
Vizualna predstavitev
Glede na seznam petih elementov naslednje slike ponazarjajo, kako algoritem za razvrščanje izbire pregleduje vrednosti med razvrščanjem.
Naslednja slika prikazuje nesortiran seznam
Korak 1)
Prva vrednost 21 se primerja z ostalimi vrednostmi, da se preveri, ali je to najmanjša vrednost.
3 je najmanjša vrednost, zato se položaj 21 in 3 zamenjata. Vrednosti z zelenim ozadjem predstavljajo razvrščeno particijo seznama.
2. korak)
Vrednost 6, ki je prvi element v nesortirani particiji, se primerja z ostalimi vrednostmi, da se ugotovi, ali obstaja nižja vrednost
Vrednost 6 je najmanjša vrednost, zato ohranja svoj položaj.
3. korak)
Prvi element nesortiranega seznama z vrednostjo 9 se primerja z ostalimi vrednostmi, da se preveri, ali je to najmanjša vrednost.
Vrednost 9 je najmanjša vrednost, zato ohranja svoj položaj v razvrščeni particiji.
4. korak)
Vrednost 33 se primerja z ostalimi vrednostmi.
Vrednost 21 je nižja od 33, zato se položaji zamenjajo, da se pripravi zgornji novi seznam.
5. korak)
Na nerazdeljenem seznamu imamo samo še eno vrednost. Zato je že razvrščeno.
Končni seznam je podoben seznamu, prikazanemu na zgornji sliki.
Program za razvrščanje izbir z uporabo Pythona 3
Naslednja koda prikazuje izvedbo razvrščanja izbora z uporabo Python 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))
Zaženi zgornjo kodo daje naslednje rezultate
[3, 6, 9, 21, 33]
Razlaga kode
Razlaga kode je naslednja
Tu je razlaga kode:
- Določa funkcijo z imenom selectionSort
- Pridobi skupno število elementov na seznamu. To potrebujemo za določitev števila prehodov, ki jih je treba opraviti pri primerjavi vrednosti.
- Zunanja zanka. Uporablja zanko za ponoven pregled vrednosti seznama. Število ponovitev je (n - 1). Vrednost n je 5, torej (5 - 1) nam daje 4. To pomeni, da bodo zunanje ponovitve izvedene 4-krat. V vsaki ponovitvi je vrednost spremenljivke i dodeljena spremenljivki minValueIndex
- Notranja zanka. Z zanko primerja skrajno levo vrednost z drugimi vrednostmi na desni strani. Vendar se vrednost za j ne začne pri indeksu 0. Začne se pri (i + 1). To izključuje že razvrščene vrednosti, tako da se osredotočimo na postavke, ki še niso bile razvrščene.
- Najde najmanjšo vrednost na nesortiranem seznamu in jo postavi v pravi položaj
- Posodobi vrednost minValueIndex, če je pogoj zamenjave resničen
- Primerja vrednosti indeksnih števil minValueIndex in i, da ugotovi, ali niso enake
- Najkrajša leva vrednost je shranjena v časovni spremenljivki
- Spodnja vrednost na desni strani zavzame položaj v prvem položaju
- Vrednost, ki je bila shranjena v časovni vrednosti, je shranjena v položaju, ki ga je prej imela najmanjša vrednost
- Vrne razvrščeni seznam kot rezultat funkcije
- Ustvari seznam el z naključnimi številkami
- Natisnite razvrščeni seznam, potem ko pokličete funkcijo Razvrsti, ki kot parameter posreduje el
Časovna zapletenost izbora razvrstitve
Zapletenost razvrščanja se uporablja za izražanje števila izvedb, potrebnih za razvrščanje seznama. Izvedba ima dve zanki.
Zunanja zanka, ki izbere vrednosti eno za drugo s seznama, se izvede n-krat, pri čemer je n skupno število vrednosti na seznamu.
Notranja zanka, ki primerja vrednost iz zunanje zanke z ostalimi vrednostmi, se izvede tudi n-krat, pri čemer je n skupno število elementov na seznamu.
Zato je število izvršitev (n * n), kar lahko izrazimo tudi kot O (n 2 ).
Izbirna sorta ima tri kategorije zahtevnosti, in sicer;
- Najslabši primer - tukaj je naveden seznam v padajočem vrstnem redu. Algoritem izvede največje število izvedb, ki je izraženo kot [Big-O] O (n 2 )
- Najboljši primer - to se zgodi, ko je navedeni seznam že razvrščen. Algoritem izvede najmanjše število izvedb, ki je izraženo kot [Big-Omega] Ω (n 2 )
- Povprečen primer - to se zgodi, če je seznam v naključnem vrstnem redu. Povprečna zahtevnost je izražena kot [Big-theta] ⊝ (n 2 )
Izbirna sorta ima zapletenost prostora O (1), saj zahteva eno časovno spremenljivko, ki se uporablja za zamenjavo vrednosti.
Kdaj uporabiti razvrščanje izbora?
Razvrščanje izbora je najbolje uporabiti, če želite:
- Majhen seznam elementov morate razvrstiti po naraščajočem vrstnem redu
- Ko so stroški zamenjave vrednosti nepomembni
- Uporablja se tudi, ko se morate prepričati, da so bile preverjene vse vrednosti na seznamu.
Prednosti sorte izbire
Sledijo prednosti izbire
- Zelo dobro se obnese na majhnih seznamih
- To je algoritem na mestu. Za razvrščanje ne zahteva veliko prostora. Za zadrževanje časovne spremenljivke je potreben le en dodaten prostor.
- Dobro se obnese pri že razvrščenih elementih.
Slabosti sorte izbire
Sledijo slabosti izbire.
- Slabo se obnese pri delu na ogromnih seznamih.
- Število ponovitev, opravljenih med razvrščanjem, je n-kvadrat, kjer je n skupno število elementov na seznamu.
- Drugi algoritmi, na primer hitri razvrščanje, imajo boljšo zmogljivost v primerjavi z izbirno razvrstitvijo.
Povzetek:
- Izbirno razvrščanje je primerjalni algoritem na mestu, ki se uporablja za razvrščanje naključnega seznama v urejen seznam. Ima časovno zapletenost O (n 2 )
- Seznam je razdeljen na dva odseka, razvrščena in nerazvrščena. Najmanjša vrednost se izbere iz nerazvrščenega odseka in postavi v razvrščeni odsek.
- Ta stvar se ponavlja, dokler niso razvrščeni vsi elementi.
- Izvajanje psevdokode v Python 3 vključuje uporabo dveh for zanke in stavkov if za preverjanje, ali je zamenjava potrebna
- Zapletenost časa meri število korakov, potrebnih za razvrščanje seznama.
- Najslabša časovna zapletenost se zgodi, če je seznam v padajočem vrstnem redu. Ima časovno zapletenost [Big-O] O (n 2 )
- Najbolj primerna časovna zapletenost se zgodi, ko je seznam že v naraščajočem vrstnem redu. Ima časovno zapletenost [Big-Omega] Ω (n 2 )
- Zapletenost časa v povprečnem primeru se zgodi, če je seznam v naključnem vrstnem redu. Ima časovno zapletenost [Big-theta] ⊝ (n 2 )
- Izbirno razvrščanje je najbolje uporabiti, če imate majhen seznam elementov za razvrščanje, stroški zamenjave vrednosti niso pomembni in je preverjanje vseh vrednosti obvezno.
- Razvrstitev na velikih seznamih ni uspešna
- Drugi algoritmi za razvrščanje, na primer hitri razvrščanje, imajo boljšo zmogljivost v primerjavi z izbirnim razvrščanjem.