Valintalajittelualgoritmi, jossa on Python Code esimerkki

⚡ Älykäs yhteenveto

Valintalajittelu on vertailualgoritmi, joka lajittelee satunnaisen listan nousevaan järjestykseen valitsemalla toistuvasti pienimmän lajittelemattoman arvon ja siirtämällä sen lajiteltuun osioon. Tämä resurssi selittää Python esimerkki ja sen ajallinen monimutkaisuus.

🎯 Perusidea: Valintalajittelu etsii toistuvasti lajittelemattoman osan pienimmän arvon ja siirtää sen lajiteltuun osioon.
🧠 Paikan päällä: Se lajittelee käyttämällä vain yhtä ylimääräistä väliaikaista muuttujaa, jolloin avaruuskompleksisuudeksi tulee O(1).
⏱️ Ajan monimutkaisuus: Se toimii O(n²) ajassa pahimmassa, parhaassa ja keskimääräisessä tapauksessa sisäkkäisten silmukoiden vuoksi.
🐍 Python Esimerkiksi: Lyhyt funktio, jossa on kaksi silmukkaa, vaihtaa minimin paikoilleen, kunnes lista on lajiteltu.
🇧🇷 Paras käyttö: Se sopii pienille listoille, joissa swap-kustannukset ovat alhaiset ja jokainen arvo on tarkistettava.

Lue lisää

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]

Code Selitys

Koodin selitys on seuraava

Tässä on Code selitys:

Määrittää toiminnon nimeltä selectionSort
Hakee luettelon elementtien kokonaismäärän. Tarvitsemme tätä määrittääksemme suoritettavien siirtojen lukumäärän arvojen vertailussa.
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
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.
Etsii vähimmäisarvon lajittelemattomasta luettelosta ja sijoittaa sen oikeaan paikkaan
Päivittää minValueIndex-arvon, kun swap-arvoping ehto on tosi
Vertaa indeksilukujen minValueIndex ja i arvoja nähdäkseen, eivätkö ne ole yhtä suuret
Vasemmanpuoleisin arvo on tallennettu ajalliseen muuttujaan
Alempi arvo oikealta ottaa ensimmäisen aseman
Temporaaliarvoon tallennettu arvo tallennetaan asemaan, joka oli aiemmin minimiarvon hallussa
Palauttaa lajitellun luettelon funktiotuloksena
Luo listan, jossa on satunnaislukuja
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 lista on jo lajiteltu. Algoritmi suorittaa pienimmän mahdollisen määrän suorituksia, joka ilmaistaan muodossa [Big-Omega] Ω(n²)
Keskimääräinen tapaus – tämä tapahtuu, kun lista on satunnaisessa järjestyksessä. Keskimääräinen kompleksisuus ilmaistaan muodossa [Big-theta] Θ(n²)

Valintalajittelun tilavaativuus on O(1), koska se vaatii yhden ajallisen muuttujan, jota käytetään swappiinping arvot.

Milloin valintalajittelua käytetään?

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

Sinun on lajiteltava pieni luettelo kohteista nousevaan järjestykseen
Kun swapin hintaping arvot ovat merkityksettömiä
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.

UKK

Valintalajittelu ei ole perusmuodossaan vakaa, koska swapping Etäiset elementit voivat muuttaa yhtäläisten avainten suhteellista järjestystä. Linkitetyn listan variantti tai huolellinen siirto voi tehdä siitä vakaan, mutta vakiomatriisiversio on epävakaa.

Valintalajittelu skannaa lajittelemattoman osan löytääkseen pienimmän mahdollisen alkion ja vaihtaa sen paikalleen tekemällä vain vähän vaihtoja. Lisäyslajittelu ottaa jokaisen alkion ja siirtää suuremmat lajitellut alkiot oikealle lisätäkseen ne. Lisäyslajittelu on yleensä nopeampi lähes lajitellulle datalle.

Valintalajittelu suorittaa enintään n-1 vaihtoa n alkion listalle, yhden kerrallaan. Tämä pieni vaihtomäärä tekee siitä hyödyllisen silloin, kun muistiin kirjoittaminen on kallista, vaikka se silti suorittaa O(n²) vertailua.

Tekoälyohjaajat voivat tracLajittele valinnat askel askeleelta, animoi jokaisen vaihdon ja testaa ajallisesti monimutkaisuutta. Tämä interaktiivinen palaute auttaa aloittelijoita ymmärtämään, miten minimi valitaan ja siirretään jokaisen kierroksen aikana.

Kyllä. Tekoälykoodausavustajat voivat luoda valintalajittelun useilla kielillä, selittää jokaisen rivin ja ehdottaa tehokkaampia algoritmeja, kuten pikalajittelua, kun syöte kasvaa suureksi. Testaa aina luotu koodi ennen sen käyttöä.