[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 <b, b <c, ens.
Of jy kan sorteer dae van die week waar Sondag is minder as Maandag
wat is minder as Dinsdag.
>> Bubble Sorteer is geensins 'n baie doeltreffende of vinnig sorteer algoritme.
Die ergste-geval looptyd is Big O van n ²
want jy het 'n iterasies te maak deur middel van 'n lys
kontrolering van alle n elemente elke pass-through, NxN = n ².
Hierdie looptyd beteken dat as die aantal elemente wat jy verhogings jy sorteer,
die loop van die tyd verhoog kwadratisch.
>> Maar as doeltreffendheid is nie 'n groot bron van kommer vir jou program
of as jy net die sortering van 'n klein aantal van die elemente,
dalk vind jy Bubble Sorteer nuttig omdat
dit is een van die eenvoudigste sorteer-algoritmes om te verstaan
en te kodeer.
Dit is ook 'n goeie manier om ervaring te kry om met die vertaling van 'n teoretiese
algoritme in die werklike werking kode.
Wel, dit is Bubble Sorteer vir jou. Dankie vir jou kyk.
CS50.TV