Bubble Sort Algorithm with Python käyttäen luetteloesimerkkiä

Sisällysluettelo:

Anonim

Mikä on kuplalajittelu?

Bubble Sort on lajittelualgoritmi, jota käytetään lajittelemaan luettelokohteet nousevassa järjestyksessä 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. Kuplalajittelun läpikulkujen määrä on yhtä suuri kuin luettelossa olevien elementtien lukumäärä miinus yksi.

Tässä Bubble Sorting in Python -opetusohjelmassa opit:

  • Mikä on kuplalajittelu?
  • Bubble Sort -algoritmin toteuttaminen
  • Optimoitu kuplalajittelualgoritmi
  • Visuaalinen esitys
  • Python-esimerkkejä
  • Koodin selitys
  • Kuplalajittelun edut
  • Kuplalajittelun haitat
  • Bubble Sortin monimutkaisuusanalyysi

Bubble Sort -algoritmin toteuttaminen

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

Ongelma

Luettelo tuotteista annetaan satunnaisessa järjestyksessä, ja haluaisimme järjestää kohteet järjestyksessä

Harkitse seuraavaa luetteloa:

[21,6,9,33,3]

Ratkaisu

Vaihda luettelon läpi vertaamalla kahta vierekkäistä elementtiä ja vaihtamalla niitä, jos ensimmäinen arvo on suurempi kuin toinen arvo.

Tuloksen tulisi olla seuraava:

[3,6,9,21,33]

Algoritmi

Kuplalajittelualgoritmi toimii seuraavasti

Vaihe 1) Hanki elementtien kokonaismäärä. Hanki annettujen luetteloiden kohteiden kokonaismäärä

Vaihe 2) Määritä suoritettavien ulompien läpikulkujen määrä (n - 1). Sen pituus on luettelo miinus yksi

Vaihe 3) Suorita sisäiset läpikulut (n - 1) kertaa ulkoiselle läpikululle 1. Hanki ensimmäisen elementin arvo ja vertaa sitä toiseen arvoon. Jos toinen arvo on pienempi kuin ensimmäinen arvo, vaihda sijainnit

Vaihe 4) Toista vaihe 3, kunnes saavutat ulomman läpikulun (n - 1). Hanki seuraava elementti luettelosta ja toista sitten vaiheessa 3 suoritettu prosessi, kunnes kaikki arvot on asetettu oikeaan nousevaan järjestykseen.

Vaihe 5) Palauta tulos, kun kaikki syötöt on tehty. Palauta lajitellun luettelon tulokset

Vaihe 6) Optimoi algoritmi

Vältä tarpeettomia sisäisiä läpäisyjä, jos luettelo tai viereiset arvot on jo lajiteltu. Esimerkiksi, jos toimitettu luettelo sisältää jo elementtejä, jotka on lajiteltu nousevassa järjestyksessä, voimme katkaista silmukan aikaisin.

Optimoitu kuplalajittelualgoritmi

Oletusarvon mukaan Pythonin kuplalajittelualgoritmi vertaa kaikkia luettelon kohteita riippumatta siitä, onko luettelo jo lajiteltu vai ei. Jos annettu luettelo on jo lajiteltu, kaikkien arvojen vertailu on ajanhukkaa ja resursseja.

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

Esimerkiksi, jos ensimmäinen ja toinen kohde on jo lajiteltu, muita arvoja ei tarvitse toistaa. Iteraatio lopetetaan ja seuraava aloitetaan, kunnes prosessi on valmis, kuten alla olevassa Bubble Sort -esimerkissä on esitetty.

Optimointi tapahtuu seuraavien vaiheiden avulla

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

Vaihe 2) Jos arvot ovat vaihtaneet sijainteja, jatka seuraavaan iterointiin

Vaihe 3) Jos edut eivät ole vaihtaneet sijainteja, lopeta sisempi silmukka ja jatka ulommalla silmukalla.

Optimoitu kuplalajittelu on tehokkaampaa, koska se suorittaa vain tarvittavat vaiheet ja ohittaa ne, joita ei tarvita.

Visuaalinen esitys

Seuraavat kuvat esittävät viiden elementin luettelon, kuinka kupla lajittelee iteroidut arvojen läpi lajitellessaan niitä

Seuraava kuva näyttää lajittelemattoman luettelon

Ensimmäinen iterointi

Vaihe 1)

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

21 on suurempi kuin 6, joten 21 ottaa 6: n käyttämän sijainnin, kun taas 6 on 21: n käyttämän

Muokattu luettelomme näyttää nyt ylläolevalta.

Vaihe 2)

Arvoja 21 ja 9 verrataan.

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

Uusi luettelo on nyt kuten yllä

Vaihe 3)

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

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

Vaihe 4)

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

Arvo 33 on suurempi kuin 3, joten vaihdamme heidän sijaintinsa.

Lajiteltu luettelo ensimmäisen iteraation lopussa on kuin yllä

Toinen iterointi

Uusi luettelo toisen iteraation jälkeen on seuraava

Kolmas iteraatio

Uusi luettelo kolmannen iteraation jälkeen on seuraava

Neljäs iterointi

Uusi luettelo neljännen iteraation jälkeen on seuraava

Python-esimerkkejä

Seuraava koodi näyttää, kuinka Bubble Sort -algoritmi otetaan käyttöön Pythonissa.

def bubbleSort( theSeq ):n = len( theSeq )for i in range( n - 1 ) :flag = 0for j in range(n - 1) :if theSeq[j] > theSeq[j + 1] :tmp = theSeq[j]theSeq[j] = theSeq[j + 1]theSeq[j + 1] = tmpflag = 1if flag == 0:breakreturn theSeqel = [21,6,9,33,3]result = bubbleSort(el)print (result)

