Valintalajittelu: Algoritmi selitetään Python-koodiesimerkillä

Sisällysluettelo:

Anonim

Mikä on valintalajittelu?

SELECTION SORT on vertailulajittelualgoritmi, jota käytetään lajittelemaan satunnaisluettelo kohteista nousevassa järjestyksessä. Vertailu ei vaadi paljon ylimääräistä tilaa. Aikamuuttujalle se vaatii vain yhden ylimääräisen muistitilan.

Tätä kutsutaan paikan päällä tapahtuvaksi lajitteluksi. Valintalajittelun aikakompleksi on O (n 2 ), jossa n on luettelon alkioiden kokonaismäärä. Ajan monimutkaisuus mittaa luettelon lajittelun edellyttämien iteraatioiden määrää. Luettelo on jaettu kahteen osioon: Ensimmäinen luettelo sisältää lajiteltuja kohteita, kun taas toinen luettelo sisältää lajittelemattomia kohteita.

Lajiteltu luettelo on oletuksena tyhjä, ja lajittelematon luettelo sisältää kaikki elementit. Lajittelemattomasta luettelosta skannataan sitten vähimmäisarvo, joka sitten sijoitetaan lajiteltuun luetteloon. Tätä prosessia toistetaan, kunnes kaikkia arvoja on verrattu ja lajiteltu.

Tässä algoritmin opetusohjelmassa opit:

  • Mikä on valintalajittelu?
  • Kuinka valintalajittelu toimii?
  • Ongelman määrittely
  • Ratkaisu (algoritmi)
  • Visuaalinen esitys
  • Lajitteluohjelma Python 3: lla
  • Koodin selitys
  • Ajan monimutkaisuus valinnan lajittelussa
  • Milloin valintalajittelua käytetään?
  • Valintalajittelun edut
  • Valintalajittelun haitat

Kuinka valintalajittelu toimii?

Lajittelemattoman osion ensimmäistä kohdetta verrataan kaikkiin arvoihin oikealla puolella sen tarkistamiseksi, onko se vähimmäisarvo. Jos se ei ole vähimmäisarvo, sen sijainti vaihdetaan minimiarvoon.

Esimerkki:

  • Esimerkiksi, jos vähimmäisarvon indeksi on 3, indeksillä 3 olevan elementin arvo sijoitetaan indeksiin 0, kun taas indeksillä 0 ollut arvo sijoitetaan indeksiin 3. Jos lajittelemattoman osion ensimmäinen elementti on pienimmän arvon, sitten se palauttaa sijaintinsa.
  • Minimiarvoksi määritetty elementti siirretään sitten vasemmalla puolella olevaan osioon, joka on lajiteltu luettelo.
  • Osioidulla puolella on nyt yksi elementti, kun taas osioimattomalla puolella on (n - 1) elementtiä, joissa n on luettelon elementtien kokonaismäärä. Tätä prosessia toistetaan yhä uudelleen, kunnes kaikkia kohteita on verrattu ja lajiteltu niiden arvojen perusteella.

Ongelman määrittely

Luettelo satunnaisessa järjestyksessä olevista elementeistä on lajiteltava nousevassa järjestyksessä. Tarkastellaan seuraavaa luetteloa esimerkkinä.

[21,6,9,33,3]

Yllä oleva luettelo tulisi lajitella tuottamaan seuraavat tulokset

[3,6,9,21,33]

Ratkaisu (algoritmi)

Vaihe 1) Hanki n: n arvo, joka on taulukon koko

Vaihe 2) Jaa luettelo lajiteltuihin ja lajittelemattomiin osioihin. Lajiteltu osa on aluksi tyhjä, kun taas lajittelematon osa sisältää koko luettelon

Vaihe 3) Valitse vähimmäisarvo osioimattomasta osiosta ja aseta se lajiteltuun osioon.

Vaihe 4) Toista prosessi (n - 1) kertaa, kunnes kaikki luettelon elementit on lajiteltu.

Visuaalinen esitys

Seuraavat kuvat kuvaavat viiden elementin luetteloa, kuinka valintalajittelualgoritmi iteroi arvojen läpi lajitellessaan niitä.

Seuraava kuva näyttää lajittelemattoman luettelon

Vaihe 1)

