Bubble Algoritam sortiranja s Python koristeći Primjer popisa
Što je a Bubble Sortiraj?
Bubble Razvrstaj je algoritam sortiranja koji se koristi za sortiranje stavki popisa uzlaznim redoslijedom usporedbom dviju susjednih vrijednosti. Ako je prva vrijednost veća od druge vrijednosti, prva vrijednost zauzima poziciju druge vrijednosti, dok druga vrijednost zauzima poziciju prve vrijednosti. Ako je prva vrijednost niža od druge vrijednosti, tada se ne vrši zamjena.
Ovaj se postupak ponavlja sve dok se sve vrijednosti na popisu ne usporede i po potrebi zamijene. Svaka se iteracija obično naziva prolaz. Broj prolaza u mjehurićnom sortiranju jednak je broju elemenata na popisu minus jedan.
U ovom Bubble Razvrstavanje u Python udžbenik naučit ćeš:
Provedba Bubble Algoritam sortiranja
Implementaciju ćemo podijeliti u tri (3) koraka, odnosno problem, rješenje i algoritam koji možemo koristiti za pisanje koda za bilo koji jezik.
Problem
Popis stavki dan je nasumičnim redoslijedom, a mi bismo željeli rasporediti stavke na uredan način
Razmotrite sljedeći popis:
[21,6,9,33,3]
rješenje
Iterirajte kroz 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ćima radi na sljedeći način
Korak 1) Dobijte ukupan broj elemenata. Dobijte ukupan broj stavki na danom popisu
Korak 2) Odredite broj vanjskih prolaza (n – 1) koje treba napraviti. Njegova duljina je lista minus jedan
Korak 3) Izvršite unutarnje prolaze (n – 1) puta za vanjski prolaz 1. Dobijte vrijednost prvog elementa i usporedite je s drugom vrijednošću. Ako je druga vrijednost manja od prve vrijednosti, zamijenite pozicije
Korak 4) Ponavljajte korak 3 prolaza dok ne dođete do vanjskog prolaza (n – 1). Dohvatite sljedeći element na popisu, a zatim ponovite postupak koji je izveden u koraku 3 dok se sve vrijednosti ne postave ispravnim uzlaznim redoslijedom.
Korak 5) Vrati rezultat kada su svi prolazi gotovi. Vrati rezultate sortirane liste
Korak 6) Algoritam optimizacije
Izbjegavajte nepotrebna unutarnja prolaska ako su popis ili susjedne vrijednosti već poredane. Na primjer, ako navedeni popis već sadrži elemente koji su poredani uzlaznim redoslijedom, tada možemo rano prekinuti petlju.
Optimizirano Bubble Algoritam sortiranja
Prema zadanim postavkama, algoritam za oblačiće sortira Python uspoređuje sve stavke na popisu bez obzira je li popis već sortiran ili ne. Ako je navedeni popis već sortiran, usporedba svih vrijednosti je gubitak vremena i resursa.
Optimiziranje oblačića pomaže nam da izbjegnemo nepotrebne iteracije i uštedimo vrijeme i resurse.
Na primjer, ako su prva i druga stavka već sortirane, tada nema potrebe ponavljati kroz ostale vrijednosti. Iteracija se prekida, a sljedeća se pokreće dok se proces ne završi kao što je prikazano u nastavku Bubble Primjer sortiranja.
Optimizacija se provodi pomoću sljedećih koraka
Korak 1) Napravite varijablu zastavice koja prati je li došlo do zamjene u unutarnjoj petlji
Korak 2) Ako su vrijednosti zamijenile položaje, nastavite na sljedeću iteraciju
Korak 3) Ako prednosti nisu zamijenile položaje, prekinite unutarnju petlju i nastavite s vanjskom petljom.
Optimizirano sortiranje u obliku mjehurića učinkovitije je jer izvršava samo potrebne korake i preskače one koji nisu potrebni.
Vizualno predstavljanje
S obzirom na popis od pet elemenata, sljedeće slike ilustriraju kako sortiranje u mjehurićima ponavlja kroz vrijednosti kada ih sortira
Sljedeća slika prikazuje nerazvrstani popis
Prva iteracija
Korak 1)
Vrijednosti 21 i 6 se uspoređuju kako bi se provjerilo koja je veća od druge.
21 je veće od 6, tako da 21 zauzima poziciju koju je zauzimao 6, dok 6 zauzima poziciju koju je zauzimao 21
Naš modificirani popis sada izgleda kao onaj iznad.
Korak 2)
Uspoređuju se vrijednosti 21 i 9.
21 je veće od 9, pa mijenjamo mjesta 21 i 9
Novi popis sada je kao gore
Korak 3)
Vrijednosti 21 i 33 uspoređuju se kako bi se pronašla veća.
Vrijednost 33 je veća od 21, tako da se ne vrši zamjena.
Korak 4)
Vrijednosti 33 i 3 uspoređuju se kako bi se pronašla veća.
Vrijednost 33 je veća od 3, pa im mijenjamo položaje.
Poredani popis na kraju prve iteracije je kao onaj iznad
Druga iteracija
Nova lista nakon druge iteracije je sljedeća
Treća iteracija
Nova lista nakon treće iteracije je sljedeća
Četvrta iteracija
Nova lista nakon četvrte iteracije je sljedeća
Python Primjeri
Sljedeći kod pokazuje kako implementirati Bubble Algoritam sortiranja u 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)
Izvršavanje gornjeg programa za sortiranje mjehurića u Python daje sljedeće rezultate
[6, 9, 21, 3, 33]
Objašnjenje koda
Objašnjenje za Python Bubble Programski kod sortiranja je sljedeći
OVDJE,
- Definira funkciju bubbleSort koja prihvaća parametar theSeq. Kod ne ispisuje ništa.
- Dohvaća duljinu niza i dodjeljuje vrijednost varijabli n. Kod ne ispisuje ništa
- Pokreće for petlju koja pokreće algoritam sortiranja u obliku mjehurića (n – 1) puta. Ovo je vanjska petlja. Kod ne ispisuje ništa
- Definira varijablu zastavice koja će se koristiti za određivanje je li došlo do zamjene ili ne. Ovo je u svrhu optimizacije. Kod ne ispisuje ništa
- Pokreće unutarnju petlju koja uspoređuje sve vrijednosti na popisu od prve do zadnje. Kod ne ispisuje ništa.
- Koristi naredbu if za provjeru je li vrijednost na lijevoj strani veća od one na neposrednoj desnoj strani. Kod ne ispisuje ništa.
- Dodjeljuje vrijednost theSeq[j] vremenskoj varijabli tmp ako je uvjet procijenjen kao istinit. Kod ne ispisuje ništa
- Vrijednost theSeq[j + 1] dodijeljena je poziciji theSeq[j]. Kod ne ispisuje ništa
- Vrijednost varijable tmp dodjeljuje se poziciji theSeq[j + 1]. Kod ne ispisuje ništa
- Varijabli zastavice dodijeljena je vrijednost 1 kako bi se označilo da je izvršena zamjena. Kod ne ispisuje ništa
- Koristi naredbu if za provjeru je li vrijednost zastavice varijable 0. Kod ne ispisuje ništa
- Ako je vrijednost 0, tada pozivamo naredbu break koja izlazi iz unutarnje petlje.
- Vraća vrijednost theSeq nakon što je sortiran. Kod daje sortirani popis.
- Definira varijablu el koja sadrži popis slučajnih brojeva. Kod ne ispisuje ništa.
- Dodjeljuje vrijednost funkcije bubbleSort rezultatu varijable.
- Ispisuje vrijednost varijable rezultat.
Bubble vrste prednosti
Slijede neke od prednosti algoritma sortiranja u mjehurićima
- Lako je razumjeti
- Djeluje vrlo dobro kada je popis već ili gotovo sortiran
- Ne zahtijeva veliku memoriju.
- Lako je napisati kod za algoritam
- Potreban prostor minimalan je u usporedbi s drugim algoritmima sortiranja.
Bubble vrsta Nedostaci
Slijede neki od nedostataka algoritma sortiranja u mjehurićima
- Ne radi dobro pri sortiranju velikih popisa. Oduzima previše vremena i resursa.
- Uglavnom se koristi u akademske svrhe, a ne za primjenu u stvarnom svijetu.
- Broj koraka potrebnih za sortiranje liste je reda n2
Analiza složenosti Bubble Razvrstaj
Postoje tri vrste složenosti:
1) Složenost sortiranja
Složenost sortiranja koristi se za izražavanje vremena izvršenja i prostora koji je potreban za sortiranje popisa. Sortiranje u obliku mjehurića čini (n – 1) ponavljanja za sortiranje popisa gdje je n ukupan broj elemenata na popisu.
2) Vremenska složenost
Vremenska složenost sortiranja mjehurićima je O(n2)
Vremenske složenosti mogu se kategorizirati kao:
- Najgori slučaj – ovdje je navedeni popis u silaznom redoslijedu. Algoritam izvodi maksimalan broj izvršenja koji se izražava kao [Big-O] O(n2)
- Najbolji slučaj – ovo se događa kada je navedeni popis već sortiran. Algoritam izvodi minimalni broj izvršavanja koji se izražava kao [Big-Omega] Ω(n)
- Prosječan slučaj – ovo se događa kada je popis nasumičan. Prosječna složenost predstavljena je kao [Big-theta] ⊝(n2)
3) Složenost prostora
Složenost prostora mjeri količinu dodatnog prostora koji je potreban za sortiranje popisa. Oblačić sortiranja zahtijeva samo jedan (1) dodatni prostor za vremensku varijablu koja se koristi za zamjenu vrijednosti. Stoga ima prostornu složenost O (1).
rezime
- Algoritam sortiranja u obliku mjehurića funkcionira tako da uspoređuje dvije susjedne vrijednosti i mijenja ih ako je vrijednost s lijeve strane manja od vrijednosti s desne strane.
- Implementacija algoritma sortiranja mjehurićima je relativno jednostavna Python. Sve što trebate koristiti su petlje for i if naredbe.
- Problem koji rješava algoritam sortiranja u obliku mjehurića je uzimanje nasumičnog popisa stavki i njegovo pretvaranje u uređeni popis.
- Algoritam sortiranja u obliku mjehurića u strukturi podataka ima najbolju izvedbu kada je popis već sortiran budući da izvodi minimalan broj ponavljanja.
- Algoritam sortiranja u obliku mjehurića ne radi dobro kada je popis obrnutim redoslijedom.
- Razvrstavanje mjehurićima ima vremensku složenost O (n2) i složenost prostora od O (1)
- Algoritam sortiranja s mjehurićima najprikladniji je za akademske svrhe, a ne za aplikacije u stvarnom svijetu.
- Optimizirano sortiranje u obliku mjehurića čini algoritam učinkovitijim preskakanjem nepotrebnih iteracija prilikom provjere vrijednosti koje su već sortirane.