Valinnan lajittelu: Algoritmi selitetty Python Koodiesimerkki

Mikä on valintalajittelu?

VALINTA LAJITTELU on vertailulajittelualgoritmi, jota käytetään lajittelemaan satunnainen luettelo kohteista nousevaan järjestykseen. Vertailu ei vaadi paljon ylimääräistä tilaa. Se vaatii vain yhden ylimääräisen muistitilan aikamuuttujalle.

Tätä kutsutaan nimellä paikallaan lajittelu. Valintalajittelun aikamonimutkaisuus on O(n²) jossa n on luettelon kohteiden kokonaismäärä. Aikamonimutkaisuus mittaa luettelon lajitteluun tarvittavien iteraatioiden määrää. Luettelo on jaettu kahteen osioon: Ensimmäinen luettelo sisältää lajitellut kohteet, kun taas toinen luettelo sisältää lajittelemattomat kohteet.

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

Miten valintalajittelu toimii?

Lajittelemattoman osion ensimmäistä kohdetta verrataan kaikkiin oikealla oleviin arvoihin sen tarkistamiseksi, onko se pienin arvo. Jos se ei ole minimiarvo, sen sijainti vaihdetaan minimiarvoon.

esimerkki

• Jos esimerkiksi minimiarvon indeksi on 3, indeksin 3 elementin arvo sijoitetaan indeksiin 0, kun taas indeksissä 0 ollut arvo sijoitetaan indeksiin 3. Jos lajittelemattoman osion ensimmäinen elementti on vähimmäisarvon, niin se palauttaa asemansa.
• Elementti, joka on määritetty minimiarvoksi, siirretään sitten vasemmalla olevaan osioon, joka on lajiteltu luettelo.
• Osioidulla puolella on nyt yksi elementti, kun taas osittamattomalla puolella on (n – 1) elementtiä, missä n on listan elementtien kokonaismäärä. Tämä prosessi toistetaan yhä uudelleen, kunnes kaikkia kohteita on verrattu ja lajiteltu niiden arvojen perusteella.

Ongelman määrittely

Luettelo elementeistä, jotka ovat satunnaisessa järjestyksessä, on lajiteltava nousevaan järjestykseen. Harkitse seuraavaa luetteloa esimerkkinä.

[21,6,9,33,3]

Yllä oleva luettelo tulee lajitella seuraavien tulosten saamiseksi

[3,6,9,21,33]

Ratkaisu (algoritmi)

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

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

Vaihe 3) Valitse vähimmäisarvo osittamattomasta osiosta ja sijoita se lajiteltuun osioon.

Vaihe 4) Toista prosessi (n – 1) kertaa, kunnes kaikki luettelon elementit on järjestetty.

Visuaalinen esitys

Kun annetaan viiden elementin luettelo, seuraavat kuvat havainnollistavat, kuinka valintalajittelualgoritmi toistuu arvojen läpi lajitellessaan niitä.

Seuraava kuva näyttää lajittelemattoman luettelon

Vaihe 1)

Ensimmäistä arvoa 21 verrataan muihin arvoihin sen tarkistamiseksi, onko se pienin arvo.

3 on minimiarvo, joten paikat 21 ja 3 vaihdetaan. Vihreällä taustalla olevat arvot edustavat luettelon lajiteltua osiota.

Vaihe 2)

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

Arvo 6 on minimiarvo, joten se säilyttää asemansa.

Vaihe 3)

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

Arvo 9 on pienin arvo, joten se säilyttää asemansa lajitetussa osiossa.

Vaihe 4)

Arvoa 33 verrataan muihin arvoihin.

Arvo 21 on pienempi kuin 33, joten paikat vaihdetaan yllä olevan uuden listan tuottamiseksi.

Vaihe 5)

Meillä on vain yksi arvo jäljellä osittamattomassa luettelossa. Siksi se on jo lajiteltu.

Lopullinen lista on samanlainen kuin yllä olevassa kuvassa.

Valinta Lajittele ohjelma käyttäen Python 3

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

def selectionSort( itemsList ):
    n = len( itemsList )
    for i in range( n - 1 ): 
        minValueIndex = i

        for j in range( i + 1, n ):
            if itemsList[j] < itemsList[minValueIndex] :
                minValueIndex = j

        if minValueIndex != i :
            temp = itemsList[i]
            itemsList[i] = itemsList[minValueIndex]
            itemsList[minValueIndex] = temp

    return itemsList


