[Powered by Google Translate] [BUBBLE SORT] [JACKSON STEINKAMP Harvard Universiteit] [HIERDIE IS CS50. CS50TV] Bubble Sorteer is 'n voorbeeld van 'n sorteer algoritme - dit is 'n proses vir die sortering van 'n stel van die elemente in stygende of dalende volgorde. Byvoorbeeld, as jy wou 'n skikking te sorteer uit van die getalle [3, 5, 2, 9], sou 'n korrekte implementering van die Bubble Sorteer die standaard van die gesorteer array [2, 3, 5, 9 in stygende orde. Nou, ek gaan om te verduidelik die pseudokode hoe die algoritme werk. Kom ons sê dat ons 'n lys van 5 heelgetalle te sorteer - 3, 2, 9, 6, en 5. Die algoritme begin deur te kyk na die eerste twee elemente, 3 en 2, en te keur as hulle uit van orde relatief tot mekaar. Hulle is 3 groter as 2 is. Te wees in stygende volgorde, moet hulle die ander manier om. So, ons ruil hulle. Nou is die lys lyk soos hierdie: [2, 3, 9, 6, 5]. Volgende kyk ons ​​na die tweede en derde elemente, 3 en 9. Hulle is in die korrekte volgorde relatief tot mekaar. Dit is, 3 is minder as 9 sodat die algoritme hulle nie ruil. Volgende, ons kyk op 9 en 6. Hulle is buite orde. So, ons nodig het om hulle te ruil, want 9 is meer as 6. Ten slotte, ons kyk na die laaste twee heelgetalle, 9 en 5. Hulle is buite orde, so hulle moet omgeruil word. Na die eerste volledige slaag deur die lys, dit lyk soos hierdie: [2, 3, 6, 5, 9]. Nie sleg nie. Dit is byna gesorteer. Maar ons moet loop weer deur die lys om dit heeltemal gesorteer te kry. Twee is minder as 3, so ons ruil hulle nie. Drie is minder as 6, so ons ruil hulle nie. Ses is groter as 5. Ons verruil. Ses minder as 9. Ons ruil nie. Na die tweede deurtrek, dit lyk soos hierdie: [2, 3, 5, 6, 9]. Perfect. Nou, laat ons skryf dit in pseudokode. Basies, vir elke element in die lys, ons nodig het om te kyk na dit en die element direk tot sy reg. As hulle buite werking is relatief tot mekaar - dit is, as die element aan die linkerkant is groter as die een aan die regter - ons moet ruil die twee elemente. Ons doen dit vir elke element van die lys, en ons het een deurtrek. Nou moet ons net die pass-through genoeg keer om te doen om die lys om te verseker is ten volle, behoorlik gesorteer. Maar hoeveel keer het ons het om te slaag deur die lys te waarborg dat ons gedoen het? Wel, die ergste geval scenario is as ons 'n heeltemal agteruit lys. Dan neem 'n aantal van die slaag-throughs gelyk aan die aantal elemente N-1. As dit nie sin maak nie intuïtief, dink van 'n eenvoudige geval - die lys [2, 1]. Dit gaan 'n pass-through neem om te korrek te sorteer. [3, 2, 1] - Die ergste geval is dat met 3 elemente gesorteer agteruit, dit gaan 2 iterasies te neem om te sorteer. Na een iterasie, dit is [2, 1, 3]. Die tweede opbrengste die gesorteerde array [1, 2, 3]. So jy weet dat jy nooit weer hoef te gaan deur middel van die skikking, in die algemeen, meer as N-1 keer, waar n die aantal elemente in die skikking. Dit is genoem Bubble Sorteer omdat die grootste elemente is geneig om te "borrel-up" redelik vinnig aan die regterkant. In werklikheid, hierdie algoritme het 'n baie interessante gedrag. Na m iterasies deur die hele skikking, die regterkantste m elemente is gewaarborg word gesorteer in hulle regte plek. As jy wil om dit te sien vir jouself, ons kan probeer om dit op 'n heeltemal agteruit lys [9, 6, 5, 3, 2]. Na een keer deur die hele lys, [Geluid van skrif] [6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9] die mees regse element 9 is in sy behoorlike plek. Na die tweede pass-through, sal die 6 het geborrel-up "aan die tweede regterkantste plek. Die twee elemente op die regte - 6 en 9 - sal wees in hulle korrekte plekke na die eerste twee pass-throughs. Dus, hoe kan ons dit gebruik om die algoritme te optimaliseer? Wel, na een iterasie deur die skikking ons nie eintlik nodig het om seker te maak die mees regse element omdat ons weet dit is gesorteer. Na twee iterasies, ons weet vir seker dat die regterkantste twee elemente is in plek. So, in die algemeen, na k iterasies deur die volle verskeidenheid, die beheer van die laaste k elemente is oorbodig want ons weet hulle is reeds op die regte plek. So as jy die sortering van 'n verskeidenheid van n elemente, op die eerste iterasie - you'll het al die elemente uit te sorteer - die eerste n-0. Op die tweede iterasie, sal jy het om te kyk na al die elemente, maar die laaste - die eerste N-1. Nog 'n optimalisering kan wees om seker te maak indien die lys is reeds gesorteer na elke iterasie. As dit reeds gesorteer is, het ons nie nodig nie meer iterasies te maak deur die lys. Hoe kan ons dit doen? Wel, as ons maak geen swaps op 'n pass-through van die lys, dit is duidelik dat die lys is reeds gesorteer is, want ons het niks ruil. So het ons beslis nie om weer te sorteer. Miskien kan jy 'n vlag veranderlike genoem nie gesorteer 'to inisialiseer vals en verander dit na ware indien u enige elemente op te ruil een iterasie deur die skikking. Of soortgelyk, maak 'n toonbank om te tel hoeveel swaps jy maak op enige gegewe iterasie. Aan die einde van 'n iterasie, as jy nie enige van die elemente ruil, jy weet die lys is reeds gesorteer en wat jy gedoen het. Bubble sorteer, soos ander sorteer-algoritmes, kan tweaked om te werk vir enige elemente wat 'n bestel metode. Dit is twee elemente wat jy het 'n manier om te sê as die eerste een is groter as, gelyk aan of minder as die tweede. Byvoorbeeld, kan jy die letters van die alfabet sorteer deur te sê dat a