Bubble Lajittele algoritmi Python käyttämällä List Esimerkkiä

Mikä on a Bubble Lajittele?

Bubble Lajittele on lajittelualgoritmi, jota käytetään luettelokohteiden lajittelemiseen nousevaan järjestykseen vertaamalla kahta vierekkäistä arvoa. Jos ensimmäinen arvo on suurempi kuin toinen arvo, ensimmäinen arvo ottaa toisen arvon sijainnin, kun taas toinen arvo ottaa ensimmäisen arvon sijainnin. Jos ensimmäinen arvo on pienempi kuin toinen arvo, vaihtoa ei tehdä.ping on tehty.

Tätä prosessia toistetaan, kunnes kaikkia luettelon arvoja on verrattu ja vaihdettu tarvittaessa. Jokaista iteraatiota kutsutaan yleensä passiksi. Kulkujen määrä kuplalajittelussa on yhtä suuri kuin luettelon elementtien määrä miinus yksi.

Tässä Bubble Lajittelu Python oppitunti opit sen ratkaiseman ongelman, sen optimoidun muodon, vaiheittaisen visuaalisen läpikäynnin, toimivan Python ohjelma ja sen suorituskykyominaisuudet.

Toteuttamalla Bubble Lajittelualgoritmi

Jaamme toteutuksen kolmeen (3) vaiheeseen: ongelmaan, ratkaisuun ja algoritmiin, jota voimme käyttää koodin kirjoittamiseen mille tahansa kielelle.

Ongelma

Kohdeluettelo annetaan satunnaisessa järjestyksessä, ja haluaisimme järjestää kohteet järjestelmällisesti.

Harkitse seuraavaa luetteloa:

[21, 6, 9, 33, 3]

ratkaisu

Käy lista läpi vertaamalla kahta vierekkäistä elementtiä ja vaihtamalla ne.ping niitä, jos ensimmäinen arvo on suurempi kuin toinen arvo.

Tuloksen pitäisi olla seuraava:

[3, 6, 9, 21, 33]

algoritmi

Kuplalajittelualgoritmi toimii seuraavasti:

Vaihe 1) Hae elementtien kokonaismäärä. Hae annetun listan kohteiden kokonaismäärä.

Vaihe 2) Määritä suoritettavien ulompien ylikulkujen lukumäärä (n – 1). Sen pituus on lista miinus yksi.

Vaihe 3) Suorita sisäkierrokset (n – 1) kertaa ulkokierrolla 1. Hae ensimmäisen elementin arvo ja vertaa sitä toiseen arvoon. Jos toinen arvo on pienempi kuin ensimmäinen arvo, vaihda paikat.

Vaihe 4) Toista vaiheen 3 läpimenot, kunnes saavutat ulomman läpimenon (n – 1). Hae listan seuraava elementti ja toista sitten vaiheessa 3 suoritettu prosessi, kunnes kaikki arvot on sijoitettu oikeaan nousevaan järjestykseen.

Vaihe 5) Palauta tulos, kun kaikki läpikäynnit on tehty. Palauta lajitellun listan tulokset.

Vaihe 6) Optimointialgoritmi.

Vältä tarpeettomia sisäisiä siirtoja, jos luettelo tai viereiset arvot on jo lajiteltu. Jos esimerkiksi annettu luettelo sisältää jo elementtejä, jotka on lajiteltu nousevaan järjestykseen, voimme katkaista silmukan aikaisin.

optimoitu Bubble Lajittelualgoritmi

Oletuksena kuplalajittelun algoritmi Python vertaa kaikkia luettelon kohteita riippumatta siitä, onko luettelo jo lajiteltu vai ei. Jos annettu lista on jo lajiteltu, kaikkien arvojen vertailu on ajan ja resurssien hukkaa.

Kuplalajittelun optimointi auttaa välttämään tarpeettomia iteraatioita ja säästämään aikaa ja resursseja.

Jos esimerkiksi ensimmäinen ja toinen alkio on jo lajiteltu, muita arvoja ei tarvitse iteroida. Iterointi lopetetaan ja seuraava aloitetaan, kunnes prosessi on valmis alla olevan kuvan mukaisesti Bubble Lajittele esimerkki.

Optimointi tehdään seuraavien vaiheiden avulla:

Vaihe 1) Luo lippumuuttuja, joka valvoo mahdollisia swappejaping on tapahtunut sisäkierroksella.

Vaihe 2) Jos arvot ovat vaihtaneet paikkaa, jatka seuraavaan iteraatioon.

Vaihe 3) Jos arvot eivät ole vaihtaneet paikkoja, lopeta sisempi silmukka ja jatka ulompaa silmukkaa.

Optimoitu kuplalajittelu on tehokkaampaa, koska se suorittaa vain tarvittavat vaiheet ja ohittaa tarpeettomat.

Visuaalinen esitys

Seuraavat kuvat havainnollistavat, kuinka kuplalajittelu käy läpi arvot lajittelun aikana, kun annetaan viiden elementin luettelo.

Seuraava kuva näyttää lajittelemattoman listan:

Ensimmäinen iteraatio

Vaihe 1)

Arvoja 21 ja 6 verrataan sen tarkistamiseksi, kumpi on suurempi kuin toinen.

21 on suurempi kuin 6, joten 21 ottaa 6:n täyttämän paikan, kun taas 6 ottaa 21:n täyttämän paikan.

Muokattu luettelomme näyttää nyt samalta kuin yllä oleva.

Vaihe 2)

Arvoja 21 ja 9 verrataan.

Luku 21 on suurempi kuin 9, joten vaihdamme lukujen 21 ja 9 paikat.

Uusi lista on nyt kuten yllä.

Vaihe 3)

