Što je vrsta mjehurića?
Razvrstavanje po mjehurićima algoritam je sortiranja koji se koristi za sortiranje stavki popisa u rastućem redoslijedu uspoređivanjem dviju susjednih vrijednosti. Ako je prva vrijednost veća od druge vrijednosti, prva vrijednost zauzima drugo mjesto vrijednosti, dok druga vrijednost zauzima prvo mjesto vrijednosti. Ako je prva vrijednost niža od druge vrijednosti, tada se zamjena ne vrši.
Taj se postupak ponavlja sve dok se sve vrijednosti na popisu ne usporede i po potrebi zamijene. Svaka se iteracija obično naziva prolazom. Broj prolaza u razvrstavanju oblačića jednak je broju elemenata na popisu minus jedan.
U ovom vodiču za sortiranje mjehurića u Pythonu naučit ćete:
- Što je vrsta mjehurića?
- Primjena algoritma sortiranja mjehurića
- Optimizirani algoritam sortiranja mjehurića
- Vizualni prikaz
- Primjeri Pythona
- Objašnjenje koda
- Prednosti sortiranja mjehurića
- Nedostaci sortiranja mjehurića
- Analiza složenosti sortiranja mjehurića
Primjena algoritma sortiranja mjehurića
Razvrstit ćemo implementaciju u tri (3) koraka, naime problem, rješenje i algoritam koji možemo koristiti za pisanje koda za bilo koji jezik.
Problem
Popis predmeta dat je nasumičnim redoslijedom i željeli bismo ih uredno poredati
Razmotrite sljedeći popis:
[21,6,9,33,3]
Rješenje
Prelistajte popis uspoređujući dva susjedna elementa i mijenjajući ih ako je prva vrijednost veća od druge vrijednosti.
Rezultat bi trebao biti sljedeći:
[3,6,9,21,33]
Algoritam
Algoritam sortiranja mjehurića radi na sljedeći način
Korak 1) Dobijte ukupan broj elemenata. Dohvatite ukupan broj predmeta na danom popisu
Korak 2) Odredite broj vanjskih dodavanja (n - 1) koje treba obaviti. Njegova je duljina popis minus jedan
Korak 3) Izvedite unutarnje prolaze (n - 1) puta za vanjski prolaz 1. Nabavite vrijednost prvog elementa i usporedite ga s drugom vrijednošću. Ako je druga vrijednost manja od prve, zamijenite pozicije
Korak 4) Ponovite korake iz koraka 3 dok ne dođete do vanjskog prolaza (n - 1). Nabavite sljedeći element na popisu, a zatim ponavljajte postupak koji je izveden u koraku 3 dok sve vrijednosti ne budu postavljene u njihov ispravan redoslijed.
Korak 5) Vratite rezultat kad su obavljena sva dodavanja. Vrati rezultate razvrstanog popisa
Korak 6) Optimizirajte algoritam
Izbjegavajte nepotrebne unutarnje prolaze ako su popis ili susjedne vrijednosti već sortirani. Na primjer, ako navedeni popis već sadrži elemente koji su poredani u rastućem redoslijedu, tada možemo rano prekinuti petlju.
Optimizirani algoritam sortiranja mjehurića
Prema zadanim postavkama algoritam za razvrstavanje oblačića u Pythonu uspoređuje sve stavke na popisu bez obzira je li popis već sortiran ili ne. Ako je zadani popis već sortiran, usporedba svih vrijednosti gubitak je vremena i resursa.
Optimizacija sortiranja mjehurića pomaže nam izbjeći nepotrebne ponavljanja i uštedjeti vrijeme i resurse.
Na primjer, ako su prva i druga stavka već sortirane, nema potrebe za iteracijom kroz ostale vrijednosti. Ponavljanje se prekida, a slijedeće započinje dok se postupak ne dovrši, kao što je prikazano u donjem primjeru sortiranja mjehurića.
Optimizacija se vrši pomoću sljedećih koraka
Korak 1) Stvorite varijablu zastavice koja nadgleda je li došlo do zamjene u unutarnjoj petlji
Korak 2) Ako su vrijednosti zamijenile položaje, prijeđite na sljedeću iteraciju
Korak 3) Ako se prednosti nisu zamijenile položajima, prekinite unutarnju petlju i nastavite s vanjskom petljom.
Optimizirana vrsta mjehurića učinkovitija je jer izvršava samo potrebne korake i preskače one koji nisu potrebni.
Vizualni prikaz
S obzirom na popis od pet elemenata, sljedeće slike ilustriraju kako se mjehurić sortira kroz vrijednosti prilikom sortiranja
Sljedeća slika prikazuje nesortirani popis
Prvo ponavljanje
Korak 1)
Vrijednosti 21 i 6 uspoređuju se kako bi se provjerilo koja je veća od druge.
21 je veće od 6, tako da 21 zauzima položaj koji zauzima 6, dok 6 zauzima položaj koji je zauzimao 21
Naš izmijenjeni popis sada izgleda poput gornjeg.
Korak 2)
Uspoređuju se vrijednosti 21 i 9.
21 je veće od 9, pa zamijenimo pozicije 21 i 9
Novi je popis sada kao gore
Korak 3)
Vrijednosti 21 i 33 uspoređuju se kako bi se pronašla veća.
Vrijednost 33 veća je od 21, pa se ne mijenja.
Korak 4)
Vrijednosti 33 i 3 uspoređuju se kako bi se pronašla veća.
Vrijednost 33 veća je od 3, pa zamjenjujemo njihove pozicije.
Poredani popis na kraju prve iteracije je poput gornjeg
Druga ponavljanja
Novi popis nakon druge iteracije je sljedeći
Treća ponavljanja
Novi popis nakon treće iteracije je sljedeći
Četvrta ponavljanja
Novi popis nakon četvrte iteracije je sljedeći
Primjeri Pythona
Sljedeći kod pokazuje kako implementirati algoritam sortiranja mjehurića u Python.
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)
Izvršavanje gornjeg programa za razvrstavanje oblačića u Pythonu daje sljedeće rezultate
[6, 9, 21, 3, 33]
Objašnjenje koda
Objašnjenje programskog koda Python Bubble Sort je sljedeće
OVDJE,
- Definira funkciju bubbleSort koja prihvaća parametar theSeq. Kôd ne daje ništa.
- Dobiva duljinu polja i dodjeljuje vrijednost varijabli n. Kôd ne daje ništa
- Pokreće petlju for koja pokreće algoritam sortiranja oblačića (n - 1) puta. Ovo je vanjska petlja. Kôd ne daje ništa
- Definira varijablu zastave koja će se koristiti za utvrđivanje je li došlo do zamjene ili nije. Ovo je u svrhu optimizacije. Kôd ne daje ništa
- Pokreće unutarnju petlju koja uspoređuje sve vrijednosti na popisu od prve do posljednje. Kôd ne daje ništa.
- Koristi naredbu if da provjeri je li vrijednost na lijevoj strani veća od vrijednosti na neposrednoj desnoj strani. Kôd ne daje ništa.
- Dodjeljuje vrijednostSeq [j] privremenoj varijabli tmp ako se uvjet procijeni na true. Kôd ne daje ništa
- Vrijednost Seq [j + 1] dodjeljuje se položaju Seq [j]. Kôd ne daje ništa
- Vrijednost varijable tmp dodjeljuje se položajuSeq [j + 1]. Kôd ne daje ništa
- Varijabli zastave dodjeljuje se vrijednost 1 koja označava da je došlo do zamjene. Kôd ne daje ništa
- Koristi izraz if za provjeru je li vrijednost oznake varijable 0. Kôd ne daje ništa
- Ako je vrijednost 0, tada nazivamo naredbu break koja izlazi iz unutarnje petlje.
- Vraća vrijednost theSeq nakon što je sortiran. Kôd daje sortirani popis.
- Definira varijablu el koja sadrži popis slučajnih brojeva. Kôd ne daje ništa.
- Dodijeljuje vrijednost funkcije bubbleSort varijabilnom rezultatu.
- Ispisuje vrijednost varijable rezultat.
Prednosti sortiranja mjehurića
Slijede neke od prednosti algoritma sortiranja mjehurića
- To je lako razumjeti
- Izvodi se vrlo dobro kad je popis već ili gotovo sortiran
- Ne zahtijeva opsežnu memoriju.
- Lako je napisati kod za algoritam
- Prostorni zahtjevi su minimalni u usporedbi s drugim algoritmima za sortiranje.
Nedostaci sortiranja mjehurića
Slijede neki od nedostataka algoritma za razvrstavanje mjehurića
- Ne funkcionira dobro prilikom sortiranja velikih popisa. Potrebno je previše vremena i sredstava.
- Uglavnom se koristi u akademske svrhe, a ne u stvarnom svijetu.
- Broj koraka potrebnih za sortiranje popisa reda je n 2
Analiza složenosti sortiranja mjehurića
Postoje tri vrste složenosti:
1) Poredaj složenost
Složenost sortiranja koristi se za izražavanje količine vremena izvršavanja i prostora potrebnog za sortiranje popisa. Razvrstavanje oblačića čini (n - 1) iteracija za sortiranje popisa gdje je n ukupan broj elemenata na popisu.
2) Vremenska složenost
Vremenska složenost vrste mjehurića je O (n 2 )
Složenost vremena možemo kategorizirati kao:
- Najgori slučaj - ovdje je navedeni popis u padajućem redoslijedu. Algoritam izvodi maksimalan broj izvršavanja koji se izražava kao [Big-O] O (n 2 )
- Najbolji slučaj - to se događa kada je navedeni popis već sortiran. Algoritam izvodi minimalni broj izvršavanja koji se izražava kao [Big-Omega] Ω (n)
- Prosječni slučaj - to se događa kada je popis slučajnim redoslijedom. Prosječna složenost predstavljena je kao [Big-theta] ⊝ (n 2 )
3) Složenost prostora
Složenost prostora mjeri količinu dodatnog prostora potrebnog za sortiranje popisa. Razvrstavanje mjehurića zahtijeva samo jedan (1) dodatni prostor za vremensku varijablu koja se koristi za zamjenu vrijednosti. Stoga ima složenost prostora od O (1).
Sažetak
- Algoritam sortiranja mjehurića djeluje uspoređujući dvije susjedne vrijednosti i zamjenjujući ih ako je vrijednost s lijeve strane manja od vrijednosti s desne.
- Implementacija algoritma za razvrstavanje mjehurića relativno je jednostavna s Pythonom. Sve što trebate su naredbe za petlje i if.
- Problem koji rješava algoritam razvrstavanja mjehurića je uzimanje slučajnog popisa predmeta i njegovo pretvaranje u poredani popis.
- Algoritam sortiranja mjehurića u strukturi podataka najbolje funkcionira kad je popis već sortiran jer izvodi minimalan broj iteracija.
- Algoritam sortiranja mjehurića nema dobru izvedbu kad je popis obrnutim redoslijedom.
- Sorta mjehurića ima vremensku složenost O (n 2 ) i složenost prostora O (1)
- Algoritam sortiranja mjehurića najprikladniji je za akademske svrhe, a ne za stvarne programe.
- Optimizirano razvrstavanje oblačića čini algoritam učinkovitijim preskakanjem nepotrebnih iteracija pri provjeri vrijednosti koje su već razvrstane.