Ensimmäistä arvoa 21 verrataan muihin arvoihin sen tarkistamiseksi, onko se vähimmäisarvo.

3 on vähimmäisarvo, joten 21: n ja 3: n paikat vaihdetaan. Vihreällä taustalla olevat arvot edustavat luettelon lajiteltuja osioita.

Vaihe 2)

Arvoa 6, joka on lajittelemattoman osion ensimmäinen elementti, verrataan muihin arvoihin sen selvittämiseksi, onko pienempi arvo olemassa

Arvo 6 on vähimmäisarvo, joten se säilyttää asemansa.

Vaihe 3)

Lajittelemattoman luettelon ensimmäistä elementtiä, jonka arvo on 9, verrataan muihin arvoihin sen tarkistamiseksi, onko se vähimmäisarvo.

Arvo 9 on vähimmäisarvo, joten se säilyttää asemansa lajitellussa osiossa.

Vaihe 4)

Arvoa 33 verrataan muihin arvoihin.

Arvo 21 on alle 33, joten paikat vaihdetaan yllä olevan uuden luettelon tuottamiseksi.

Vaihe 5)

Meillä on vain yksi arvo jakamattomassa luettelossa. Siksi se on jo lajiteltu.

Lopullinen luettelo on kuin yllä olevassa kuvassa.

Lajitteluohjelma Python 3: lla

Seuraava koodi näyttää valintalajittelun toteutuksen käyttämällä Python 3: ta

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))

Suorita yllä oleva koodi tuottaa seuraavat tulokset

[3, 6, 9, 21, 33]

Koodin selitys

Koodin selitys on seuraava

Tässä on koodin selitys:

  1. Määrittää toiminnon nimeltä SelectionSort
  2. Hakee luettelon elementtien kokonaismäärän. Tarvitsemme tämän määritettäessä suoritettavien läpilyöntien määrää verrattaessa arvoja.
  3. Ulompi silmukka. Käyttää silmukkaa toistamaan luettelon arvot. Toistojen lukumäärä on (n - 1). N: n arvo on 5, joten (5 - 1) antaa meille 4. Tämä tarkoittaa, että ulommat iteraatiot suoritetaan 4 kertaa. Kussakin iteraatiossa muuttujan i arvo määritetään muuttujalle minValueIndex
  4. Sisäinen silmukka. Vertaa silmukkaa vasemmanpuoleiseen arvoon muihin oikeanpuoleisiin arvoihin. J: n arvo ei kuitenkaan ala indeksistä 0. Se alkaa arvosta (i + 1). Tämä sulkee pois arvot, jotka on jo lajiteltu siten, että keskitymme kohteisiin, joita ei ole vielä lajiteltu.
  5. Hakee vähimmäisarvon lajittelemattomasta luettelosta ja sijoittaa sen oikeaan paikkaan
  6. Päivittää minValueIndex-arvon, kun vaihdon ehto on tosi
  7. Vertaa indeksilukujen minValueIndex ja i arvoja nähdäksesi, eivätkö ne ole yhtä suuria
  8. Vasemmanpuoleisin arvo tallennetaan ajalliseen muuttujaan
  9. Oikealta puolelta tuleva alempi arvo ottaa ensimmäisen sijainnin
  10. Aika-arvoon tallennettu arvo tallennetaan sijaintiin, jota aikaisemmin pidettiin vähimmäisarvolla
  11. Palauttaa lajitellun luettelon funktion tuloksena
  12. Luo luettelon el, jolla on satunnaisia ​​numeroita
  13. Tulosta lajiteltu luettelo sen jälkeen kun olet kutsunut valinnan Lajittelu-toiminnon, joka välitetään parametrina el.

Ajan monimutkaisuus valinnan lajittelussa

Lajittelun monimutkaisuutta käytetään ilmaisemaan suoritusaikojen määrä, joka tarvitaan luettelon lajittelemiseen. Toteutuksessa on kaksi silmukkaa.

Ulompi silmukka, joka poimii arvot yksitellen luettelosta, suoritetaan n kertaa, jolloin n on luettelon arvojen kokonaismäärä.

Sisempi silmukka, joka vertaa ulomman silmukan arvoa muihin arvoihin, suoritetaan myös n kertaa, kun n on luettelon elementtien kokonaismäärä.

