[Speel van musiek] DOUG LLOYD: Alle reg, sodat borrel soort is 'n algoritme jy kan gebruik om 'n stel van elemente te sorteer. Kom ons neem 'n blik op hoe dit werk. 

So het die basiese idee agter borrel soort is dit. Ons wil die algemeen hoër beweeg gewaardeer elemente algemeen na regs, en laer gewaardeer elemente algemeen aan die linkerkant, soos ons sou verwag. Ons wil hê die laer dinge te wees by die begin en die hoër dinge te wees aan die einde. 

Hoe kan ons dit doen? Wel, in pseudokode kode, ons kon sê, laat stel 'n ruil toonbank om 'n nie-nul waarde. Ons sal sien waarom ons dit doen in 'n tweede. En dan herhaal ons die volgende proses totdat die swap toonbank is 0, of totdat ons nie swaps at all. 

Herstel die swap toonbank 0 as dit nie reeds 0. Kyk dan by elke aangrensende denim elemente. As daardie twee elemente is nie in orde is, ruil hulle en voeg 1 tot die omruil toonbank. As jy dink oor dit voordat jy dit visualiseer, sien dat hierdie laer sal beweeg gewaardeer elemente aan die linkerkant en hoër gewaardeer elemente na regs, effektief te doen wat ons wil doen, wat is die groepe beweeg elemente in die manier. Kom ons visualiseer hoe dit kan lyk met behulp van ons verskeidenheid wat ons gebruik om te toets uit hierdie algoritmes. Ons het 'n verskeidenheid ongesorteerde weer hier, aangedui deur al die elemente om in rooi. En ek het my ruil counter om 'n nie-nul waarde. Ek arbitrêr gekies negatiewe 1-- dit is nie 0. Ons wil hierdie proses herhaal totdat die swap toonbank is 0. Dit is waarom ek my ruil counter sommige nie-nul waarde, want anders sal die swap toonbank sou wees 0. Ons wil nie eens begin om die proses van die algoritme. So weer, die stappe are-- weer die toonbank ruil 0, dan kyk na elke aangrensende paar, en as hulle buite orde, ruil, en voeg 1 om die ruiltransaksie toonbank. So laat ons begin hierdie proses. So die eerste ding wat ons doen, is Ons stel die swap teen 0, en dan begin ons soek by elke aangrensende paar. 

So begin ons eerste kyk na 5 en 2. Ons sien dat hulle uit bestel en sodat ons hulle ruil. En ons voeg 1 tot die omruil toonbank. So nou is ons swap toonbank is 1, en 2 en 5 is aangeskakel. Nou is die proses herhaal ons. 

Ons kyk na die volgende aangrensende paar, 5 en 1-- dit is ook buite werking is, sodat ons ruil hulle en voeg 1 by die ruil toonbank. Dan kyk ons ​​na 5 en 3. Hulle is buite orde, so ons ruil hulle en ons voeg 1 tot die omruil toonbank. Dan kyk ons ​​na 5 en 6. Hulle is in orde, so ons doen nie eintlik nodig om iets te ruil hierdie tyd. Dan kyk ons ​​na 6 en 4. Hulle is ook buite werking is, sodat ons ruil hulle en ons voeg 1 tot die omruil toonbank. 

Nou sien wat gebeur het. Ons het verhuis 6 al die pad tot die einde. So in seleksie soort, as jy het gesien dat die video, wat ons gedoen het, was ons beland die verskuiwing van die kleinste elemente in die bou die gesorteerde skikking wese van links na regs, die kleinste tot die grootste. In die geval van die borrel soort, as ons volgende hierdie spesifieke algoritme, ons is eintlik gaan bou die gesorteerde skikking van regs na links, die grootste tot die kleinste. Ons het effektief geborrel 6, die grootste waarde, al die pad tot die einde. 

En so kan ons nou verklaar dat is gesorteer, en in die toekoms iterations-- gaan deur die skikking again-- ons nie meer hoef te oorweeg 6. Ons het net om te oorweeg die ongesorteerde elemente wanneer ons kyk na die aangrensende pare. So het ons een klaar deur borrelsortering. So nou gaan ons terug na die vraag, herhaal totdat die swap toonbank is 0. Wel, die ruil counter is 4, so ons gaan hou weer herhaal hierdie proses. 

Ons gaan na die toonbank ruil herstel 0, en kyk na elke aangrensende paar. So het ons begin met 2 en 1-- hulle is buite werking is, sodat ons hulle ruil en ons voeg 1 tot die omruil toonbank. 2 en 3, hulle is in orde. Ons het nie nodig om iets te doen. 3 en 5 in orde is. Ons het nie nodig om iets daar te doen. 

5 en 4, is hulle uit van orde, en so het ons nodig het om hulle te ruil en voeg 1 by die ruil toonbank. En nou het ons verhuis 5, die volgende grootste element, tot aan die einde van die ongesorteerde gedeelte. So kan ons nou noem deel van die gesorteer gedeelte. 

Nou jy kyk na die skerm en waarskynlik kan sê, as ek kan, wat die skikking is nou gesorteer. Maar ons kan nog nie bewys dat. Ons het nie 'n waarborg het dat dit gesorteer. Maar dit is waar die ruil counter gaan in die spel kom. 

So het ons 'n pass voltooi. Die swap toonbank is 2. So ons gaan herhaal hierdie proses weer herhaal totdat die swap toonbank is 0. Herstel die swap toonbank 0. So sal ons dit weer. 

Nou kyk na elke aangrensende paar. Dit is in orde, 1 en 2. 2 en 3 in orde is. 3 en 4 in orde is. So op hierdie punt, sien ons voltooi het soek op elke aangrensende paar, maar die swap toonbank is nog 0. 

As ons nie hoef te skakel enige elemente, dan sal hulle moet wees om deur hoofde van hierdie proses. En so 'n doeltreffendheid van spesies, dat ons rekenaar wetenskaplikes liefhet, is ons nou kan verklaar die hele skikking moet gesorteer, want ons het nie het om enige elemente te ruil. Dit is redelik nice. 

So, wat is die ergste geval scenario met borrelsortering? In die ergste geval die skikking is in totaal omgekeerde volgorde, en so het ons na elke borrel van die groot elemente al die pad oor die skikking. En ons moet ook effektief borrel al die klein elemente terug al die pad oor die skikking, ook. So elkeen van die N elemente het om te beweeg oor al die ander elemente N. So wat is die ergste geval scenario. In die beste geval scenario al is, dit is effens anders seleksie soort. Die skikking is reeds gesorteer wanneer ons gaan in. Ons het nie nodig om enige te maak swaps op die eerste pass. Sodat ons kan om te kyk op minder elemente, reg? Ons hoef nie te herhaal hierdie verwerk 'n paar keer oor. 

So wat beteken dit? So, wat is die ergste geval scenario vir borrelsortering, en wat is die beste scenario vir borrelsortering? Het jy dit raai? In die ergste geval wat jy hoef te Itereer oor al die elemente N N tye. So het die ergste geval is N kwadraat. 

As die skikking is perfek gesorteerde al, net jy het om te kyk na elke van die elemente 'n keer. En as die ruil toonbank is nog 0, jy kan sê hierdie skikking gesorteer. En so in die beste geval, dit is eintlik beter as seleksie sort-- dis omega van n. 

Ek is Doug Lloyd. Dit is CS50.