>> [MUSIC SPILLE]
DOUG LLOYD: Greit, så boble liksom er en algoritme
du kan bruke til å sortere et sett av elementer.
La oss ta en titt på hvordan det fungerer.
>> Så den grunnleggende ideen bak boble liksom er dette.
Vi vanligvis ønsker å flytte høyere verdsatte elementer vanligvis til høyre,
og lavere verdsatte elementer generelt til venstre, som vi forventer.
Vi ønsker de lavere ting å være på begynnelsen, og de høyere ting
å være på slutten.
>> Hvordan gjør vi dette?
Vel i pseudokode, vi kunne si, la oss
satt en swap disken til en annen verdi enn null.
Vi vil se hvorfor vi gjør det i et sekund.
Og da vi gjenta følgende prosessen til swap telleren er 0,
eller før vi gjør ingen bytteavtaler i det hele tatt.
>> Tilbakestill swap telleren til 0 hvis det ikke allerede er 0.
Deretter se på hver tilstøtende par av elementer.
Hvis disse to elementene er ikke i orden, bytte dem,
og legge en til swap disken.
Hvis du tenker på dette før du visualisere det,
Legg merke til at dette vil gå lavere verdsatte elementer til venstre
og høyere verdsatt elementer til høyre, effektivt å gjøre det vi ønsker å gjøre,
som er flytte disse gruppene av elementer i den måten.
La oss visualisere hvordan dette kan se ved hjelp av vårt utvalg
som vi brukte for å teste ut disse algoritmene.
Vi har en usortert utvalg her igjen, angitt ved alle elementene
være i rødt.
Og jeg satte min swap disk til en annen verdi enn null.
Jeg valgte vilkårlig negative 1-- det er ikke 0.
Vi ønsker å gjenta denne prosessen til swap telleren er 0.
Det er derfor jeg satt min swap telleren til en verdi forskjellig fra null,
fordi ellers swap disken ville være 0.
Vi ville ikke engang begynne Fremgangsmåten ifølge algoritmen.
Så igjen, trinnene are-- nullstille swap disken
til 0, og deretter se på hver tilstøtende pair, og hvis de er ute av drift,
bytte dem, og tilsett 1 til swap disken.
Så la oss starte denne prosessen.
Så det første vi gjør er vi sette swap disken til 0,
og da vi begynne å se ved hvert tilstøtende par.
>> Så vi først begynner å se på 5 og 2.
Vi ser at de er ute av bestille og så vi bytte dem.
Og vi legger en til swap disken.
Så nå vår swap disken er 1, og 2 og 5 har blitt slått.
Nå gjentar vi prosessen på nytt.
>> Vi ser på den neste tilstøtende par, 5 og 1-- de er også ute av drift,
så vi bytte dem og legge En til swap disken.
Så ser vi på fem og tre.
De er ute av drift, så vi bytte dem, og vi legger en til swap disken.
Så ser vi på fem og seks.
De er i orden, slik at vi ikke faktisk trenger å bytte noe denne gangen.
Så ser vi på 6 og 4.
De er også ute av drift, så vi bytte dem, og vi legger en til swap disken.
>> Nå legge merke til hva som har skjedd.
Vi har flyttet 6 hele veien til enden.
Så i utvalget slag, hvis du har sett at video, det vi gjorde var
vi endte opp med å flytte den minste elementene i bygningen
den sorterte rekke hovedsak fra venstre til høyre, minst til størst.
I tilfelle av boblen slag, hvis vi Følgende denne algoritmen,
vi faktisk kommer til å være å bygge den sorterte rekke fra høyre
til venstre, størst til minst.
Vi har effektivt boblet 6, største verdi, helt til enden.
>> Og så kan vi nå erklære at det er sortert,
og i fremtiden iterations-- går gjennom rekke igjen--
vi trenger ikke å vurdere seks lenger.
Vi trenger bare å vurdere de usorterte elementer
når vi ser på tilstøtende par.
Så vi er ferdig med én passere gjennom boble slag.
Så nå går vi tilbake til spørsmålet, gjenta til swap telleren er 0.
Vel swap disken er fire, så vi kommer
for å holde gjenta denne prosessen på nytt.
>> Vi kommer til å nullstille swap disken til 0, og se på hvert tilstøtende par.
Så vi starter med to og 1-- de er ute av drift, så vi bytte dem
og vi legger en til swap disken.
2 og 3, de er i orden.
Vi trenger ikke å gjøre noe.
3 og 5 er i orden.
Vi trenger ikke å gjøre noe der.
>> 5 og 4, de er ute av orden, og så vi
trenger å bytte dem og legge En til swap disken.
Og nå har vi flyttet 5, den nest største element,
til enden av usortert partiet.
Så vi kan nå kalle det en del av den sorterte partiet.
>> Nå du ser på skjermen og sannsynligvis kan fortelle,
som kan jeg, at matrisen er sortert akkurat nå.
Men vi kan ikke bevise det ennå.
Vi har ikke en garanti at det er sortert.
Men det er her swap disken kommer til å komme inn i bildet.
>> Så vi har fullført et pass.
Swap telleren er 2.
Så vi kommer til å gjenta denne prosessen på nytt,
gjenta til swap telleren er 0.
Tilbakestill swap disken til 0.
Så vi vil tilbakestille det.
>> Nå ser på hvert tilstøtende par.
Det er i orden, 1 og 2.
2 og 3 er i orden.
3 og 4 er i orden.
Så på dette punktet, merker vi har fullført ser på hvert nabopar,
men swap disken er fortsatt 0.
>> Hvis vi ikke trenger å bytte noen elementer, da de
må være i orden, etter I kraft av denne fremgangsmåten.
Og så en effektivitet av former, At vi dataforskere elsker,
er vi nå kan erklære hele matrisen må
sorteres, fordi vi ikke må bytte noen elementer.
Det er ganske fin.
>> Så hva er det verste tilfellet scenario med boble liksom?
I verste fall er matrisen i helt motsatt rekkefølge,
og så har vi å boble hver av de store elementer alle
veien over rekken.
Og vi effektivt må også boble alle de små elementer iden
hele veien over rekken, også.
Slik at hver av de n elementene har til å bevege seg på tvers av alle de andre n elementene.
Så det er worst case scenario.
I beste fall scenario skjønt, er dette
litt forskjellig fra utvalget slag.
Matrisen er allerede sortert når vi går i.
Vi trenger ikke å gjøre noen swaps på første pass.
Så vi må kanskje se på færre elementer, ikke sant?
Vi trenger ikke å gjenta denne behandle en rekke ganger over.
>> Så hva betyr det?
Så hva er worst case scenario for boble sortere, og hva som er
best case scenario for boble liksom?
Visste du antar dette?
I verste fall må du reagere på tvers av alle de n elementene n ganger.
Så det verste tilfellet er n squared.
>> Hvis rekken er helt sortert skjønt, bare du
må se på hver av elementene gang.
Og hvis swap disken er fortsatt 0, du kan si denne tabellen er sortert.
Og så i beste fall, er dette faktisk bedre enn utvalg
sort-- det er omega n.
>> Jeg er Doug Lloyd.
Dette er CS50.