[MUSIK SPELA] DOUG LLOYD: Okej, så bubbelsortering är en algoritm du kan använda för att sortera en rad faktorer. Låt oss ta en titt på hur det fungerar. 

Så grundidén bakom bubbelsortering är detta. Vi vill i allmänhet att röra sig högre värderade element i allmänhet till höger, och lägre värderade element i allmänhet till vänster, som vi skulle förvänta oss. Vi vill att lägre saker att vara på början, och de högre saker att vara i slutet. 

Hur gör vi detta? Väl i pseudokod kod, Vi kan säga, låt oss ange en swap mot en icke-noll. Vi får se varför vi gör det i en sekund. Och då är vi upprepa följande processen tills swap räknaren är 0, eller tills vi gör inga swappar alls. 

Återställ swap mot 0 om den inte redan är 0. Så titta på varje intilliggande par av element. Om dessa två element är inte är i ordning, byta dem, och tillsätt en på växlingsräknaren. Om du funderar på detta innan du visualisera det, märka att detta kommer att flytta lägre värderade element till vänster och högre värderade element till höger, effektivt gör vad vi vill göra, vilket är flytta dessa grupper element på detta sätt. Låt oss visualisera hur detta kan se med hjälp av vår array som vi använde för att testa ut dessa algoritmer. Vi har en osorterad array här igen, indikeras av alla elementen vara i rött. Och jag ställer min swap disk till ett värde skilt från noll. Jag godtyckligt valde negativt 1-- det är inte 0. Vi vill upprepa denna process tills swap räknaren är 0. Detta är anledningen till att jag in min swap mot vissa icke-nollvärde, eftersom annars swap disk skulle vara 0. Vi skulle inte ens börja förfarandet enligt algoritmen. Så återigen, stegen är-- återställa swap räknaren 0, sedan titta på varje intilliggande par, och om de är i ordning, byta dem, och tillsätt 1 till swap räknaren. Så låt oss börja den här processen. Så det första vi gör är vi sätter swap mot 0, och sedan börjar vi ser vid varje angränsande par. 

Så vi först börja titta på 5 och 2. Vi ser att de är ute ur ordning och så vi byta dem. Och vi lägger 1 till swap räknaren. Så nu vår swap disk är en, och 2 och 5 har kopplats. Nu är vi upprepa processen igen. 

Vi tittar på nästa intilliggande par, 5 och 1-- de är också i ordning, så vi byta dem och lägg 1 till swap räknaren. Sedan tittar vi på 5 och 3. De är i ordning, så vi byta dem och vi lägger en till swap räknaren. Sedan tittar vi på 5 och 6. De är i ordning, så vi egentligen inte behöver byta något den här gången. Sedan tittar vi på 6 och 4. De är också i ordning, så vi byta dem och vi lägger en till swap räknaren. 

Nu märker vad som har hänt. Vi har flyttat 6 hela vägen till slutet. Så i valet sort, om du har sett att video, vad vi gjorde var Vi hamnade flytta minsta element i byggnaden den sorterade arrayen huvudsakligen från från vänster till höger, minsta till största. I fallet med bubbelsortering, om vi är följer efter denna särskilda algoritm, vi faktiskt kommer att bygga den sorterade arrayen från höger till vänster, största till minsta. Vi har faktiskt bubblade 6, den största värde, hela vägen till slutet. 

Och så vi kan nu förklara att detta är sorterad, och i framtiden iterations-- går igenom arrayen igen-- Vi behöver inte tänka på sex längre. Vi behöver bara tänka på de osorterade element När vi tittar på angränsande par. Så vi har avslutat ett passera genom bubbelsortering. Så nu går vi tillbaka till frågan, Upprepa tills swap räknaren är 0. Tja swap räknaren är 4, så vi tänker att fortsätta att upprepa denna process igen. 

Vi kommer att återställa swap räknaren till 0, och titta på varje intilliggande par. Så vi börjar med två och 1-- de är i ordning, så vi byta dem och vi lägger en till swap räknaren. 2 och 3, de är i ordning. Vi behöver inte göra någonting. 3 och 5 är i ordning. Vi behöver inte göra något där. 

5 och 4, de är ute av ordning, och så vi måste byta dem och lägg 1 till swap räknaren. Och nu har vi flyttat 5, den näst största elementet, till slutet av osorterade delen. Så kan vi nu kallar det en del av det sorterade partiet. 

Nu är du tittar på den skärm och förmodligen kan berätta, som kan jag, att uppsättningen sorteras just nu. Men vi kan inte bevisa det ännu. Vi har inte en garanti att det är för sortering. Men det är där swap disk kommer att träda i funktion. 

Så vi har avslutat ett pass. Swapräknaren är 2. Så vi kommer att upprepa denna process igen, Upprepa tills swap räknaren är 0. Återställ swap mot 0. Så vi kommer att återställa den. 

Nu tittar på varje angränsande par. Det är i sin ordning, 1 och 2. 2 och 3 är i ordning. 3 och 4 är i ordning. Så på denna punkt, märker vi har slutfört titta på varje angränsande par, men swap räknaren är fortfarande 0. 

Om vi ​​inte behöver växla några element, då de måste vara i ordning, genom kraft av denna process. Och så en effektivitet av olika slag, att vi datavetare älskar, är vi nu deklarera hela gruppen måste sorteras, eftersom vi inte måste byta några delar. Det är ganska trevligt. 

Så vad är det värsta fallet scenario med bubbelsortering? I värsta fall arrayen är i helt omvänd ordning, och så vi måste bubbla varje av de stora elementen alla vägen över arrayen. Och vi effektivt även behöva bubbla alla de små elementen tillbaka hela vägen över arrayen, också. Så vart och ett av de n elementen måste flytta över alla de andra n element. Så det är det värsta scenariot. I bästa fall scenario är dock detta skiljer sig något från val slag. Matrisen är redan sorterade när vi går in. Vi behöver inte göra några swappar på det första passet. Så vi kanske måste se på färre element, eller hur? Vi behöver inte upprepa denna bearbeta ett antal gånger under. 

Så vad betyder det? Så vad är det värsta scenariot för bubbelsortering, och vad som är det bästa scenariot för bubbelsortering? Har du gissa det? I värsta fall måste man iterera i alla de n elementen n gånger. Så det värsta fallet är n i kvadrat. 

Om arrayen är perfekt sorterade men bara du måste titta på varje av elementen gång. Och om växlingsräknaren fortfarande är 0, du kan säga detta arrayen sorteras. Och så i bästa fall, är detta faktiskt bättre än val sort-- det är omega n. 

Jag är Doug Lloyd. Detta är CS50.