[Muziek] DOUG LLOYD: Oke, dus bubble sort is een algoritme u kunt gebruiken om een ​​set van elementen afstand. Laten we eens kijken hoe het werkt. 

Dus de basisidee achter bubble sort is dit. We willen over het algemeen hogere bewegen gewaardeerd elementen algemeen naar rechts en lager gewaardeerde elementen in het algemeen naar links, als we zouden verwachten. We willen dat de lagere dingen te zijn op het begin, en de hogere dingen zijn eind. 

Hoe doen we dat? Welnu, in pseudocode code, we kunnen zeggen, laten we stel een ruil tegen een niet-nul waarde. We zullen zien waarom we dat doen in een tweede. En dan herhalen we de volgende proces tot de swap teller is 0, of totdat wij geen swaps helemaal. 

Reset de swap in tegen 0 als het niet al 0. Kijk dan bij elke aangrenzend paar elementen. Als deze twee elementen niet in orde, swap hen, en voeg 1 om de swap teller. Als u denkt over dit voordat je het visualiseren, opmerken dat deze lager zal bewegen gewaardeerd elementen naar links en hoger gewaardeerde elementen naar rechts, effectief te doen wat we willen doen, die bewegen die groepen elementen op die manier. Laten we visualiseren hoe deze zou kunnen kijken met behulp van ons aanbod die we gebruikten testen uit deze algoritmes. We hebben een ongesorteerde serie hier weer, aangeduid door alle elementen zijn in rood. En ik mijn swap teller een nul waarde. Ik willekeurig gekozen negatieve 1-- het is niet 0. We willen dit proces herhalen totdat de swap teller is 0. Dit is de reden waarom ik mijn swap in tegen een aantal niet-nul waarde, omdat anders de swap teller zou zijn 0. We zouden niet eens beginnen met het Werkwijze van het algoritme. Dus nogmaals, de stappen zijn-- reset de swap teller 0, dan kijken naar elke aangrenzende paar, en als ze buiten de orde, ze te verwisselen, en voeg 1 om de swap teller. Dus laten we beginnen met dit proces. Dus het eerste wat we doen is zetten we de swap teller op 0, en dan beginnen we op zoek bij elk aangrenzend paar. 

Dus beginnen we eerst kijken naar de 5 en 2. We zien dat ze uit bestellen en zodat we ze ruilen. En we voegen 1 om de swap teller. Dus nu onze swap teller 1, en 2 en 5 zijn ingeschakeld. Nu het proces herhalen we. 

We kijken naar de volgende aangrenzende paar, 5 en 1-- ze zijn ook buiten de orde, dus we ruilen hen en voeg 1 om de swap teller. Dan kijken we naar 5 en 3. Ze zijn niet in orde, dus we ruilen hen en we voegen 1 om de swap teller. Dan kijken we naar 5 en 6. Ze zijn in orde, dus we eigenlijk niet nodig om iets te ruilen deze tijd. Dan kijken we naar 6 en 4. Ze zijn ook buiten de orde, dus we ruilen hen en we voegen 1 om de swap teller. 

Let nu op wat er gebeurd is. Wij hebben ons bewogen 6 helemaal tot het einde. Dus in selectie sorteren, als je hebt gezien dat de video, wat we deden was belandden we het verplaatsen van de kleinste elementen in de bouw de gesorteerde array wezen uit van links naar rechts, klein naar groot. In het geval van de bubble sort, als we volgens het desbetreffende algoritme, we daadwerkelijk gaan bouwen de gesorteerde array van rechts naar links groot naar klein. We hebben effectief geborreld 6, de grootste waarde, helemaal tot het einde. 

En dus kunnen we nu verklaren dat is gesorteerd, en in de toekomst iterations-- gaat door de array again-- We hoeven niet meer te overwegen 6. We hebben alleen te overwegen de ongesorteerde elementen als we kijken naar aangrenzende paren. Dus we hebben een afgewerkt passeren bubble sort. Dus nu gaan we terug naar de vraag, herhalen totdat de swap teller is 0. Nou, de swap teller is 4, dus we gaan blijven opnieuw herhalen van deze werkwijze. 

We gaan om de swap teller 0, en kijken naar elk aangrenzend paar. Dus beginnen we met 2 en 1-- ze buiten de orde, zodat we ze ruilen en we voegen 1 om de swap teller. 2 en 3, ze zijn in orde. We niet nodig om iets te doen. 3 en 5 in orde zijn. We niet nodig om iets te doen is. 

5 en 4, zijn ze uit van de orde, en dus hebben we nodig hebben om ze te verwisselen en voeg 1 om de swap teller. En nu hebben we verhuisd 5, de volgende grootste element, aan het einde van het ongesorteerde deel. Dus kunnen we nu noemen deel van de gesorteerde gedeelte. 

Nu u op zoek bent naar de scherm en waarschijnlijk kan vertellen, evenals ik, dat de matrix is nu opgelost. Maar we kunnen nog niet bewijzen dat. We hebben geen garantie hebben dat het is opgelost. Maar dit is waar de swap toonbank gaat in het spel te komen. 

Dus hebben we een pas afgerond. De swap teller is 2. Dus we gaan om te herhalen Dit proces opnieuw, herhalen totdat de swap teller is 0. Reset de swap teller op 0. Dus zullen we het resetten. 

Nu kijken naar elk aangrenzend paar. Dat is in orde, 1 en 2. 2 en 3 zijn in orde. 3 en 4 zijn in orde. Dus op dit punt zien we hebt voltooid kijken naar elk aangrenzend paar, maar de swap teller is nog steeds 0. 

Als we niet over te schakelen elke elementen, dan zijn ze moeten in volgorde, hoofde van dit proces. En zo een efficiëntie van soorten, dat we computer wetenschappers houden, is dat we nu kunnen verklaren de hele array moet gesorteerd worden, omdat we niet moet elke elementen te wisselen. Dat is vrij aardig. 

Dus wat is het ergste geval scenario met bubble sort? In het ergste geval de array volledig in omgekeerde volgorde, en dus moeten we elke bubble van de grote elementen alle de weg over de array. En we effectief moeten ook bubble alle kleine elementen back helemaal over de matrix, ook. Dus elk van de n elementen te verplaatsen voor alle andere n elementen. Dus dat is het worst case scenario. In het beste geval scenario echter, dit iets anders dan selectie sorteren. De array is al naargelang als we gaan in. We hoeven niet te elk merk swaps op de eerste pass. Dus we zouden moeten kijken op minder elementen, toch? We hoeven niet te herhalen proces meerdere malen. 

Dus wat betekent dat? Dus wat is het worst case scenario voor de bubble sort, en wat het best case scenario voor bubble sort? Hebt u deze raden? In het ergste geval moet je herhalen Bij alle n elementen n keer. Dus het ergste geval n kwadraat. 

Als de matrix perfect gesorteerde al, alleen jij moeten kijken naar elk van de elementen eenmaal. En als de swap teller is nog steeds 0, je kunt zeggen dat deze array wordt gesorteerd. En dus in het beste geval is eigenlijk beter dan selectie sort-- het omega van de n. 

Ik ben Doug Lloyd. Dit is CS50.