>> [MIZIK jwe]
>> Doug Lloyd: Se konsa, sòt ensèsyon se yon lòt algorithm nou ka sèvi ak yo sòt yon etalaj.
Lide a dèyè sa a algorithm se bati etalaj Ranje ou
nan plas, déplacement soti nan eleman wout la jan ou ale, fè chanm.
Sa a se yon ti kras diferan soti nan sòt seleksyon oswa jarèt
sòt, pou egzanp, kote nou ap ajiste kote yo,
kote nou ap fè echanj.
>> Nan ka sa a sa nou ap aktyèlman fè se glisman eleman
sou yo, soti nan fason an.
Kijan sa a algorithm travay nan pseudocode?
Oke kite yo jis abitrèman di ke nan se premye eleman nan etalaj la Ranje.
Nou ap bati l 'nan plas.
>> Nou ap pral ale yon sèl eleman nan yon lè ak bati l ', e konsa nan premye bagay nou wè
se yon etalaj yon sèl eleman.
Apre sa, pa definisyon, yon yon sèl se etalaj eleman Ranje.
>> Lè sa a, nou pral repete pwosesis sa a until-- nou pral repete pwosesis sa a
jiskaske tout nan eleman yo yo ranje.
Gade nan pwochen eleman ki klase ak insert l 'nan pòsyon nan Ranje,
pa déplacement nimewo yo egzije nan eleman soti nan fason an.
Nou swete ke sa a vizyalizasyon pral ede w wè egzakteman sa ki nan
pwal sou ak sòt ensèsyon.
>> Se konsa, ankò, isit la nan nou an tout etalaj klase,
tout nan eleman yo endike nan wouj.
Li kite yo swiv la etap nan pseudocode nou an.
Premye bagay nou fè sa, se nou rele nan premye eleman nan etalaj la, Ranje.
Se konsa, nou ap jis pral di senk, w ap kounye a Ranje.
>> Lè sa a, nou gade nan pwochen an triye eleman nan etalaj la
epi nou vle insert ki nan pòsyon nan Ranje,
pa déplacement eleman sou.
Se konsa, de se pwochen ki klase eleman nan etalaj la.
Klèman li fè pati anvan an senk, Se konsa, sa nou ap pral fè
se sòt de kenbe de sou kote pou yon dezyèm fwa, chanjman senk sou yo, ak Lè sa a Insert de
anvan senk, ki kote yo ta dwe ale.
Epi, koulye a nou ka di ke de se Klase.
>> Se konsa, jan ou ka wè, nou te sèlman byen lwen tèlman gade de eleman nan etalaj la.
Nou pa t 'gade nan rès nan tout, men nou te
te resevwa sa yo de eleman Ranje pa fason pou mekanis nan déplacement.
>> Se konsa, nou repete pwosesis la ankò.
Gade nan pwochen triye nan eleman, sa a, se yon sèl.
Se pou yo kenbe ki sou kote pou yon dezyèm fwa, chanjman tout bagay sou, ak mete yon sèl
kote li ta dwe ale.
>> Yon fwa ankò, toujou, nou te sèlman janm gade yon sèl, de, ak senk.
Nou pa konnen ki lòt bagay la ap vini, men nou te Ranje moun twa eleman.
>> Next eleman triye se twa, se konsa nou pral mete l 'sou kote.
Nou pral chanjman sou sa nou bezwen ki, tan sa a
se pa tout bagay tankou nan anvan an de ka, li nan jis senk an.
Lè sa a, nou pral bwa twa nan, ant de la ak senk an.
>> Sis se pwochen ki klase eleman nan etalaj la.
Lè an reyalite sis gen plis pouvwa pase senk, se konsa nou pa menm bezwen fè nenpòt ki échanjé.
Nou ka jis fofile sis touswit nan nan fen pòsyon nan Ranje.
>> Anfen, kat se nan dènye eleman triye.
Se konsa, nou pral mete l 'sou kote, chanjman sou eleman yo nou bezwen chanjman sou,
ak Lè sa a mete kat kote li ki dwe.
Epi, koulye a gade, nou te sòt nan tout eleman yo.
Avi ak ensèsyon sòt, nou pa t 'gen
yo ale retounen ak lide atravè etalaj la.
Nou sèlman te ale atravè etalaj la yon sèl fwa, epi nou deplase bagay
ke nou ta deja rankontre, yo nan lòd pou fè plas pou eleman yo nouvo.
>> Se konsa, sa ki nan ka ki pi mal senaryo ak sòt ensèsyon?
Nan ka ki pi mal la, an etalaj se nan do lòd.
Ou gen chanjman chak nan eleman yo n jiska pozisyon n, chak fwa yon sèl nou
fè yon ensèsyon.
Sa se yon anpil nan déplacement.
>> Nan ka ki pi bon, nan etalaj se parfe Ranje.
Apre sa, sòt de tankou sa ki te pase ak senk ak sis nan egzanp lan,
kote nou te kapab jis fofile l 'sou san yo pa gen fè nenpòt déplacement,
nou ta esansyèlman fè sa.
>> Si ou imajine ke nou an etalaj se te youn nan sis,
nou ta kòmanse nan pa deklare yon sèl ki Ranje.
De vini apre yon pou nou ka jis di, OK, byen youn ak de yo ranje.
Twa vini apre de sa, OK, youn ak de ak twa yo ranje.
>> Nou pa ap fè nenpòt ki echanj, nou ap jis k ap deplase liy abitrè sa a
ant klase epi triye jan nou ale.
Kòm efektivman jan nou te fè nan egzanp lan, vire eleman ble, jan nou kontinye.
Se konsa, sa ki nan ègzekutabl a ka pi mal la, lè sa a?
Sonje byen, si nou gen chanjman chak nan eleman yo n pètèt pozisyon n,
èspere ke ki ba ou yon lide ki ka ki pi mal
ègzekutabl se Big O nan n okib.
>> Si etalaj la se parfe Ranje, tout sa nou dwe fè
se gade nan chak eleman sèl yon fwa, ak lè sa a nou ap fè.
Se konsa, nan ka ki pi bon, li nan Omega nan n.
>> Mwen se Doug Lloyd.
Sa a se CS50.