Edellä olevan kuplalajitteluohjelman suorittaminen Pythonissa tuottaa seuraavat tulokset

[6, 9, 21, 3, 33]

Koodin selitys

Python Bubble Sort -ohjelmakoodin selitys on seuraava

TÄSSÄ,

  1. Määrittää toiminnon bubbleSort, joka hyväksyy parametrin Seq. Koodi ei tuota mitään.
  2. Hakee matriisin pituuden ja määrittää arvon muuttujalle n. Koodi ei tuota mitään
  3. Käynnistää for for -silmukan, joka suorittaa kuplalajittelualgoritmin (n - 1) kertaa. Tämä on ulompi silmukka. Koodi ei tuota mitään
  4. Määrittää lippumuuttujan, jota käytetään määrittämään onko vaihto tapahtunut vai ei. Tämä on optimointitarkoituksia varten. Koodi ei tuota mitään
  5. Aloittaa sisemmän silmukan, joka vertaa kaikkia luettelon arvoja ensimmäisestä viimeiseen. Koodi ei tuota mitään.
  6. Tarkistaa if-käskyn avulla, onko vasemmanpuoleinen arvo suurempi kuin oikealla puolella oleva arvo. Koodi ei tuota mitään.
  7. Määrittää Seq [j]: n arvon ajalliselle muuttujalle tmp, jos ehto arvioi arvon tosi. Koodi ei tuota mitään
  8. Seq [j + 1]: n arvo määritetään Seq [j]: n sijaintiin. Koodi ei tuota mitään
  9. Muuttujan tmp arvo annetaan sijainnille Seq [j + 1]. Koodi ei tuota mitään
  10. Lippumuuttujalle on määritetty arvo 1 osoittamaan, että vaihto on tapahtunut. Koodi ei tuota mitään
  11. Käyttää if-käskyä tarkistaakseen, onko muuttujan lipun arvo 0. Koodi ei tuota mitään
  12. Jos arvo on 0, niin kutsumme tauko-lauseita, jotka astuvat ulos sisäisestä silmukasta.
  13. Palauttaa sekvenssin arvon lajittelun jälkeen. Koodi antaa lajitellun luettelon.
  14. Määrittää muuttujan el, joka sisältää luettelon satunnaisluvuista. Koodi ei tuota mitään.
  15. Määrittää funktion bubbleSort arvon muuttuvaan tulokseen.
  16. Tulostaa muuttujan tuloksen arvon.

Kuplalajittelun edut

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 koodi on helppo kirjoittaa
  • Tilavaatimukset ovat vähäiset verrattuna muihin lajittelualgoritmeihin.

Kuplalajittelun haitat

Seuraavassa on joitain kuplalajittelualgoritmin haittoja

  • Se ei toimi hyvin lajitellessasi suuria luetteloita. Se vie liikaa aikaa ja resursseja.
  • Sitä käytetään enimmäkseen akateemisiin tarkoituksiin eikä reaalimaailman sovelluksiin.
  • Luettelon lajittelun edellyttämien vaiheiden määrä on järjestyksessä n 2

Bubble Sortin monimutkaisuusanalyysi

Monimutkaisuutta on kolme tyyppiä:

1) Lajittele monimutkaisuus

Lajittelun monimutkaisuutta käytetään ilmaisemaan suoritusaikojen ja tilan määrä, joka tarvitaan luettelon lajittelemiseen. Kuplalajittelu tekee (n - 1) toistoa luettelon lajittelemiseksi, jossa n on luettelon elementtien kokonaismäärä.

2) Ajan monimutkaisuus

Kuplalajin ajan monimutkaisuus on O (n 2 )

Ajan monimutkaisuus voidaan luokitella seuraavasti:

  • 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)
  • Keskimääräinen tapaus - tämä tapahtuu, kun luettelo on satunnaisessa järjestyksessä. Keskimääräinen monimutkaisuus esitetään muodossa [iso-theta] ⊝ (n 2 )

3) Avaruuden monimutkaisuus

Avaruuden monimutkaisuus mittaa ylimääräisen tilan määrää, jota tarvitaan luettelon lajittelemiseen. Kuplalajittelu vaatii vain yhden (1) ylimääräisen tilan ajalliselle muuttujalle, jota käytetään arvojen vaihtamiseen. Siksi sen avaruuskompleksi on O (1).

Yhteenveto

  • Kuplalajittelualgoritmi toimii vertaamalla kahta vierekkäistä arvoa ja vaihtamalla ne, jos vasemmalla oleva arvo on pienempi kuin oikealla oleva arvo.
  • Kuplalajittelualgoritmin toteuttaminen on suhteellisen suoraviivaista Pythonin kanssa. Sinun tarvitsee käyttää vain silmukoita ja if-lauseita.
  • Kuplalajittelualgoritmin ratkaisema ongelma on satunnaisen alkulistan ottaminen ja muuttaminen järjestetyksi luetteloksi.
  • Kuplalajittelualgoritmi tietorakenteessa toimii parhaiten, kun luettelo on jo lajiteltu, koska se suorittaa minimaalisen määrän iteraatioita.
  • Kuplalajittelualgoritmi ei toimi hyvin, kun luettelo on päinvastaisessa järjestyksessä.
  • Kuplittelijan lajittelulla on O (n 2 ) aikakompleksuus ja O (1) avaruuden monimutkaisuus.
  • Kuplittelijan lajittelualgoritmi sopii parhaiten akateemisiin tarkoituksiin eikä reaalimaailman sovelluksiin.
  • Optimoitu kuplalajittelu tekee algoritmista tehokkaamman ohittamalla tarpeettomat iteraatiot tarkistettaessa jo lajiteltuja arvoja.