Mis on valiku sortimine?
SELECTION SORT on võrdleva sorteerimise algoritm, mida kasutatakse üksuste juhusliku loendi sortimiseks kasvavas järjekorras. Võrdlus ei nõua palju lisaruumi. Ajalise muutuja jaoks on vaja ainult ühte täiendavat mäluruumi.
Seda nimetatakse kohapeal sorteerimiseks. Valiku sorteerimise ajaline keerukus on O (n 2 ), kus n on loendis olevate üksuste koguarv. Aja keerukus mõõdab loendi sortimiseks vajalike korduste arvu. Nimekiri on jagatud kaheks sektsiooniks: esimene loend sisaldab sorteeritud üksusi, teine aga sorteerimata üksusi.
Vaikimisi on sorteeritud loend tühi ja sortimata loend sisaldab kõiki elemente. Seejärel skaneeritakse sortimata loend minimaalse väärtuse osas, mis seejärel paigutatakse sorteeritud loendisse. Seda protsessi korratakse seni, kuni kõiki väärtusi on võrreldud ja sorteeritud.
Selles algoritmi õpetuses saate teada:
- Mis on valiku sortimine?
- Kuidas valiku sortimine käib?
- Probleemi määratlus
- Lahendus (algoritm)
- Visuaalne esitus
- Sortimisprogrammi valimine Python 3 abil
- Koodi selgitus
- Valiku sorteerimise ajaline keerukus
- Millal kasutada valiku sortimist?
- Valiku sortimise eelised
- Valiku sorteerimise puudused
Kuidas valiku sortimine käib?
Sorteerimata sektsiooni esimest üksust võrreldakse kõigi parempoolsete väärtustega, et kontrollida, kas see on minimaalne väärtus. Kui see pole minimaalne väärtus, vahetatakse selle asukoht minimaalse väärtusega.
Näide:
- Näiteks kui minimaalse väärtuse indeks on 3, asetatakse indeksiga 3 elemendi väärtus indeksile 0, samas kui indeksil 0 olnud väärtus asetatakse indeksile 3. Kui sortimata sektsiooni esimene element on miinimumväärtus, siis tagastab oma positsioonid.
- Minimaalseks väärtuseks määratud element viiakse seejärel vasakpoolsel sektsioonil, mis on sorditud loend.
- Jaotatud küljel on nüüd üks element, samal ajal kui jaotamata poolel on (n - 1) elementi, kus n on loendi elementide koguarv. Seda protsessi korratakse ikka ja jälle, kuni kõiki üksusi on nende väärtuste põhjal võrreldud ja sorteeritud.
Probleemi määratlus
Juhuslikus järjekorras olevate elementide loetelu tuleb järjestada kasvavas järjekorras. Vaatleme näiteks järgmist loendit.
[21,6,9,33,3]
Ülaltoodud loend tuleks sortida järgmiste tulemuste saamiseks
[3,6,9,21,33]
Lahendus (algoritm)
1. samm. Hankige n väärtus, mis on massiivi kogu suurus
2. samm. Jaotage loend sorditud ja sortimata osadeks. Sorteeritud jaotis on esialgu tühi, samas kui sortimata jaotis sisaldab tervet loendit
Samm 3) Valige jaotamata jaotisest minimaalne väärtus ja asetage see sorditud sektsiooni.
Samm 4) Korrake protsessi (n - 1) korda, kuni kõik loendi elemendid on sorteeritud.
Visuaalne esitus
Viie elemendi loendi põhjal illustreerivad järgmised pildid, kuidas valiku sortimise algoritm nende sortimisel väärtuste kaudu kordub.
Järgmine pilt näitab sortimata loendit
Samm 1)
Esimest väärtust 21 võrreldakse ülejäänud väärtustega, et kontrollida, kas see on minimaalne väärtus.
3 on minimaalne väärtus, nii et positsioonid 21 ja 3 vahetatakse. Rohelise taustaga väärtused tähistavad loendi sorditud sektsiooni.
2. samm)
Väärtust 6, mis on sortimata sektsiooni esimene element, võrreldakse ülejäänud väärtustega, et teada saada, kas on olemas väiksem väärtus
Väärtus 6 on minimaalne väärtus, nii et see säilitab oma positsiooni.
3. samm)
Sorteerimata loendi esimest elementi väärtusega 9 võrreldakse ülejäänud väärtustega, et kontrollida, kas see on minimaalne väärtus.
Väärtus 9 on minimaalne väärtus, nii et see säilitab oma positsiooni sorteeritud sektsioonis.
4. samm)
Väärtust 33 võrreldakse ülejäänud väärtustega.
Väärtus 21 on madalam kui 33, seega vahetatakse positsioonid ülaltoodud uue loendi koostamiseks.
5. samm)
Meil on jaotamata loendis alles vaid üks väärtus. Seetõttu on see juba sorteeritud.
Lõplik nimekiri on nagu ülaltoodud pildil.
Sortimisprogrammi valimine Python 3 abil
Järgmine kood näitab Python 3 abil valiku sorteerimist
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))
Ülaltoodud koodi käivitamine annab järgmised tulemused
[3, 6, 9, 21, 33]
Koodi selgitus
Koodi selgitus on järgmine
Siin on koodi selgitus:
- Määrab funktsiooni nimega selectionSort
- Saab loendis olevate elementide koguarvu. Vajame seda väärtuste võrdlemisel tehtavate läbipääsude arvu määramiseks.
- Välimine silmus. Kasutab tsüklit loendi väärtuste itereerimiseks. Korduste arv on (n - 1). N väärtus on 5, nii et (5 - 1) annab meile 4. See tähendab, et välised iteratsioonid tehakse 4 korda. Igas iteratsioonis määratakse muutuja i väärtus muutujale minValueIndex
- Sisemine silmus. Kasutab tsüklit, et võrrelda vasakpoolset väärtust teiste parempoolsete väärtustega. J väärtus ei alga siiski indeksist 0. See algab punktist (i + 1). See välistab väärtused, mis on juba sorteeritud, nii et keskendume üksustele, mida pole veel sorteeritud.
- Leiab miinimumväärtuse sortimata loendist ja paigutab selle õigesse kohta
- Värskendab minValueIndexi väärtust, kui vahetustingimus on tõene
- Võrdleb indeksnumbrite minValueIndex ja i väärtusi, et näha, kas need pole võrdsed
- Vasakpoolseim väärtus salvestatakse ajalises muutujas
- Parema käe madalam väärtus võtab positsiooni esimese positsiooni
- Ajalises väärtuses salvestatud väärtus salvestatakse positsiooni, mida varem hoidis minimaalne väärtus
- Tagastab funktsiooni tulemina sorditud loendi
- Loob loendi el, millel on juhuslikud numbrid
- Sorteeritud loetelu printimine pärast valiku Sordi funktsiooni kutsumist parameetrina edastatakse el.
Valiku sorteerimise ajaline keerukus
Sorteerimise keerukust kasutatakse loendi sorteerimiseks kuluvate täitmiskordade arvu väljendamiseks. Rakendusel on kaks silmust.
Väline silmus, mis valib loendist ükshaaval väärtused, teostatakse n korda, kus n on loendi väärtuste koguarv.
Sisemine silmus, mis võrdleb välise silmuse väärtust ülejäänud väärtustega, teostatakse samuti n korda, kus n on loendi elementide koguarv.
Seetõttu on hukkamiste arv (n * n), mida saab väljendada ka kui O (n 2 ).
Valiku sortimisel on kolm keerukuse kategooriat, nimelt;
- Halvimal juhul - siin on esitatud loetelu kahanevas järjekorras. Algoritm teostab maksimaalse hukkamiste arvu, mis on väljendatud kui [Big-O] O (n 2 )
- Parimal juhul - see juhtub siis, kui esitatud loend on juba sorteeritud. Algoritm teostab minimaalse hukkamiste arvu, mis on väljendatud [Big-Omega] Ω (n 2 )
- Keskmine juhtum - see juhtub siis, kui loend on juhuslikus järjekorras. Keskmist keerukust väljendatakse [suurteeta] ⊝ (n 2 )
Valiku sortimisel on ruumi keerukus O (1), kuna see nõuab väärtuste vahetamiseks ühte ajalist muutujat.
Millal kasutada valiku sortimist?
Valikusorte on kõige parem kasutada siis, kui soovite:
- Peate sortima väikese üksuste loendi kasvavas järjekorras
- Kui väärtuste vahetamise hind on ebaoluline
- Seda kasutatakse ka siis, kui peate veenduma, et kõik loendis olevad väärtused on kontrollitud.
Valiku sortimise eelised
Järgnevad on valiku sortimise eelised
- See toimib väga hästi väikestes nimekirjades
- See on kohapealne algoritm. Sortimiseks ei vaja see palju ruumi. Ajalise muutuja hoidmiseks on vaja ainult ühte lisaruumi.
- See toimib hästi juba sorteeritud üksuste puhul.
Valiku sorteerimise puudused
Järgnevad on valiku sorteerimise puudused.
- See toimib halvasti, kui töötate tohutute nimekirjade kallal.
- Sorteerimise käigus tehtud korduste arv on n-ruut, kus n on loendi elementide koguarv.
- Teiste algoritmide, näiteks kiirsordi, toimivus on parem kui valiku sortimisel.
Kokkuvõte:
- Valiku sortimine on kohapealne võrdlusalgoritm, mida kasutatakse juhusliku loendi järjestamiseks järjestatud loendisse. Selle ajaline keerukus on O (n 2 )
- Nimekiri on jagatud kahte ossa, sorditud ja sortimata. Minimaalne väärtus valitakse sortimata jaotisest ja paigutatakse sorteeritud sektsiooni.
- Seda asja korratakse seni, kuni kõik üksused on sorteeritud.
- Pseudokoodi rakendamine Python 3-s hõlmab silmuste jaoks kahe kasutamist ja lausete kasutamist, et kontrollida, kas vahetamine on vajalik
- Aja keerukus mõõdab loendi sortimiseks vajalike toimingute arvu.
- Halvima aja keerukus juhtub siis, kui loend on kahanevas järjekorras. Selle ajaline keerukus on [Big-O] O (n 2 )
- Parima aja keerukus juhtub siis, kui loend on juba kasvavas järjekorras. Selle ajaline keerukus on [Big-Omega] Ω (n 2 )
- Keskmine juhtumi keerukus juhtub siis, kui loend on juhuslikus järjekorras. Selle ajaline keerukus on [suurteeta] ⊝ (n 2 )
- Valiku sortimist saab kõige paremini kasutada siis, kui teil on sortimiseks väike üksuste loend, väärtuste vahetamise maksumus pole oluline ja kõigi väärtuste kontrollimine on kohustuslik.
- Valikusortimine ei toimi suurtes loendites hästi
- Muude sortimisalgoritmide, näiteks kiirsordi, toimivus on parem kui valiku sortimisel.