>> [MIZIK jwe]
Doug Lloyd: Tout dwa, se konsa sòt ti wonn se yon algorithm
ou ka itilize yo sòt yon seri eleman.
Se pou nou pran yon gade nan ki jan li fonksyone.
>> Se konsa, lide a debaz dèyè sòt ti wonn se sa a.
Nou jeneralman vle pou avanse pou pi wo valè eleman jeneralman a dwat la,
ak pi ba valè eleman jeneralman sou bò goch la, menm jan nou ta atann.
Nou vle bagay sa yo pi ba yo dwe nan nan konmansman an, ak bagay sa yo yo pi wo
yo dwe nan fen an.
>> Ki jan nou fè sa?
Oke nan kòd pseudocode, nou te ka di, se pou yo
mete yon vann san preskripsyon swap nan yon valè ki pa zewo.
Nou pwal wè poukisa nou fè sa nan yon dezyèm fwa.
Lè sa a, nou repete sa ki annapre yo pwosesis jouk kontwa an swap se 0,
oswa jiskaske nou fè pa gen okenn echanj nan tout.
>> Reyajiste kontwa an swap 0 si li pa deja 0.
Lè sa a, gade nan chak pè adjasan nan eleman.
Si sa yo de eleman yo pa nan lòd, swap yo,
epi ajoute 1 a kontwa an swap.
Si w ap panse sou sa a anvan ou visualized li,
remake ke sa a ap deplase pi ba valè eleman sou bò goch la
ak pi wo valè eleman a dwat la, efektivman fè sa nou vle fè,
ki se deplase gwoup moun nan eleman nan fason sa a.
Se pou nou visualized ki jan sa a ta ka gade lè l sèvi avèk etalaj nou an
ke nou itilize li teste soti algoritm sa yo.
Nou gen yon etalaj triye isit la ankò, endike nan tout nan eleman yo
yo te nan wouj.
Apre sa, mwen mete vann san preskripsyon mwen an swap nan yon valè zewo.
Mwen te chwazi abitrèman negatif 1-- li pa 0.
Nou vle repete pwosesis sa a jouk kontwa an swap se 0.
Sa a se poukisa mwen mete m 'swap vann san preskripsyon nan kèk valè ki pa zewo,
paske otreman nan swap vann san preskripsyon ta dwe 0.
Nou pa ta ka menm kòmanse nan pwosesis pou algorithm nan.
Se konsa, ankò, etap sa yo sont- Reyajiste kontwa an swap
a 0, lè sa a gade nan chak adjasan pè, e si yo te ap soti nan lòd,
swap yo, epi ajoute 1 nan kontwa an swap.
Se konsa nou kòmanse pwosesis sa a.
Se konsa, premye bagay la nou fè se nou mete kontwa an swap a 0,
ak Lè sa a nou kòmanse kap nan chak pè adjasan.
>> Se konsa, nou premye kòmanse gade nan 5 ak 2.
Nou wè yo ke yo ap soti nan lòd ak se konsa nou boukante yo.
Epi nou ajoute 1 nan kontwa an swap.
Se konsa, kounye vann san preskripsyon swap nou an, se 1, ak 2 ak 5 yo te chanje.
Koulye a, nou repete pwosesis la ankò.
>> Nou gade nan pwochen pè a adjasan, 5 ak 1-- yo ap tou soti nan lòd,
se konsa nou swap yo epi ajoute 1 a kontwa an swap.
Lè sa a, nou gade nan 5 ak 3.
Yo se soti nan lòd, se konsa nou boukante yo e yo nou ajoute 1 a kontwa an swap.
Lè sa a, nou gade nan 5 ak 6.
Yo ap nan lòd, se konsa nou pa fè sa aktyèlman bezwen swap anyen tan sa a.
Lè sa a, nou gade nan 6 ak 4.
Yo ap tou soti nan lòd, se konsa nou boukante yo e yo nou ajoute 1 a kontwa an swap.
>> Koulye a, remake sa k te pase.
Nou te demenaje ale rete 6 tout wout la nan fen an.
Se konsa, nan sòt seleksyon, si ou te wè ke videyo, sa nou te fè te
nou te fini k ap deplase nan pi piti eleman nan bilding
etalaj la Ranje esansyèlman soti nan gòch a dwat, pi piti nan pi gwo.
Nan ka a nan sòt jarèt, si nou ap apre sa a algorithm patikilye,
nou ap aktyèlman pral yo dwe bati etalaj la Ranje de dwat
sou bò goch, pi gwo pi piti.
Nou te efektivman bul 6 an, pi gwo valè, tout wout la nan fen an.
>> Se konsa, nou kapab kounye a deklare ki ki klase,
ak nan fiti iterations-- ale atravè tout etalaj la again--
nou pa gen konsidere 6 ankò.
Nou sèlman gen konsidere eleman ki klase
lè nou ap chèche a pè adjasan.
Se konsa, nou rive nan bout youn pase nan sòt jarèt.
Se konsa, kounye a nou tounen nan kesyon an, repete jiskaske kontwa an swap se 0.
Oke kontwa an swap se 4, se konsa nou ap ale
kenbe repete pwosesis sa a ankò.
>> Nou pral Reyajiste kontwa an swap a 0, ak gade nan chak pè adjasan.
Se konsa, nou kòmanse ak 2 ak 1-- yo ap soti nan lòd, se konsa nou boukante yo
epi nou ajoute 1 nan kontwa an swap.
2 ak 3, yo ap nan lòd.
Nou pa bezwen fè anyen.
3 ak 5 se nan lòd.
Nou pa bezwen fè anyen la.
>> 5 ak 4 yo, yo se soti nan lòd, epi pou nou
bezwen swap yo epi ajoute 1 a kontwa an swap.
Epi, koulye a nou te demenaje ale rete 5, pwochen pi gwo eleman nan,
nan fen a nan pòsyon ki klase.
Se konsa, nou kapab kounye a rele ke yon pati nan pòsyon nan Klase.
>> Koulye a, ou ap chèche a nan ekran ak pwobableman ka di,
kòm kapab mwen, ki etalaj la se Klase kounye a.
Men, nou pa ka pwouve ke ankò.
Nou pa gen yon garanti ke li nan Ranje.
Men, sa a se kote swap nan vann san preskripsyon k ap pase yo antre nan jwe.
>> Se konsa, nou te ranpli yon pas.
Kontwa an swap se 2.
Se konsa, nou ap ale nan repete pwosesis sa a ankò,
repete jiskaske kontwa an swap se 0.
Reyajiste kontwa an swap a 0.
Se konsa, nou pral Reyajiste li.
>> Koulye a, gade nan chak pè adjasan.
Sa a yo nan lòd, 1 ak 2.
2 ak 3 yo se nan lòd.
3 ak 4 yo se nan lòd.
Se konsa, nan pwen sa a, remake nou te ranpli gade nan chak pè adjasan,
men kontwa an swap se toujou 0.
>> Si nou pa gen yo chanje nenpòt eleman, lè sa a yo
dwe nan lòd, pa vèti nan pwosesis sa a.
Se konsa, yon efikasite nan kalite, ke syantis nou òdinatè renmen,
se nou kapab kounye a deklare etalaj la tout antye dwe
dwe klase, paske nou pa t ' gen swap nenpòt eleman.
Sa a trè bèl.
>> Se konsa, sa ki nan ka ki pi mal senaryo ak sòt jarèt?
Nan ka ki pi mal la etalaj la se nan konplètman ranvèse lòd,
e konsa nou gen yo ti wonn chak nan eleman yo gwo tout
wout la atravè etalaj la.
E nou efektivman tou gen jarèt tout nan eleman yo ti tounen
tout wout la atravè etalaj la, tou.
Se konsa, chak nan eleman yo n gen pou avanse pou pi atravè tout nan eleman yo n lòt.
Se konsa, sa a, se senaryo a ka pi mal la.
Nan ka ki pi bon senaryo menm si, sa a se
yon ti kras diferan de sòt seleksyon.
Etalaj la se deja Ranje lè nou ale nan.
Nou pa gen fè okenn echanj sou pas la an premye.
Se konsa, nou ta ka gen gade a mwens eleman, dwa?
Nou pa gen yo repete sa a travay sou yon kantite fwa sou.
>> Se konsa, sa sa vle di?
Se konsa, sa ki nan senaryo a ka pi move pou sòt jarèt, ak sa ki nan
senaryo a ka pi bon pou sòt jarèt?
Èske w te devine sa a?
Nan ka ki pi mal la ou gen yo repekte atravè tout eleman ki n n fwa.
Se konsa, se ka ki pi mal n okib.
>> Si etalaj la se parfe Ranje menm si, ou sèlman
gen fè yon gade nan chak nan eleman yo yon fwa.
Men, si kontwa an swap se toujou 0, ou ka di se sa a etalaj Ranje.
Se konsa, nan ka ki pi bon, sa a se aktyèlman pi bon pase seleksyon
sort-- li nan Omega nan n.
>> Mwen se Doug Lloyd.
Sa a se CS50.