[Glazbom] Doug LLOYD: U redu, tako da Bubble sort je algoritam možete koristiti za sortiranje skup elemenata. Idemo pogledati kako se to radi. 

Dakle, osnovna ideja Bubble sort je to. Mi obično žele da se presele veći cijenjeni elementi općenito desno, i niže vrijednosti elemenata općenito lijevo, kao što smo očekivali. Želimo niže stvari da se na početak i viši stvari biti na kraju. 

Kako ćemo to učiniti? Pa u pseudokod koda, mogli bismo reći, neka je set swap suprotno od ne nula vrijednosti. Vidjet ćemo zašto smo to učiniti u sekundi. A onda smo ponoviti sljedeće Proces dok je swap brojač je 0, ili dok ne pravimo swap na sve. 

Reset swap suprotno 0, ako već nije 0. Onda pogledajte sve susjedni par elemenata. Ako ta dva elementa nije u redu, zamijenite ih, i dodati 1 do swap pulta. Ako razmišljate o to prije nego što ga vizualizirati, primijetiti da će ovaj potez niže cijenjena elementi lijevo i više cijenjena elementi desno, učinkovito raditi ono što želimo učiniti, koji je premjestiti ove skupine elemenata na taj način. Idemo zamišljati kako je to može izgledati pomoću naše ponude koje smo koristili za testiranje iz tih algoritama. Imamo nesortiranog niz opet ovdje, naznačeno sve elemente da su u crvenom. I ja postaviti moj razmjeni brojača na različit od nule vrijednosti. Ja samovoljno izabrao negativna 1-- nije 0. Želimo ponoviti ovaj postupak dok swap pulta 0. To je razlog zašto sam postaviti moj swapa Brojač za neke ne nula vrijednosti, jer u protivnom zamjena brojač će biti 0. Mi ne bi ni započinjem Postupak algoritma. Pa opet, koraci are-- resetirati swap brojač 0, a zatim pogledajte na svaki susjedni par, a ako su iz reda, mijenjati ih i dodajte 1 na swapu pulta. Tako ćemo početi taj proces. Dakle, prva stvar mi je smo postavili swap brojača na 0, a onda ćemo početi tražiti na svakim uzastopnim parom. 

Tako smo se prvi put početi gleda na 5 i 2. Vidimo da su oni izvan naručiti i tako smo ih zamijeniti. A mi dodajemo 1 swap pulta. Tako sada naša zamjena brojač je 1, i 2 i 5 su uključen. Sada smo opet ponoviti postupak. 

Mi gledamo na sljedećem susjedni par, 5 i 1-- oni su također iz reda, pa smo ih mijenjati i dodavati 1 na swapu pulta. Onda mi gledamo na 5 i 3. Oni su iz reda, pa smo zamijeniti ih i dodamo 1 do swap pulta. Onda mi gledamo na 5 i 6. Oni su u redu, tako da zapravo ne morati mijenjati išta ovaj put. Onda mi gledamo na 6 i 4. Oni su također iz reda, pa smo zamijeniti ih i dodamo 1 do swap pulta. 

Sada primijetite što se dogodilo. Mi smo se preselili 6 sve do kraja. Tako je u izbor vrste, ako ste vidjela taj video, ono što mi je je smo završili pomicanjem Najmanji elementi u zgradi Sortirani niz bitno od s lijeva na desno, najmanji na najveći. U slučaju bubble sort, ako smo Sljedeći ovom algoritmu, zapravo si idući u biti zgrada Sortirani niz s desna na lijevo, najveći do najmanjih. Mi učinkovito u mjehurićima 6, najveća vrijednost, sve do kraja. 

I tako sada možemo proglasiti da je to riješeno, au budućnosti iterations-- prolazi kroz niz again-- ne uzeti u obzir 6 više. Mi samo uzeti u obzir su Nesortirani elementi kada gledamo susjednih parova. Tako smo završili jedan prolaze kroz mjehur vrste. Dakle, sada se vratimo na pitanje, ponovite sve dok je swap brojač je 0. Pa swap brojač 4, pa idemo držati taj proces ponavlja opet. 

Ćemo resetirati swap brojač 0, a pogledajte svaki susjedni par. Tako smo započeli s 2 i 1-- oni iz reda, pa smo ih mijenjati a mi dodajemo 1 swap pulta. 2 i 3, oni su u redu. Ne morate ništa učiniti. 3 i 5 su u redu. Ne morate ništa učiniti tamo. 

5 i 4, oni su se reda, pa smo trebate ih mijenjati i dodavati 1 na swapu pulta. I sad smo se preselili 5, sljedeći najveći element na kraju nerazvrstanog dijela. Dakle, sada možemo nazvati dio sortirani dijela. 

Sada ste gledajući zaslon i vjerojatno se može reći, kao što to može sam, da je niz sortira sada. No, ne možemo dokazati da još. Nemamo jamstvo da je to riješeno. No, to je mjesto gdje je swap brojač će doći u igru. 

Tako smo završili sredinu. Swap brojač je 2. Tako ćemo ponoviti taj proces opet, ponovite sve dok je swap brojač je 0. Reset swap brojača na 0. Tako ćemo ga resetirati. 

Sada pogledajte svaki susjedni par. To je u redu, 1 i 2. 2 i 3 su u redu. 3 i 4 u redu. Dakle, u ovom trenutku, primijetit smo završili gledajući svaki susjedni par, ali swap brojač je još uvijek 0. 

Ako nemamo prebaciti sve elemente, onda su mora biti u redu, tako Vrlina ovog procesa. I tako Učinkovitost vrsta, da smo računalni znanstvenici ljubav, se sada možemo proglasiti cijeli niz mora biti razvrstani, jer nismo moraju mijenjati sve elemente. To je prilično lijepo. 

Dakle, što je najgori slučaj Scenarij s mjehur vrste? U najgorem slučaju, niz je u potpunosti obrnutom redoslijedu, pa moramo mjehurića svaki velikih elemenata svih put preko polja. I mi učinkovito također morati mjehurić sve od malih elemenata natrag sve preko polja, previše. Tako svaki od n elemenata mora premjestiti u svim drugim elementima n. Dakle, to je najgori mogući scenarij. U najboljem slučaju scenarij ipak, ovo je malo drugačiji od odabira vrste. Niz je već razvrstani kad idemo u. Nemamo da bi bilo swaps na prvom prolazu. Tako bismo mogli imati da izgleda na manje elemente, zar ne? Mi ne moramo ponoviti obraditi nekoliko puta. 

Dakle, što to znači? Dakle, što je najgori mogući scenarij za mjehur vrsta, a što je najbolji scenarij za mjehur vrste? Jeste li pogoditi ovo? U najgorem slučaju, morate ponoviti preko svih n elemenata n puta. Tako je najgori slučaj n na kvadrat. 

Ako je niz savršeno sortirati ipak, samo ti morati pogledati svaki nekad elemenata. A ako je swap brojač je još uvijek 0, možete reći ovo polje je riješeno. I tako je u najboljem slučaju, ovo je zapravo bolji od selekcije sort-- je omega n. 

Ja sam Doug Lloyd. Ovo je CS50.