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

Mikä on a Bubble Lajittele?

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

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 sinä tulet oppimaan:

Toteuttamalla Bubble Lajittelualgoritmi

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

Ongelma

Tavaraluettelo annetaan satunnaisessa järjestyksessä, ja haluamme järjestää tavarat järjestyksessä

Harkitse seuraavaa luetteloa:

[21,6,9,33,3]

ratkaisu

Toista luetteloa vertaamalla kahta vierekkäistä elementtiä ja vaihtamalla 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) Hanki elementtien kokonaismäärä. Hanki annetussa luettelossa olevien kohteiden kokonaismäärä

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

Vaihe 3) Suorita sisäiset siirrot (n – 1) kertaa ulommalle läpimenolle 1. Hanki ensimmäisen elementin arvo ja vertaa sitä toiseen arvoon. Jos toinen arvo on pienempi kuin ensimmäinen arvo, vaihda paikkoja

Vaihe 4) Toista vaihetta 3, kunnes saavutat ulomman kulman (n – 1). Hanki seuraava elementti luettelosta ja toista vaiheessa 3 suoritettu prosessi, kunnes kaikki arvot on asetettu oikeaan nousevaan järjestykseen.

Vaihe 5) Palauta tulos, kun kaikki siirrot on tehty. Palauta lajitellun luettelon tulokset

Vaihe 6) Optimoi algoritmi

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 seuraavilla vaiheilla

Vaihe 1) Luo lippumuuttuja, joka valvoo, onko sisäisessä silmukassa tapahtunut vaihtoa

Vaihe 2) Jos arvot ovat vaihtaneet paikkoja, jatka seuraavaan iteraatioon

Vaihe 3) Jos edut eivät ole vaihtaneet paikkoja, päätä sisäsilmukka ja jatka ulompaa silmukkaa.

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

Visuaalinen esitys

Kun annetaan luettelo viidestä elementistä, seuraavat kuvat havainnollistavat, kuinka kuplalajittelu iteroituu arvojen läpi lajitettaessa niitä

Seuraava kuva näyttää lajittelemattoman luettelon

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 paikan, jossa on 6, kun taas 6 ottaa paikan, jossa oli 21

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

Vaihe 2)

Arvoja 21 ja 9 verrataan.

21 on suurempi kuin 9, joten vaihdamme 21:n ja 9:n paikat

Uusi lista on nyt kuten edellä

Vaihe 3)

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

Arvo 33 on suurempi kuin 21, joten vaihtoa ei tapahdu.

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 luettelo on kuten yllä oleva

Toinen iteraatio

Uusi luettelo toisen iteroinnin jälkeen on seuraava

Kolmas iteraatio

Uusi luettelo kolmannen iteraation jälkeen on seuraava

Neljäs iteraatio

Uusi lista neljännen iteraation jälkeen 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

[6, 9, 21, 3, 33]

Koodin selitys

Selitys asialle Python Bubble Järjestä ohjelmakoodi seuraavasti

TÄSSÄ,

Määrittää funktion bubbleSort, joka hyväksyy parametrin theSeq. Koodi ei tulosta mitään.
Hakee taulukon pituuden ja antaa arvon muuttujalle n. Koodi ei tulosta mitään
Käynnistää for-silmukan, joka suorittaa kuplalajittelualgoritmin (n – 1) kertaa. Tämä on ulompi silmukka. Koodi ei tulosta mitään
Määrittää lippumuuttujan, jota käytetään määrittämään, onko vaihto tapahtunut vai ei. Tämä on optimointitarkoituksiin. Koodi ei tulosta mitään
Aloittaa sisäisen silmukan, joka vertaa kaikkia luettelon arvoja ensimmäisestä viimeiseen. Koodi ei tulosta mitään.
Käyttää if-lausetta tarkistaakseen, onko vasemmalla puolella oleva arvo suurempi kuin välittömän oikean puolen arvo. Koodi ei tulosta mitään.
Määrittää Seq[j]:n arvon aikamuuttujalle tmp, jos ehdon arvo on tosi. Koodi ei tulosta mitään
Seq[j + 1]:n arvo määrätään sekvenssin[j] paikkaan. Koodi ei tulosta mitään
Muuttujan tmp arvo on asetettu asentoon theSeq[j + 1]. Koodi ei tulosta mitään
Lippumuuttujalle annetaan arvo 1 osoittamaan, että vaihto on tapahtunut. Koodi ei tulosta mitään
Käyttää if-käskyä tarkistaakseen, onko muuttujan lipun arvo 0. Koodi ei tulosta mitään
Jos arvo on 0, kutsumme katkeamislausetta, joka astuu ulos sisäisestä silmukasta.
Palauttaa theSeq:n arvon sen lajittelun jälkeen. Koodi tulostaa lajitellun luettelon.
Määrittää muuttujan el, joka sisältää luettelon satunnaisluvuista. Koodi ei tulosta mitään.
Määrittää funktion bubbleSort arvon muuttujan tulokselle.
Tulostaa muuttujan tuloksen arvon.

Bubblerilaisia etuja

Seuraavassa on joitain kuplalajittelualgoritmin etuja

Se on helppo ymmärtää
Se toimii erittäin hyvin, kun luettelo 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 joitain kuplalajittelualgoritmin haittoja

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

Monimutkaisuusanalyysi Bubble Lajittele

Monimutkaisuutta on kolmea tyyppiä:

1) Lajittelun monimutkaisuus

Lajittelun monimutkaisuutta käytetään ilmaisemaan luettelon lajitteluun kuluva suoritusaika ja tila. Kuplalajittelu tekee (n – 1) iteraatioita listan lajittelemiseksi, missä n on listan elementtien 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 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 esitetään muodossa [Big-theta] ⊝(n²)

3) Tilan monimutkaisuus

Tilan monimutkaisuus mittaa luettelon lajitteluun tarvittavan lisätilan määrää. Kuplalajittelu vaatii vain yhden (1) lisätilan arvojen vaihtamiseen käytettävälle aikamuuttujalle. Siksi sen tilakompleksisuus on O (1).

Yhteenveto

Kuplalajittelualgoritmi toimii vertaamalla kahta vierekkäistä arvoa ja vaihtamalla niitä, jos vasemmalla oleva arvo on pienempi kuin oikealla oleva arvo.
Kuplalajittelualgoritmin toteuttaminen on suhteellisen helppoa Python. Tarvitset vain silmukoille ja if-lauseille.
Ongelma, jonka kuplalajittelualgoritmi ratkaisee, on ottaa satunnainen luettelo kohteista ja muuttaa se järjestetyksi luetteloksi.
Tietorakenteen kuplalajittelualgoritmi toimii parhaiten, kun luettelo on jo lajiteltu, koska se suorittaa minimaalisen määrän iteraatioita.
Kuplalajittelualgoritmi ei toimi hyvin, kun luettelo on käänteisessä järjestyksessä.
Bubbler-lajittelun aikamonimutkaisuus on O (n²) ja avaruuden monimutkaisuus O (1)
Bubbler lajittelualgoritmi soveltuu parhaiten akateemisiin tarkoituksiin, ei tosielämän sovelluksiin.
Optimoitu kuplalajittelu tekee algoritmista tehokkaamman ohittamalla turhat iteraatiot tarkistettaessa jo lajiteltuja arvoja.

Saatat tykätä: