[MIZIK jwe] Doug Lloyd: Seleksyon sòt se yon algorithm ki, menm jan ou ta ka atann, asòti yon seri eleman. Epi sonje algorithm se yon seri etap-pa-etap nan enstriksyon pou ranpli yon travay. 

Nan seleksyon sòt nan lide debaz se sa a, jwenn pi piti eleman ki klase ak ajoute li nan fen a nan lis la Ranje. Efektivman ki sa sa a fè se bati yon lis Ranje, yon sèl eleman nan yon tan. Breaking li desann nan pseudocode nou te ka deklare sa a algorithm jan sa a, repete sa a jouk pa gen okenn eleman triye rete. Search nan triye nan done sa yo jwenn valè a pi piti a, Lè sa a, swap valè ki pi piti a ak nan premye eleman nan pati ki klase. 

Li ka ede yo visualized sa a, kidonk kite a pran yon gade nan sa a. Se konsa, sa a, mwen plede, se yon etalaj triye ak mwen te endike li pa endike ke tout nan eleman yo ki gen koulè pal yo wouj, yo pa yo ankò Ranje. Sa a se tout antye nan triye yon pati nan etalaj la. 

Se konsa nou ale nan etap sa yo nan sòt seleksyon sòt etalaj sa a. Se konsa, ankò, nou ap pral repete jiskaske pa gen okenn eleman triye rete. Nou pral rechèch nan la done sa yo jwenn valè a pi piti a, ak Lè sa a swap ke valè ak nan premye eleman nan pati ki klase. 

Dwa koulye a, ankò, tout la etalaj se yon pati ki klase. Tout nan eleman yo wouj yo triye. Se konsa, nou rechèch nan ak nou jwenn valè ki pi piti a. Nou kòmanse nan kòmansman an, nou ale nan fen a, nou jwenn valè ki pi piti a se, yon sèl. Se konsa, sa a, se yon pati yon sèl. Lè sa a, yon pati de, swap ke valè ak eleman an premye nan pati a klase, oswa premye eleman nan wouj. 

Nan ka sa a ki ta ka senk, se konsa nou boukante yon sèl ak senk. Lè nou fè sa, nou kapab vizyèlman wè ke nou te deplase pi piti eleman nan valè nan etalaj la, nan konmansman an anpil. Efektivman klasman ki eleman. 

Se konsa, nou ka tout bon konfime ak eta ke yon moun, se Ranje. Se konsa, nou pral endike pòsyon nan Ranje nan etalaj nou an, pa koloran li ble. 

Koulye a, nou jis repete pwosesis la ankò. Nou rechèch nan pati ki klase nan etalaj la jwenn eleman ki pi piti a. Nan ka sa a, li nan de. 

Nou swap ke ak premye a eleman nan pati ki klase. Nan ka sa a de tou k ap pase yo dwe eleman an premye nan pati ki klase. Se konsa, nou swap de ak tèt li, ki reyèlman jis kite de kote li se, ak sa yo Ranje. Kontinye sou li a, nou rechèch nan jwenn eleman ki pi piti a. Li nan twa. Nou swap l 'ak premye a eleman, ki se senk. Epi, koulye a twa se Klase. 

Nou rechèch nan ankò, epi nou jwenn eleman ki pi piti a se kat. Nou swap l 'ak eleman an premye nan nan triye pati, e kounye a, kat se Klase. 

Nou jwenn ke senk se eleman nan pi piti a. Nou swap l 'ak premye a eleman nan pati ki klase. Epi, koulye a senk se Klase. 

Lè sa a, anfen, nou an triye pati konsiste nan jis yon eleman sèl, se konsa nou rechèch nan epi nou jwenn ke sis se nan pi piti a, ak nan reyalite, se sèlman eleman. Lè sa a, nou ka deklare ke li se Klase. Epi, koulye a nou te chanje etalaj nou an nan men yo te konplètman triye nan wouj, konplètman Ranje nan ble, lè l sèvi avèk sòt seleksyon. 

Se konsa, sa ki nan senaryo a ka pi move isit la? Byen nan pi move a absoli ka, nou dwe gade sou tout nan eleman yo nan etalaj la yo jwenn pi piti eleman nan klase, e nou gen yo repete pwosesis N fwa sa a. Yon fwa pou chak eleman nan etalaj la paske nou sèlman, nan sa a algorithm, sòt yon sèl eleman nan tan. 

Ki sa ki nan senaryo a ka pi bon? Oke li nan ekzakteman menm bagay la, dwa? Nou gen aktyèlman toujou etap nan chak eleman sèl nan etalaj la yo nan lòd yo konfime ke li se, an reyalite, eleman ki pi piti a. 

Se konsa, ègzekutabl a ka pi mal, nou gen repete yon pwosesis N fwa, yon fwa pou chak nan eleman n. Ak nan senaryo a ka pi bon, nou dwe fè menm bagay la. 

Se konsa, panse tounen nan nou an enfòmatik bwat zouti konpleksite, ki sa ou panse se pi move a ègzekutabl ka pou sòt seleksyon? Ki sa ou panse ki pi bon an ègzekutabl ka pou sòt seleksyon? 

Èske w te devine Big O nan n okib, ak Big Omega nan n okib? Ou ta dwe gen dwa. Moun sa yo se, an reyalite, nan pi move ka ak pi bon ka kouri fwa, pou sòt seleksyon. 

Mwen se Doug Lloyd. Sa a se CS50.