>> MARK GROZEN-SMITH: Hi, Mwen Mak Grozen-Smith, e sa se Quicksort.
Jis tankou sòt ensèsyon ak ti wonn sòt, Quicksort se yon algorithm pou
Fouye yon lis oswa yon etalaj de bagay sa yo.
Pou senplisite, se pou yo asime ke moun ki bagay sa yo yo se jis nonb antye relatif, men
konnen ke Quicksort ap travay pou pi plis pase jis chif yo.
QuickStart se yon ti jan pi konplike pase ensèsyon oswa ti wonn, men li la
tou pi plis efikas nan pifò ka.
Tann yon dezyèm fwa.
Èske li jis di "ki pi ka yo, "pa" tout "?
Enteresan, pa gen okenn.
Se pa tout ka yo se menm bagay la.
pa enkyete sou detay sa a si ou pa gen pou wè gwo notasyon O ankò, men
Quicksort se yon O (n okib) algorithm nan pi move, jis tankou
ensèsyon oswa sòt ti wonn.
Sepandan, li tipikman aji pi plis tankou yon fin vye granmoun analòg m algorithm.
Pou ki sa?
Nou pral jwenn tounen nan ki pita.
Men, pou kounye a, kite yo jis aprann ki jan Quicksort travay.
>> Se konsa, kite a mache nan Quicksorting sa a etalaj de nonb antye relatif soti nan pi piti
rive pi gran.
Isit la nou gen nonm antye relatif yo, 6, 5, 1, 3, 8, 4, 7, 9, ak 2.
Premyèman, nou chwazi eleman final la nan etalaj sa a - nan ka sa a, de -
epi rele ke "pivot la." Apre sa, nou kòmanse fè yon gade nan de bagay sa yo -
yon sèl, endèks la ki pi ba, ki mwen pral refere yo kòm rete a dwat a
miray ranpa a nan, ak, de, leftmost a eleman, ki mwen pral rele "aktyèl la
eleman. "Ki sa nou pral fè se gade tout lòt eleman yo, lòt
pase pivot la, li mete tout eleman ki ki pi piti pase pivot a nan
rete nan miray la ak tout moun sa yo pi gwo pase pivot a nan
dwat Bondye ki gen miray la.
Lè sa a, finalman, nou pral lage pivot la dwa sou epi miray ranpa lavil yo mete l 'ant
tout nimewo yo ki pi piti pase sa li ak tout nimewo yo ki pi gwo.
>> Se konsa, kite a fè sa.
Ranmase 2 a, mete miray lavil la nan la kòmanse, epi rele 6 "aktyèl la nan
eleman. "Se konsa, nou vle gade nan eleman aktyèl nou an, 6 la.
E depi li nan pi gwo pase a 2, nou kite l 'gen yo nan
dwat Bondye ki gen miray la.
Lè sa a, nou deplase sou gade nan 5 an kòm nou kounye a eleman ak wè ke sa a
se, ankò, pi gwo pase pivot a, se konsa nou kite li kote li se sou bò dwat la
bò nan miray la.
Nou deplase sou.
Eleman aktyèl nou se kounye a 1, ak - o.
Sa a se diferan kounye a.
Eleman ki la kounye a se kounye a pi piti pase pivot a, se konsa nou vle mete l '
nan kite nan miray la.
Pou fè sa, kite yo jis chanje a kounye a eleman ak endèks la ki pi ba
chita jis sou bò dwat la nan miray la.
Koulye a, nou deplase miray ranpa a nan moute yon sèl endèks Se konsa, 1 a se sou bò gòch la
bò nan miray ranpa a nan kounye a.
>> Rete tann.
Mwen jis mele eleman yo sou la dwa bò nan miray la, pa t 'mwen menm?
pa enkyete.
Sa a amann.
Bagay la sèlman nou pran swen sou pou kounye a se ke tout eleman sa yo nan
dwat Bondye ki gen miray ranpa a nan yo se pi gwo pase pivot la.
Pa gen okenn lòd aktyèl sipoze ankò.
>> Koulye a, tounen nan klasman.
Se konsa, nou kontinye sou gade nan rès la nan eleman yo.
Apre sa, nan ka sa a, nou wè ke gen pa gen okenn lòt eleman pi piti pase nan
pivot, se konsa nou kite yo tout sou bò dwat la nan miray la.
Finalman, nou jwenn yo eleman aktyèl la ak wè ke li se pivot la.
Koulye a, sa vle di nou gen de seksyon nan etalaj la, yo te nan premye
ti sou pivot a ak sou bò gòch la nan miray la, ak dezyèm ke yo te nan
pi gwo pase pivot a nan dwa bò nan miray la.
Nou vle mete eleman ki Thorne ant de a, ak Lè sa a, nou pral konnen
ki Thorne an se nan dwa li final tri plas li.
Se konsa, nou chanje eleman nan premye sou la dwa bò nan miray la ak Thorne an,
e nou konnen pivot la nan yon pozisyon dwat li yo.
>> Nou Lè sa a, repete pwosesis sa a pou la subarrays kite la ak dwa nan pivot la.
Depi dènye subarray a se sèlman yon sèl eleman lontan, nou konnen sa a, se deja
tri paske ki jan ou ka gen soti nan lòd si w ap sèlman yon sèl eleman?
Pou bò dwat la nan subarray a, nou wè ke pivot a se 5, ak miray ranpa a
se jis rete nan 6 la.
Apre sa, eleman aktyèl la tou kòmanse deyò tankou 6 la.
Se konsa, 6, pi konsekan pase 5.
Nou kite li kote li se sou la dwa bò nan miray la.
Koulye a, k ap deplase sou li a, 3 se mwens pase 5.
Se konsa, nou chanje li ak eleman nan premye jis dwa nan miray la.
Koulye a, mwen te deplase miray ranpa a nan moute yon sèl.
Koulye a, deplase sou a 8 an.
8 ki pi gran pase 5, Se konsa nou kite li.
4 a se mwens pase 5, se konsa nou chanje li.
Yo, epi sou.
>> Chak fwa nou repete pwosedi an sou la kote kite la ak dwa nan etalaj la. nou
chwazi yon pivot epi fè konparezon yo ak kreye yon lòt nivo nan kite ak
subarrays dwat.
Sa a rele repetitif yo ap kontinye jouk nou rive nan fen an lè nou te gen
divize moute etalaj la an jeneral nan jis subarrays longè 1.
Soti nan la, nou konnen se etalaj la klase paske chak eleman gen, nan
kèk pwen, te yon pivot.
Nan lòt mo, pou chak eleman yo, tout chif yo sou bò goch la se pi piti
valè ak tout nimewo yo nan la dwa gen plis valè.
>> Metòd sa a ap travay trè byen si la valè de pivot a chwazi a se
apeprè nan mitan an ran de lis valè yo.
Sa a ta vle di ke, apre yo fin nou avanse eleman alantou li, gen sou kòm anpil
eleman nan kite nan pivot la kòm gen sou bò dwat la.
Ak nati a divize-ak-konkeri nan la Se Quicksort algorithm Lè sa a, pran
anpil avantaj de.
Sa vin kreye yon ègzekutabl nan O (n ale n,) n la paske nou dwe fè n mwens 1
konparezon sou chak moun k'ap viv koulye ak boutèy n paske nou gen divize lis la
louvri sesyon fwa n.
Sepandan, nan ka yo pi mal, sa a algorithm ka aktyèlman ap O (n
okib.) Sipoze sou chak jenerasyon, pivot a jis pou k ap pase yo nan
pi piti oswa pi gwo a nan la nimewo nou ap klasman.
Sa ta vle di kraze desann lis la n fwa, epi li fè n mwens 1
konparezon chak fwa sèl.
Se konsa, o nan n okib.
>> Ki jan nou ka amelyore metòd la?
Yon bon fason yo amelyore metòd la se nan koupe desann sou pwobabilite ki genyen pou
ègzekutabl a se tout tan tout tan aktyèlman o nan n okib.
Sonje sa a pi move, senaryo ka pi mal ka sèlman rive lè a
pivot chwazi se toujou pi wo a oswa ki pi ba valè nan etalaj la.
Pou asire sa a se mwens chans rive, nou ka jwenn pivot a pa
w ap chwazi eleman miltip ak pran valè medyàn.
>> Non mwen se Mak Grozen-Smith, ak sa a se CS50.
>> Pou senplisite, se pou yo asime ke moun ki bagay sa yo yo se jis nonb antye relatif, men
konnen ke Quicksert -
Quicksert?
M regrèt.
>> Isit la nou gen nonm antye relatif yo , 6, 5, 1, 3, 8, 4, 9.
>> Oratè 1: Vrèman?
>> Oratè 2: pa sispann la.
>> Oratè 1: Vrèman?