Siksi teloitusten lukumäärä on (n * n), joka voidaan ilmaista myös O: na (n 2 ).

Valintalajikkeella on kolme monimutkaisuusluokkaa:

  • Pahin tapaus - tässä annettu luettelo on laskevassa järjestyksessä. Algoritmi suorittaa suoritusten enimmäismäärän, joka ilmaistaan ​​muodossa [Big-O] O (n 2 )
  • Paras tapaus - tämä tapahtuu, kun toimitettu luettelo on jo lajiteltu. Algoritmi suorittaa suoritusten vähimmäismäärän, joka ilmaistaan ​​muodossa [Big-Omega] Ω (n 2 )
  • Keskimääräinen tapaus - tämä tapahtuu, kun luettelo on satunnaisessa järjestyksessä. Keskimääräinen monimutkaisuus ilmaistaan ​​[Big-theta] ⊝ (n 2 )

Valintalajikkeella on tilan monimutkaisuus (O), koska se vaatii yhden ajallisen muuttujan, jota käytetään arvojen vaihtamiseen.

Milloin valintalajittelua käytetään?

Valintalajittelua käytetään parhaiten, kun haluat:

  • Sinun on lajiteltava pieni luettelo tuotteista nousevassa järjestyksessä
  • Kun arvojen vaihtamisen kustannukset ovat merkityksettömiä
  • Sitä käytetään myös, kun sinun on varmistettava, että kaikki luettelon arvot on tarkistettu.

Valintalajittelun edut

Seuraavat ovat valintalajittelun edut

  • Se toimii erittäin hyvin pienissä luetteloissa
  • Se on paikalla oleva algoritmi. Se ei vaadi paljon tilaa lajittelua varten. Ainoan muuttujan pitämiseen tarvitaan vain yksi ylimääräinen tila.
  • Se toimii hyvin kohteisiin, jotka on jo lajiteltu.

Valintalajittelun haitat

Seuraavat ovat valintalajittelun haittoja.

  • Se toimii huonosti, kun työskentelet valtavien luetteloiden parissa.
  • Lajittelun aikana tehtyjen iteraatioiden määrä on n-neliö, jossa n on luettelon elementtien kokonaismäärä.
  • Muilla algoritmeilla, kuten pikalajit, on parempi suorituskyky kuin valintalajittelulla.

Yhteenveto:

  • Valintalajittelu on paikan päällä oleva vertailualgoritmi, jota käytetään lajittelemaan satunnaisluettelo järjestettyyn luetteloon. Sen aikakompleksi on O (n 2 )
  • Luettelo on jaettu kahteen osaan, lajiteltu ja lajittelematon. Pienin arvo valitaan lajittelemattomasta osiosta ja sijoitetaan lajiteltuun osioon.
  • Tätä asiaa toistetaan, kunnes kaikki kohteet on lajiteltu.
  • Pseudokoodin käyttöönotto Python 3: ssa edellyttää kahden käyttöä silmukoille ja lausekkeilla tarkistamiseksi, onko vaihto tarpeen
  • Ajan monimutkaisuus mittaa luettelon lajittelun edellyttämien vaiheiden määrää.
  • Pahimmassa tapauksessa ajan monimutkaisuus tapahtuu, kun luettelo on laskevassa järjestyksessä. Sen aikakompleksi on [Big-O] O (n 2 )
  • Paras aika-monimutkaisuus tapahtuu, kun luettelo on jo nousevassa järjestyksessä. Sen aikakompleksisuus on [Big-Omega] Ω (n 2 )
  • Keskimääräinen tapausajan monimutkaisuus tapahtuu, kun luettelo on satunnaisessa järjestyksessä. Sen aikakompleksi on [Big-theta] ⊝ (n 2 )
  • Valintalajittelua voidaan parhaiten käyttää, kun sinulla on pieni luettelo lajiteltavista kohteista, arvojen vaihtamisen kustannuksilla ei ole merkitystä ja kaikkien arvojen tarkistaminen on pakollista.
  • Valintalajittelu ei toimi hyvin valtavissa luetteloissa
  • Muilla lajittelualgoritmeilla, kuten pikalajit, on parempi suorituskyky kuin valintalajittelulla.