Arvoja 21 ja 33 verrataan suuremman löytämiseksi.

Arvo 33 on suurempi kuin 21, joten vaihtoa ei tehdä.ping tapahtuu.

Vaihe 4)

Arvoja 33 ja 3 verrataan suuremman löytämiseksi.

Arvo 33 on suurempi kuin 3, joten vaihdamme niiden paikkoja.

Ensimmäisen iteraation lopussa oleva lajiteltu lista on samanlainen kuin yllä.

Toinen iteraatio

Uusi lista toisen iteraation jälkeen on seuraava:

Kolmas iteraatio

Kolmannen kierroksen jälkeen uusi lista on seuraava:

Neljäs iteraatio

Neljännen kierroksen jälkeen uusi lista on seuraava:

Python Esimerkit

Seuraava koodi näyttää kuinka toteuttaa Bubble Lajittele algoritmi Python.

def bubbleSort(theSeq):
    n = len(theSeq)

    for i in range(n - 1):
        flag = 0

        for j in range(n - 1):
            if theSeq[j] > theSeq[j + 1]:
                tmp = theSeq[j]
                theSeq[j] = theSeq[j + 1]
                theSeq[j + 1] = tmp
                flag = 1

        if flag == 0:
            break

    return theSeq

el = [21, 6, 9, 33, 3]
result = bubbleSort(el)
print(result)

Suoritetaan yllä oleva kuplalajitteluohjelma Python tuottaa seuraavat tulokset:

[3, 6, 9, 21, 33]

Code Selitys

Selitys asialle Python BubblLajitteluohjelman koodi on seuraava:

TÄSSÄ,

1. Määrittää funktion bubbleSort, joka hyväksyy parametrin theSeq. Koodi ei tulosta mitään.
2. Hakee taulukon pituuden ja asettaa arvon muuttujalle n. Koodi ei tulosta mitään.
3. Käynnistää for-silmukan, joka suorittaa kuplalajittelualgoritmin (n – 1) kertaa. Tämä on ulompi silmukka. Koodi ei tuota mitään tulosta.
4. Määrittelee lippumuuttujan, jota käytetään sen määrittämiseen, onko vaihto tapahtunut vai ei. Tämä on optimointitarkoituksiin. Koodi ei anna mitään tulosta.
5. Aloittaa sisäisen silmukan, joka vertaa kaikkia luettelon arvoja ensimmäisestä viimeiseen. Koodi ei tulosta mitään.
6. Käyttää if-lausetta tarkistaakseen, onko vasemmalla puolella oleva arvo suurempi kuin välittömän oikean puolen arvo. Koodi ei tulosta mitään.
7. Asettaa theSeq[j]:n arvon ajalliselle muuttujalle tmp, jos ehto on tosi. Koodi ei tuota mitään tulosta.
8. theSeq[j + 1]:n arvo annetaan theSeq[j]:n sijainnille. Koodi ei tuota mitään tulosta.
9. Muuttujan tmp arvo asetetaan kohtaan theSeq[j + 1]. Koodi ei anna tulosta mitään.
10. Lippumuuttujalle annetaan arvo 1 osoituksena siitä, että vaihto on tapahtunut. Koodi ei anna tulosta mitään.
11. Käyttää if-lauseketta tarkistaakseen, onko muuttujan flag arvo 0. Koodi ei tulosta mitään.
12. Jos arvo on 0, kutsumme katkeamislausetta, joka astuu ulos sisäisestä silmukasta.
13. Palauttaa theSeq:n arvon sen lajittelun jälkeen. Koodi tulostaa lajitellun luettelon.
14. Määrittää muuttujan el, joka sisältää luettelon satunnaisluvuista. Koodi ei tulosta mitään.
15. Määrittää funktion bubbleSort arvon muuttujan tulokselle.
16. Tulostaa muuttujan tuloksen arvon.

Bubblerilaisia ​​etuja

Seuraavassa on joitakin kuplalajittelualgoritmin etuja:

• Se on helppo ymmärtää.
• Se toimii erittäin hyvin, kun lista on jo tai melkein lajiteltu.
• Se ei vaadi laajaa muistia.
• Algoritmin koodin kirjoittaminen on helppoa.
• Tilavaatimukset ovat minimaaliset muihin lajittelualgoritmeihin verrattuna.

Bubble lajitella haitat

Seuraavassa on joitakin kuplalajittelualgoritmin haittoja:

• Se ei toimi hyvin, kun lajitellaan suuria listoja. Se vie liikaa aikaa ja resursseja.
• Sitä käytetään enimmäkseen akateemisiin tarkoituksiin eikä tosielämän sovelluksiin.
• Listan lajitteluun tarvittavien vaiheiden määrä on luokkaa n².

Monimutkaisuusanalyysi Bubble Lajittele

Monimutkaisuutta on kolmea tyyppiä:

1) Lajittelun monimutkaisuus

Lajittelukompleksisuutta käytetään ilmaisemaan listan lajitteluun tarvittava suoritusaika ja -tila. Kuplalajittelussa lista lajitellaan (n – 1) iteraatiota, missä n on listan alkioiden kokonaismäärä.

2) Aika monimutkaisuus

Kuplalajittelun aikamonimutkaisuus on O(n²).

Aika monimutkaisuus voidaan luokitella seuraavasti:

• 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äistä kompleksisuutta esitetään muodossa [Big-theta] ⊝(n²).

3) Tilan monimutkaisuus

Tilakompleksisuus mittaa listan lajitteluun tarvittavan lisätilan määrää. Kuplalajittelu vaatii vain yhden (1) lisätilan swapissa käytettävälle ajalliselle muuttujalle.ping arvoja. Siksi sen avaruuskompleksisuus on O(1).

UKK