el = [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ä koodin selitys:

1. Määrittää toiminnon nimeltä selectionSort
2. Hakee luettelon elementtien kokonaismäärän. Tarvitsemme tätä määrittääksemme suoritettavien siirtojen lukumäärän arvojen vertailussa.
3. Ulompi silmukka. Käyttää silmukkaa listan arvojen iterointiin. Iteraatioiden määrä on (n – 1). Arvo n on 5, joten (5 – 1) antaa meille 4. Tämä tarkoittaa, että ulommat iteraatiot suoritetaan 4 kertaa. Jokaisessa iteraatiossa muuttujan i arvo määrätään muuttujalle minValueIndex
4. Sisäinen silmukka. Käyttää silmukkaa vertaamaan vasemmanpuoleisinta arvoa muihin oikean puolen arvoihin. Arvo j:lle ei kuitenkaan ala indeksistä 0. Se alkaa arvosta (i + 1). Tämä sulkee pois arvot, jotka on jo lajiteltu, joten keskitymme tuotteisiin, joita ei ole vielä lajiteltu.
5. Etsii vähimmäisarvon lajittelemattomasta luettelosta ja sijoittaa sen oikeaan paikkaan
6. Päivittää minValueIndexin arvon, kun vaihtoehto on tosi
7. Vertaa indeksilukujen minValueIndex ja i arvoja nähdäkseen, eivätkö ne ole yhtä suuret
8. Vasemmanpuoleisin arvo on tallennettu ajalliseen muuttujaan
9. Alempi arvo oikealta ottaa ensimmäisen aseman
10. Temporaaliarvoon tallennettu arvo tallennetaan asemaan, joka oli aiemmin minimiarvon hallussa
11. Palauttaa lajitellun luettelon funktiotuloksena
12. Luo listan, jossa on satunnaislukuja
13. Tulosta lajiteltu lista sen jälkeen, kun olet kutsunut lajittelufunktion valinnan, joka ohittaa parametrina el.

Aika monimutkaisuus Valinnan Lajittelu

Lajittelun monimutkaisuutta käytetään ilmaisemaan, kuinka monta suorituskertaa luettelon lajitteluun kuluu. Toteutuksessa on kaksi silmukkaa.

Ulompi silmukka, joka poimii arvot yksitellen listasta, suoritetaan n kertaa, missä n on listan arvojen kokonaismäärä.

Sisäinen silmukka, joka vertaa ulkoisen silmukan arvoa muihin arvoihin, suoritetaan myös n kertaa, missä n on listan elementtien kokonaismäärä.

Siksi suoritusten lukumäärä on (n * n), joka voidaan myös ilmaista muodossa O(n²).

Valintalajittelussa on kolme monimutkaisuusluokkaa, nimittäin;

• Pahimmassa tapauksessa – tässä annettu luettelo on laskevassa järjestyksessä. Algoritmi suorittaa maksimimäärän suorituksia, joka ilmaistaan ​​[Big-O] O(n²)
• Paras tapaus – tämä tapahtuu, kun annettu luettelo on jo lajiteltu. Algoritmi suorittaa minimimäärän suorituksia, joka ilmaistaan ​​[Big-Omega] ?(n²)
• Keskimääräinen tapaus – tämä tapahtuu, kun luettelo on satunnaisessa järjestyksessä. Keskimääräinen monimutkaisuus ilmaistaan ​​[Big-theta] ?(n²)

Valintalajittelun tilamonimutkaisuus on O(1), koska se vaatii yhden aikamuuttujan, jota käytetään arvojen vaihtamiseen.

Milloin valintalajittelua käytetään?

Valintalajittelu on parasta käyttää, kun haluat:

• Sinun on lajiteltava pieni luettelo kohteista nousevaan järjestykseen
• Kun arvojen vaihtokustannukset ovat merkityksettömät
• Sitä käytetään myös silloin, kun sinun on varmistettava, että kaikki luettelon arvot on tarkistettu.

Valikoimalajittelun edut

Seuraavat ovat valintalajittelun edut

• Se toimii erittäin hyvin pienillä listoilla
• Se on paikallaan oleva algoritmi. Se ei vaadi paljon tilaa lajitteluun. Aikamuuttujan pitämiseen tarvitaan vain yksi lisätila.
• Se toimii hyvin kohteissa, jotka on jo lajiteltu.

Valikoimalajittelun haitat

Seuraavat ovat valintalajittelun haitat.

• Se toimii huonosti käytettäessä suuria listoja.
• Lajittelun aikana tehtyjen iteraatioiden määrä on n-neliö, jossa n on listan elementtien kokonaismäärä.
• Muilla algoritmeilla, kuten pikalajittelulla, on parempi suorituskyky verrattuna valintalajitteluun.

Yhteenveto

• Valintalajittelu on paikallaan oleva vertailualgoritmi, jota käytetään satunnaisluettelon lajitteluun järjestetyksi luetteloksi. Sen aikamonimutkaisuus on O(n²)
• Luettelo on jaettu kahteen osaan, lajiteltuun ja lajittelemattomaan. Minimiarvo poimitaan lajittelemattomasta osiosta ja sijoitetaan lajiteltuun osuuteen.
• Tätä toistetaan, kunnes kaikki kohteet on lajiteltu.
• Pseudokoodin käyttöönotto sisään Python 3 sisältää kahden for-silmukan ja if-lauseiden käyttämisen sen tarkistamiseksi, onko vaihto tarpeen
• Aika monimutkaisuus mittaa luettelon lajitteluun tarvittavien vaiheiden määrää.
• Pahimman mahdollisen ajan monimutkaisuus tapahtuu, kun luettelo on laskevassa järjestyksessä. Sen aikakompleksisuus on [Big-O] O(n²)
• Parhaassa tapauksessa aika monimutkaisuus tapahtuu, kun luettelo on jo nousevassa järjestyksessä. Sen aikamonimutkaisuus on [Big-Omega] ?(n²)
• Keskimääräinen tapauksen aika monimutkaisuus tapahtuu, kun luettelo on satunnaisessa järjestyksessä. Sen aikamonimutkaisuus on [Big-theta] ?(n²)
• Valintalajittelu on parasta käyttää, kun sinulla on pieni lista lajiteltavista kohteista, arvojen vaihtamisen hinnalla ei ole väliä ja kaikkien arvojen tarkistaminen on pakollista.
• Valintalajittelu ei toimi hyvin suurilla listoilla
• Muilla lajittelualgoritmeilla, kuten pikalajittelulla, on parempi suorituskyky verrattuna valintalajitteluun.