Sortering betyr å ordne data i økende eller synkende rekkefølge i henhold til noe lineært forhold mellom elementene. Denne artikkelen om Bubble Sort in vil hjelpe deg med å forstå dette konseptet i detalj.
Vi vil dekke nedenstående emner i denne bloggen:
- Hva er Bubble sort?
- Fremgangsmåte for å utføre en boblesortering
- Bubble Sort Algorithm
- Python-program for å implementere ent Bubble Sort
Hva er Bubble Sort?
Boblesortering er også kjent som synkende sortering. Det er en enkel sorteringsalgoritme som kontinuerlig går gjennom listen som skal sorteres, sammenligner hvert par tilstøtende elementer og bytter dem hvis de ikke er i riktig rekkefølge. Trinnene gjentas til det ikke er behov for flere bytter, det er når listen er sortert.
Fremgangsmåte for å utføre en boblesortering
- Sammenlign første og andre element i listen, og bytt om de er i feil rekkefølge.
- Sammenlign andre og tredje element og bytt dem hvis de er i feil rekkefølge.
- Fortsett på samme måte til det siste elementet på listen på en lignende måte.
- Fortsett å gjenta alle trinnene ovenfor til listen er sortert.
Ovennevnte trinn vil være tydeligere av følgende visualiseringer -
søkeorddrevet rammeverk i selen
Bubble Sort Algorithm
La oss nå se på algoritmen bak Bubble Sort.
Første pass:
( 16.19 , 11,15,10) -> ( 16.19 , 11,15,10) - Algoritmen sammenligner de to første elementene og bytter siden 19> 16
(16, 19.11 , 15.10) -> (16, 11.19 , 15.10) - Bytt siden 19> 11
(16.11, 19.15 , 10) -> (16,11, 15.19 , 10) - Bytt siden 19> 15
(16,11,15, 19.10 ) -> (16,11,15, 10.19 ) - Siden disse elementene allerede er i riktig rekkefølge (19> 10), bytter ikke algoritmen dem.
Andre pass:
( 16.11 , 15,10,19) -> ( 11.16 , 15,10,19) - Bytt siden 16> 11
(elleve, 16.15 , 10,19) -> (11, 15.16 , 10,19) - Bytt siden 16> 15
(11.15, 16.10 , 19) -> (11,15, 10.16 , 19) - Bytt siden 16> 10
(11,15,10,16,19) -> (11,15,10,16,19)
De er sortert, men algoen vår vet ikke om den er fullført. Derfor trenger det et nytt helt pass uten bytte for å vite at det er sortert.
Tredje pass:
(elleve, 15.10 , 16,19) -> (11, 15.10 , 16,19)
(elleve, 15.10 , 16,19) -> (11, 10.15 , 16,19) - Bytt siden 15> 10
(11,10,15,16,19) -> (11,10,15,16,19)
(11,10,15,16,19) -> (11,10,15,16,19)
Fjerde pass:
( 11.10 , 15,16,19) -> ( 10.11 , 15,16,19) - Bytt siden 11> 10
Den endelige produksjonen er (10,11,15,16,19)
La oss nå kode dette -
Python-program for å implementere Bubble Sort
a = [16, 19, 11, 15, 10, 12, 14]
# gjentakende sløyfe len (a) (antall elementer) antall ganger for j innen rekkevidde (len (a)): #byttet først er falsk byttet = Falsk i = 0 mens ia [i + 1]: # bytte a ], a [i + 1] = a [i + 1], a [i] # Endring av verdien på byttet byttet = Sann i = i + 1 # hvis byttet er falsk, blir listen sortert # vi kan stoppe sløyfen hvis byttet == Falsk: bryt utskrift (a)
PRODUKSJON:
I koden ovenfor sammenligner vi de tilstøtende tallene og bytter dem hvis de ikke er i riktig rekkefølge. Gjenta samme prosess len (a) antall ganger. Vi har tilordnet en variabel 'byttet ut' og gjort den til 'sann' hvis noen av elementene byttes ut i en iterasjon. Og hvis det ikke er noen utveksling av elementer, er listen allerede sortert, og det er derfor ingen endring i verdien på 'byttet', og vi kan bryte løkken.
Med dette kommer vi til en slutt på bloggen med tittelen “How to implement Bubble Sort in Python”. Jeg håper innholdet gir merverdi for Python-kunnskapen din.
Forsikre deg om at du trener så mye som mulig og tilbakestiller opplevelsen.Har du et spørsmål til oss? Vennligst nevn det i kommentarfeltet i denne 'Hvordan implementere Bubble Sort in Python' -bloggen, så kommer vi tilbake til deg så snart som mulig.
For å få inngående kunnskap om Python sammen med de forskjellige applikasjonene, kan du registrere deg for live med 24/7 support og levetidstilgang.