>> [Musik spiller]
DOUG LLOYD: Okay, så boble sortere er en algoritme
du kan bruge til at sortere et sæt af elementer.
Lad os tage et kig på, hvordan det fungerer.
>> Så den grundlæggende idé bag boble sortere er dette.
Vi generelt ønsker at flytte højere værdsatte elementer generelt til højre,
og sænk værdsatte elementer generelt til venstre, som vi ville forvente.
Vi ønsker de nederste ting at være på begyndelsen, og de højere ting
at være ved enden.
>> Hvordan gør vi det?
Godt i pseudokode kode, vi kunne sige, lad os
sætte en swap mod en ikke-nul værdi.
Vi vil se, hvorfor vi gør det i en anden.
Og derefter gentage vi følgende proces, indtil swap tælleren er 0,
eller indtil vi gør ingen swaps overhovedet.
>> Nulstil swap imod 0, hvis den ikke allerede er 0.
Derefter se på hver tilstødende par af elementer.
Hvis disse to elementer er ikke i orden, bytte dem,
og der tilsættes 1 til swap tæller.
Hvis du tænker på dette, før du visualisere det,
bemærke, at dette vil bevæge lavere værdsatte elementer til venstre
og højere værdsat elementer til højre, effektivt gør, hvad vi ønsker at gøre,
som er flytte disse grupper elementer i den måde.
Lad os forestille sig, hvordan dette kan se ved hjælp af vores vifte
som vi brugte til at teste disse algoritmer.
Vi har en usorteret matrix her igen, angivet ved alle elementerne
være rødt.
Og jeg satte mit bytte tæller til en værdi forskellig fra nul.
Jeg vilkårligt valgte negativ 1-- det er ikke 0.
Vi ønsker at gentage denne proces indtil swap tælleren er 0.
Det er derfor, jeg indstille min bytte imod nogle ikke-nul,
fordi ellers swap tæller ville være 0.
Vi ville ikke engang begynde processen med algoritmen.
Så igen, are-- trinnene nulstille swap tælleren
til 0, så kig på hver tilstødende par, og hvis de er ude af orden,
bytte dem, og der tilsættes 1 til swap tæller.
Så lad os begynde denne proces.
Så det første, vi gør, er vi satte swap imod 0,
og så må vi begynde at kigge på hvert tilstødende par.
>> Så vi først begynde at kigge på 5 og 2.
Vi ser, at de er ude af bestille og så vi bytte dem.
Og vi tilføjer 1 til swap tæller.
Så nu er vores swap tælleren er 1, og 2 og 5 er blevet skiftet.
Nu skal vi gentage processen igen.
>> Vi ser på den næste tilstødende par, 5 og 1-- de er også ude af drift,
så vi bytte dem og tilføje 1 til swap tælleren.
Så ser vi på 5 og 3.
De er ude af drift, så vi bytte dem, og vi tilføjer 1 til swap tæller.
Så ser vi på 5 og 6.
De er i orden, så vi faktisk ikke nødt til at bytte noget denne gang.
Så ser vi på 6 og 4.
De er også ude af drift, så vi bytte dem, og vi tilføjer 1 til swap tæller.
>> Nu opdager hvad der er sket.
Vi har flyttet 6 hele vejen til enden.
Så i udvælgelsen sortere, hvis du har set, at video, hvad vi gjorde, var
vi endte med at flytte den mindste elementer i bygningen
det sorterede matrix hovedsagelig fra venstre til højre, mindste til den største.
I tilfælde af boble sortere, hvis vi er efter denne bestemte algoritme,
vi faktisk kommer til at bygge det sorterede vifte fra højre
til venstre, største til mindste.
Vi har effektivt boblet 6, den største værdi, hele vejen til enden.
>> Og så kan vi nu erklære at det er sorteret,
og i fremtiden iterations-- gennemgår array igen--
Vi behøver ikke at overveje 6 længere.
Vi behøver kun at overveje de usorterede elementer
når vi kigger på tilstødende par.
Så vi er færdige én passere gennem boble slags.
Så nu går vi tilbage til spørgsmålet, gentag indtil swap tælleren er 0.
Nå swap counter er 4, så vi vil
at holde at gentage denne proces igen.
>> Vi kommer til at nulstille swap tælleren til 0, og se på hvert tilstødende par.
Så vi starter med 2 og 1-- de er ude af drift, så vi bytte dem
og vi tilføjer 1 til swap tæller.
2 og 3, er de i orden.
Vi behøver ikke at gøre noget.
3 og 5 er i orden.
Vi behøver ikke at gøre noget der.
>> 5 og 4, de er ude af orden, og så vi
nødt til at bytte dem og tilføje 1 til swap tælleren.
Og nu har vi flyttet 5, den næststørste element,
til slutningen af ​​usorteret del.
Så kan vi nu kalder det del af sorteret del.
>> Nu du kigger på den skærm og sandsynligvis kan fortælle,
som kan jeg, at arrayet sorteres lige nu.
Men vi kan ikke bevise, at endnu.
Vi har ikke en garanti at det er ordnet.
Men det er her swap tæller kommer til at komme i spil.
>> Så vi har afsluttet et pass.
Swap tæller er 2.
Så vi kommer til at gentage denne proces igen,
gentag indtil swap tælleren er 0.
Nulstil swap imod 0.
Så vi vil nulstille den.
>> Nu ser på hvert tilstødende par.
Det er i orden, 1 og 2.
2 og 3 er i orden.
3 og 4 er i orden.
Så på dette punkt, mærke, vi har gennemført ser på hver hosliggende par,
men swap tælleren er stadig 0.
>> Hvis vi ikke behøver at skifte eventuelle elementer, så de
skal være i orden, ved kraft af denne proces.
Og så en effektivitet slags, At vi dataloger elsker,
er kan vi nu erklære hele systemet skal
sorteres, fordi vi ikke gjorde nødt til at skifte eventuelle elementer.
Det er ret nice.
>> Så hvad er den værste fald scenarie med boble slags?
I værste fald array er i helt omvendt rækkefølge,
og så vi er nødt til at boble hver af de store elementer alle
vejen på tværs af array.
Og vi effektivt også nødt til at boble alle de små elementer tilbage
hele vejen på tværs af array, også.
Så hver af de n elementer skal bevæge sig på tværs af alle de andre n elementer.
Så det er det værst tænkelige scenarie.
I bedste fald scenario om, det er
lidt anderledes fra valg slags.
Grupperingen er allerede sorteres, når vi går i.
Vi har ikke at gøre nogen swaps på den første passage.
Så vi måske nødt til at se på færre elementer, ikke?
Vi behøver ikke at gentage dette behandle en række gange.
>> Så hvad betyder det?
Så hvad er den værst tænkelige scenarie til boble sortere, og hvad der er
den bedste tænkelige scenario for boble slags?
Vidste du gætte det?
I værste fald er du nødt til gentage på tværs af alle n elementer n gange.
Så det værste tilfælde er n potens.
>> Hvis array er perfekt sorterede selv, kun du
nødt til at se på hver af elementerne gang.
Og hvis swap tælleren er stadig 0, du kan sige dette array er sorteret.
Og så i bedste fald, er dette faktisk bedre end valg
sort-- det er omega n.
>> Jeg er Doug Lloyd.
Det er CS50.