Kaj je vrsta mehurčkov?
Razvrstitev po mehurčkih je algoritem za razvrščanje, ki se uporablja za razvrščanje elementov seznama v naraščajočem vrstnem redu s primerjavo dveh sosednjih vrednosti. Če je prva vrednost višja od druge vrednosti, prva vrednost zavzame drugo mesto vrednosti, druga vrednost pa prvo mesto vrednosti. Če je prva vrednost nižja od druge, zamenjava ni izvedena.
Ta postopek se ponavlja, dokler se ne primerjajo in po potrebi zamenjajo vse vrednosti na seznamu. Vsako ponovitev se običajno imenuje prehod. Število prehodov v razvrstitvi oblačkov je enako številu elementov na seznamu minus ena.
V tej vadnici za razvrščanje mehurčkov v Pythonu boste izvedeli:
- Kaj je vrsta mehurčkov?
- Izvajanje algoritma za razvrščanje mehurčkov
- Optimiziran algoritem za razvrščanje mehurčkov
- Vizualna predstavitev
- Primeri Pythona
- Razlaga kode
- Prednosti sortiranja mehurčkov
- Slabosti pri razvrščanju mehurčkov
- Analiza kompleksnosti sorte mehurčkov
Izvajanje algoritma za razvrščanje mehurčkov
Izvedbo bomo razdelili na tri (3) korake, in sicer na težavo, rešitev in algoritem, s katerim lahko napišemo kodo za kateri koli jezik.
Težava
Seznam predmetov je podan v naključnem vrstnem redu, elemente pa bi radi uredili urejeno
Upoštevajte naslednji seznam:
[21,6,9,33,3]
Rešitev
Preletite seznam, primerjajte dva sosednja elementa in jih zamenjajte, če je prva vrednost višja od druge vrednosti.
Rezultat mora biti naslednji:
[3,6,9,21,33]
Algoritem
Algoritem za razvrščanje mehurčkov deluje na naslednji način
Korak 1) Pridobite skupno število elementov. Pridobite skupno število elementov na danem seznamu
Korak 2) Določite število zunanjih podaj (n - 1), ki jih je treba opraviti. Njegova dolžina je seznam minus ena
Korak 3) Izvedite notranje prenose (n - 1) krat za zunanji prehod 1. Pridobite prvo vrednost elementa in jo primerjajte z drugo vrednostjo. Če je druga vrednost manjša od prve, zamenjajte položaje
Korak 4) Ponavljajte korake 3, dokler ne pridete do zunanjega prehoda (n - 1). Poiščite naslednji element na seznamu, nato ponovite postopek, ki je bil izveden v koraku 3, dokler niso vse vrednosti postavljene v pravilnem naraščajočem vrstnem redu.
Korak 5) Vrnite rezultat, ko so opravljeni vsi prehodi. Vrnite rezultate razvrščenega seznama
6. korak) Optimizirajte algoritem
Izogibajte se nepotrebnim notranjim prehodom, če so seznam ali sosednje vrednosti že razvrščene. Če na primer navedeni seznam že vsebuje elemente, ki so bili razvrščeni po naraščajočem vrstnem redu, lahko zanko zgodaj prekinemo.
Optimiziran algoritem za razvrščanje mehurčkov
Privzeto algoritem za razvrstitev oblačkov v Pythonu primerja vse elemente na seznamu, ne glede na to, ali je seznam že razvrščen ali ne. Če je dani seznam že razvrščen, je primerjava vseh vrednosti izguba časa in virov.
Optimizacija vrste mehurčkov nam pomaga, da se izognemo nepotrebnim ponovitvam ter prihranimo čas in sredstva.
Če sta na primer prva in druga postavka že razvrščena, ni potrebe po pregledu preostalih vrednosti. Ponovitev se zaključi, naslednja pa se začne, dokler se postopek ne zaključi, kot je prikazano v spodnjem primeru razvrščanja mehurčkov.
Optimizacija se izvede z naslednjimi koraki
Korak 1) Ustvarite spremenljivko zastavice, ki spremlja, ali je prišlo do zamenjave v notranji zanki
Korak 2) Če so vrednosti zamenjale položaje, nadaljujte z naslednjo ponovitvijo
Korak 3) Če prednosti niso zamenjale položajev, zaključite notranjo zanko in nadaljujte z zunanjo zanko.
Optimizirana vrsta mehurčkov je učinkovitejša, saj izvede le potrebne korake in preskoči tiste, ki niso potrebni.
Vizualna predstavitev
Glede na seznam petih elementov naslednje slike ponazarjajo, kako mehurček razvrsti vrednosti med razvrščanjem
Naslednja slika prikazuje nesortiran seznam
Prva ponovitev
Korak 1)
Vrednosti 21 in 6 primerjamo, da preverimo, katera je večja od druge.
21 je večje od 6, torej 21 zavzame položaj 6, medtem ko 6 zavzame položaj, ki ga je zasedel 21
Naš spremenjeni seznam je zdaj videti kot zgornji.
2. korak)
Primerjamo vrednosti 21 in 9.
21 je večje od 9, zato zamenjamo položaji 21 in 9
Novi seznam je zdaj kot zgoraj
3. korak)
Vrednosti 21 in 33 primerjamo, da poiščemo večjega.
Vrednost 33 je večja od 21, zato zamenjava ne poteka.
4. korak)
Vrednosti 33 in 3 primerjamo, da poiščemo večjo.
Vrednost 33 je večja od 3, zato zamenjamo njihove položaje.
Razvrščeni seznam na koncu prve ponovitve je podoben zgornjemu
Druga ponovitev
Nov seznam po drugi ponovitvi je naslednji
Tretja ponovitev
Nov seznam po tretji ponovitvi je naslednji
Četrta ponovitev
Nov seznam po četrti ponovitvi je naslednji
Primeri Pythona
Naslednja koda prikazuje, kako v Pythonu implementirati algoritem Bubble Sort.
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)
Izvedba zgornjega programa za razvrščanje mehurčkov v Pythonu povzroči naslednje rezultate
[6, 9, 21, 3, 33]
Razlaga kode
Razlaga programske kode Python Bubble Sort je naslednja
TUKAJ,
- Določa funkcijo bubbleSort, ki sprejme parameter theSeq. Koda ne izda ničesar.
- Pridobi dolžino polja in dodeli vrednost spremenljivki n. Koda ne izda ničesar
- Zažene zanko for, ki zažene algoritem za razvrščanje oblačkov (n - 1) krat. To je zunanja zanka. Koda ne izda ničesar
- Določa spremenljivko zastavice, ki bo uporabljena za ugotavljanje, ali je prišlo do zamenjave ali ne. To je namenjeno optimizaciji. Koda ne izda ničesar
- Zažene notranjo zanko, ki primerja vse vrednosti na seznamu od prve do zadnje. Koda ne izda ničesar.
- Uporabi stavek if, da preveri, ali je vrednost na levi strani večja od vrednosti na neposredni desni strani. Koda ne izda ničesar.
- Vrednost theSeq [j] dodeli časovni spremenljivki tmp, če pogoj oceni na true. Koda ne izda ničesar
- Vrednost Seq [j + 1] se dodeli položaju Seq [j]. Koda ne izda ničesar
- Vrednost spremenljivke tmp je dodeljena položaju Seq [j + 1]. Koda ne izda ničesar
- Spremenljivki zastave je dodeljena vrednost 1, ki označuje, da je prišlo do zamenjave. Koda ne izda ničesar
- Uporabi stavek if, da preveri, ali je vrednost zastavice spremenljivke 0. Koda ne izda ničesar
- Če je vrednost 0, potem pokličemo izjavo break, ki stopi iz notranje zanke.
- Vrne vrednost zaporedja po razvrščanju. Koda prikaže razvrščeni seznam.
- Določa spremenljivko el, ki vsebuje seznam naključnih števil. Koda ne izda ničesar.
- Vrednosti spremenljivke dodeli vrednost funkcije bubbleSort.
- Natisne vrednost spremenljivke rezultat.
Prednosti sortiranja mehurčkov
Sledi nekaj prednosti algoritma za razvrščanje mehurčkov
- To je enostavno razumeti
- Zelo dobro deluje, ko je seznam že ali skoraj razvrščen
- Ne zahteva obsežnega pomnilnika.
- Kodo za algoritem je enostavno napisati
- Prostorske zahteve so v primerjavi z drugimi algoritmi za razvrščanje minimalne.
Slabosti pri razvrščanju mehurčkov
Sledi nekaj slabosti algoritma za razvrščanje mehurčkov
- Pri razvrščanju velikih seznamov se ne obnese dobro. Traja preveč časa in sredstev.
- Uporablja se večinoma za akademske namene in ne za resnično uporabo.
- Število korakov, potrebnih za razvrščanje seznama, je vrstnega reda n 2
Analiza kompleksnosti sorte mehurčkov
Obstajajo tri vrste zapletenosti:
1) Razvrsti zapletenost
Zapletenost razvrščanja se uporablja za izražanje časa izvedbe in prostora, ki je potreben za razvrščanje seznama. Razvrstitev mehurčkov naredi (n - 1) ponovitve za razvrščanje seznama, kjer je n skupno število elementov na seznamu.
2) Časovna zapletenost
Časovna zapletenost vrste mehurčkov je O (n 2 )
Časovne zapletenosti lahko razvrstimo kot:
- Najslabši primer - tukaj je naveden seznam v padajočem vrstnem redu. Algoritem izvede največje število izvedb, ki je izraženo kot [Big-O] O (n 2 )
- Najboljši primer - to se zgodi, ko je navedeni seznam že razvrščen. Algoritem izvede najmanjše število izvedb, ki je izraženo kot [Big-Omega] Ω (n)
- Povprečen primer - to se zgodi, če je seznam v naključnem vrstnem redu. Povprečna kompleksnost je predstavljena kot [Big-theta] ⊝ (n 2 )
3) Zapletenost prostora
Zapletenost prostora meri količino dodatnega prostora, ki je potreben za razvrščanje seznama. Razvrstitev mehurčkov zahteva le en (1) dodaten prostor za časovno spremenljivko, ki se uporablja za zamenjavo vrednosti. Zato ima vesoljsko kompleksnost O (1).
Povzetek
- Algoritem za razvrščanje mehurčkov deluje tako, da primerja dve sosednji vrednosti in jih zamenjata, če je vrednost na levi manjša od vrednosti na desni.
- Izvajanje algoritma za razvrščanje mehurčkov je s Pythonom razmeroma enostavno. Vse, kar morate uporabiti, so stavki zanke in if.
- Problem, ki ga rešuje algoritem za razvrščanje mehurčkov, je jemanje naključnega seznama elementov in njegovo spreminjanje v urejen seznam.
- Algoritem za razvrščanje mehurčkov v podatkovni strukturi deluje najbolje, če je seznam že razvrščen, saj izvaja minimalno število ponovitev.
- Algoritem razvrščanja oblačkov ne deluje dobro, če je seznam v obratnem vrstnem redu.
- Razvrstitev mehurčkov ima časovno zapletenost O (n 2 ) in vesoljsko zapletenost O (1)
- Algoritem razvrščanja mehurčkov je najprimernejši za akademske namene in ne za resnične aplikacije.
- Optimizirano razvrščanje oblačkov naredi algoritem učinkovitejši tako, da preskoči nepotrebne ponovitve pri preverjanju že razvrščenih vrednosti.