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 manja od druge vrijednosti, tada nema zamjeneping Gotovo je.

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 ćete problem koji rješava, njegov optimizirani oblik, detaljan vizualni vodič i radni Python program i njegove karakteristike performansi.

Provedba Bubble Algoritam sortiranja

Implementaciju ćemo podijeliti u tri (3) koraka, i to 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 da stavke budu uredno poredane.

Razmotrite sljedeći popis:

[21, 6, 9, 33, 3]

rješenje

Iteracija kroz listu uspoređuje dva susjedna elementa i zamjenjuje ihping njih 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) Dohvati ukupan broj elemenata. Dohvati ukupan broj stavki na zadanom popisu.

Korak 2) Odredite broj vanjskih prolaza (n – 1) koje treba obaviti. Njegova duljina je lista minus jedan.

Korak 3) Izvršite unutarnje prolaze (n – 1) puta za vanjski prolaz 1. Uzmite vrijednost prvog elementa i usporedite je s drugom vrijednošću. Ako je druga vrijednost manja od prve vrijednosti, zamijenite pozicije.

Korak 4) Ponavljajte prolaze koraka 3 dok ne dođete do vanjskog prolaza (n – 1). Uzmite sljedeći element na popisu, a zatim ponovite postupak koji je izveden u koraku 3 dok se sve vrijednosti ne postave u ispravnom uzlaznom redoslijedu.

Korak 5) Vrati rezultat kada su svi prolazci izvršeni. Vrati rezultate sortiranog popisa.

Korak 6) Optimiziraj algoritam.

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 postoji li zamjenaping se dogodilo u unutarnjoj petlji.

Korak 2) Ako su vrijednosti zamijenile pozicije, nastavite na sljedeću iteraciju.

Korak 3) Ako vrijednosti nisu zamijenile pozicije, 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 mjehurićasto sortiranje iterira kroz vrijednosti prilikom njihovog sortiranja.

Sljedeća slika prikazuje nesortirani 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ći od 6, pa 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ći od 9, pa mijenjamo pozicije 21 i 9.

Novi popis je sada 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 nema zamjeneping odvija se.

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.

Sortirana lista na kraju prve iteracije je poput one gore.

Druga iteracija

Novi popis nakon druge iteracije je sljedeći:

Treća iteracija

Novi popis nakon treće iteracije je sljedeći:

Četvrta iteracija

Novi popis nakon četvrte iteracije je sljedeći:

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 proizvodi sljedeće rezultate:

[3, 6, 9, 21, 33]

Code Objašnjenje

Objašnjenje za Python BubblKod programa za sortiranje je sljedeći:

OVDJE,

1. Definira funkciju bubbleSort koja prihvaća parametar theSeq. Kod ne ispisuje ništa.
2. Dohvaća duljinu niza i dodjeljuje vrijednost varijabli n. Kod ne ispisuje ništa.
3. Pokreće for petlju koja izvršava algoritam mjehurićastog sortiranja (n – 1) puta. Ovo je vanjska petlja. Kod ne ispisuje ništa.
4. 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.
5. Pokreće unutarnju petlju koja uspoređuje sve vrijednosti na popisu od prve do zadnje. Kod ne ispisuje ništa.
6. Koristi naredbu if za provjeru je li vrijednost na lijevoj strani veća od one na neposrednoj desnoj strani. Kod ne ispisuje ništa.
7. Dodjeljuje vrijednost theSeq[j] vremenskoj varijabli tmp ako se uvjet isplati kao istinit. Kod ne ispisuje ništa.
8. Vrijednost theSeq[j + 1] dodjeljuje se poziciji theSeq[j]. Kod ne ispisuje ništa.
9. Vrijednost varijable tmp dodijeljena je poziciji theSeq[j + 1]. Kod ne ispisuje ništa.
10. Varijabli flag dodjeljuje se vrijednost 1 kako bi se naznačilo da je došlo do zamjene. Kod ne ispisuje ništa.
11. Koristi if naredbu za provjeru je li vrijednost varijable flag 0. Kod ne ispisuje ništa.
12. Ako je vrijednost 0, tada pozivamo naredbu break koja izlazi iz unutarnje petlje.
13. Vraća vrijednost theSeq nakon što je sortiran. Kod daje sortirani popis.
14. Definira varijablu el koja sadrži popis slučajnih brojeva. Kod ne ispisuje ništa.
15. Dodjeljuje vrijednost funkcije bubbleSort rezultatu varijable.
16. Ispisuje vrijednost varijable rezultat.

Bubble vrste prednosti

Neke od prednosti algoritma mjehurićastog sortiranja su sljedeće:

• Lako je razumjeti.
• Vrlo dobro funkcionira 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

Neki od nedostataka algoritma mjehurićastog sortiranja su sljedeći:

• Ne radi dobro pri sortiranju velikih popisa. Oduzima previše vremena i resursa.
• Uglavnom se koristi u akademske svrhe, a ne u stvarne primjene.
• Broj koraka potrebnih za sortiranje liste je reda n².

Analiza složenosti Bubble Razvrstaj

Postoje tri vrste složenosti:

1) Složenost sortiranja

Složenost sortiranja koristi se za izražavanje količine vremena izvršavanja i prostora potrebnog za sortiranje popisa. Sortiranje mjehurićima izvodi (n – 1) iteracija za sortiranje popisa gdje je n ukupan broj elemenata na popisu.

2) Vremenska složenost

Vremenska složenost sortiranja mjehurićima je O(n²).

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(n²).
• Najbolji slučaj – ovo se događa kada je navedeni popis već sortiran. Algoritam izvodi minimalni broj izvršavanja koji je izražen kao [Big-Omega] Ω(n).
• Prosječan slučaj – ovo se događa kada je popis u slučajnom redoslijedu. Prosječna složenost predstavljena je kao [Big-theta] ⊝(n²).

3) Složenost prostora

Prostorna složenost mjeri količinu dodatnog prostora potrebnog za sortiranje popisa. Sortiranje mjehurićima zahtijeva samo jedan (1) dodatni prostor za vremensku varijablu koja se koristi za zamjenu.ping vrijednosti. Stoga ima prostornu složenost O(1).

Pitanja i odgovori