[Powered by Google Translate] Tommy: Se pou nou pran yon gade nan kalite seleksyon, yon algorithm pou pran yon lis nimewo ak Fouye yo. Yon algorithm, sonje, se senpleman yon etap-pa-etap pwosedi pou reyalize yon travay. Lide a debaz dèyè sòt seleksyon se divize lis nou an nan de pòsyon - yon pòsyon klase epi yon pòsyon klase. Nan chak etap nan algorithm la, se yon nimewo te deplase soti nan la klase pòsyon pòsyon nan Ranje jouk evantyèlman a se tout lis Ranje. Se konsa, isit la nan yon lis nan sis nimewo - 23, 42, 4, 16, 8, ak 15. Dwa koulye a, se lis la tout antye konsidere kòm klase. Menm si yon nimewo tankou 16 ka deja dwe nan kòrèk li yo kote, algorithm nou an ki gen okenn jan pou konnen sa jouk lè a se tout lis Ranje. Se konsa, nou pral konsidere chak nimewo yo dwe klase jiskaske nou sòt li tèt nou. Nou konnen nou vle lis la yo dwe nan Ascending lòd. Se konsa, nou pral vle bati pòsyon nan Ranje nan lis nou an de goch a dwat, pi piti pi gwo. Pou fè sa, nou pral bezwen jwenn minimòm eleman nan klase li mete l 'nan fen a nan pòsyon an Ranje. Depi lis sa a pa se Klase, wout la sèlman nan fè sa se gade nan chak eleman nan pòsyon klase, sonje ki eleman se pi ba a ak konpare chak eleman ak sa yo ki. Se konsa, nou pral premye gade nan 23 an. Sa a se eleman nan premye nou te wè, se konsa nou pral sonje li kòm minimòm la. Next n ap gade 42. 42 se pi gwo pase 23, se konsa 23 se toujou minimòm la. Next se 4 a ki se mwens pase 23, se konsa nou pral sonje 4 kòm minimòm nan nouvo. Next se 16 ki se pi gwo pase 4, ki fè 4 se toujou minimòm la. 8 se pi gwo pase 4, ak 15 se pi gwo pase 4, ki fè 4 yo dwe pi piti eleman ki klase. Se konsa, menm si tankou moun nou ka imedyatman wè ke 4 se eleman minimòm-nan, algorithm nou an bezwen fè yon gade nan chak eleman nan klase, menm apre nou te jwenn 4 an - minimòm eleman. Se konsa, kounye a ke nou te jwenn eleman minimòm-nan, 4, nou pral vle pou avanse pou li nan pòsyon nan Ranje nan lis la. Depi sa a se premye etap la, sa vle di nou vle mete 4 nan nan konmansman an nan lis la. Kounye a, 23 se nan kòmansman an nan lis la, se konsa kite a swap 4 an ak 23 an. Se konsa, kounye a lis nou an sanble tankou sa a. Nou konnen ke 4 yo dwe nan kote final li yo, paske li se tou de eleman ki pi piti a ak eleman ki nan kòmansman an nan lis la. Se konsa, sa sa vle di ke nou pa janm bezwen pou avanse pou li ankò. Se konsa, kite a repete pwosesis sa a ajoute yon lòt eleman nan Ranje pòsyon nan lis la. Nou konnen nou pa bezwen fè yon gade nan 4 a, paske li nan deja klase. Se konsa, nou kapab kòmanse nan 42 an, ki nou pral sonje kòm la minimòm eleman. Se konsa, pwochen n ap gade 23 la ki se mwens pase 42, konsa nou sonje 23 se minimòm nan nouvo. Next nou wè 16 la ki se mwens pase 23, se konsa 16 se minimòm nan nouvo. Koulye a, nou gade nan 8 la ki se mwens pase 16, se konsa 8 se minimòm nan nouvo. Epi finalman 8 se mwens pase 15, se konsa nou konnen ke 8 se yon minimòm klase eleman. Se konsa, sa vle di nou ta dwe tache 8 a Ranje a pòsyon nan lis la. Kounye a, 4 se eleman ki sèlman Ranje, se konsa nou vle mete pwochen an 8 a 4 an. Depi 42 se eleman ki an premye nan pòsyon ki klase nan la lis, nou pral vle swap 42 an ak 8 la. Se konsa, kounye a lis nou an sanble tankou sa a. 4 ak 8 reprezante pòsyon nan Ranje nan lis la, ak nan ki rete nimewo reprezante klase nan pòsyon nan lis la. Se konsa, kite a kontinye ak yon lòt iterasyon. Nou kòmanse avèk 23 tan sa a, depi nou pa bezwen gade 4 an ak 8 nan ankò paske yo te te deja klase. 16 se mwens pase 23, se konsa nou pral sonje 16 kòm minimòm nan nouvo. 16 se mwens pase 42, men 15 gen mwens pase 16, se konsa 15 yo dwe minimòm eleman nan klase. Se konsa, kounye a nou vle swap 15 an ak 23 an ba nou lis sa a. Pòsyon nan Ranje nan lis la konsiste de 4 8, ak 15, ak eleman sa yo se toujou klase. Men, li jis pou rive nan pwochen fèt eleman nan klase, 16, deja klase. Sepandan, gen nan pa gen fason pou algorithm nou konnen ke 16 se deja nan kote kòrèk li yo, pou nou toujou bezwen repete egzakteman menm pwosesis yo. Se konsa, nou wè ke 16 se mwens pase 42, ak 16 se mwens pase 23, se konsa 16 dwe eleman nan minimòm. Li nan enposib swap sa a eleman ak pwòp tèt li, se konsa nou kapab tou senpleman kite li nan sa a kote. Se konsa, nou bezwen youn plis pas nan algorithm nou an. 42 se pi gran pase 23, se konsa 23 yo dwe a minimòm eleman klase. Yon fwa nou boukante 23 an ak 42 an, nou fini ak final nou an Ranje lis - 4, 8, 15, 16, 23, 42. Nou konnen 42 yo dwe an plas ki kòrèk la depi li nan la sèlman eleman ki rete, e sa a, se sòt seleksyon. Se pou nou kounye a formalizra algorithm nou an ak kèk pseudocode. Sou liy youn, nou ka wè ke nou bezwen entegre sou chak eleman nan lis la. Eksepte eleman an dènye, depi eleman nan 1 lis la deja klase. Sou liy de, nou konsidere eleman an premye nan klase nan pòsyon nan lis la yo dwe minimòm lan, kòm nou te fè sa avèk nou egzanp, pou nou gen yon bagay yo konpare ak. Liy twa kòmanse yon riban dezyèm nan ki nou repekte sou chak eleman klase. Nou konnen ke apre mwen fin itérations, pòsyon nan Ranje nan lis nou an dwe gen mwen eleman nan li depi chak etap kalite yon sèl eleman. Se konsa, premye eleman ki klase yo dwe nan pozisyon mwen plis 1. Sou liy kat, nou konpare eleman aktyèl la minimòm la eleman ke nou te wè byen lwen tèlman. Si eleman aktyèl la se pi piti pase minimòm nan eleman, Lè sa a, nou chonje eleman aktyèl la kòm nouvo a minimòm sou liy senk. Finalman, sou liy sis ak sèt, nou boukante minimòm la eleman ak eleman nan premye klase, kidonk ajoute li nan pòsyon nan Ranje nan lis la. Yon fwa nou gen yon algorithm, yon kesyon ki enpòtan nan mande tèt nou kòm pwogramasyon se konbyen tan t 'ki pran? Nou pral premye mande kesyon an konbyen tan li pran pou sa a algorithm nan kouri nan ka ki pi mal la? Rapèl nou reprezante sa a kouri tan ak notasyon gwo O. Yo nan lòd yo detèmine minimòm eleman nan klase, nou esansyèlman te gen yo konpare chak eleman nan lis la chak eleman lòt nan lis la. Intuitivement, sa a son tankou yon O de operasyon okib n. Gade nan pseudocode nou an, nou menm tou nou gen yon riban pare solèy andedan yon lòt bouk yo, ki tout bon son tankou yon O pou n operasyon okib. Sepandan, sonje ke nou pa t 'bezwen gade sou la tout lis lè y ap detèmine minimòm eleman nan klase? Yon fwa nou te konnen ki te 4 nan Ranje, pou egzanp, nou pa t ' bezwen gade l 'ankò. Se konsa, sa a pi ba tan an kouri? Pou lis nou an longè, 6, nou bezwen fè senk konparezon pou eleman a an premye, kat konparezon pou eleman, dezyèm lan, ak sou sa. Sa vle di ke kantite total etap a se sòm total nonm antye relatif yo nan 1 rive nan longè nan lis la mwens 1. Nou ka reprezante sa a ak yon somasyon. Nou pa pral antre summations isit la. Men, li sanble ke sa a somasyon ki egal a n fwa n mwens 1 sou 2. Oswa équivalant, n Squared plis pase 2 mwens n plis pase 2. Lè w ap pale sou ègzekutabl asenptotik, sa a n tèm okib ki pral domine tèm sa a n. Se konsa, sòt seleksyon se O nan n okib. Sonje byen, nan egzanp nou an, sòt seleksyon toujou bezwen tcheke si yon nimewo ki te deja klase bezwen brannen l '. Se konsa, sa vle di ke si nou kouri sòt seleksyon sou plis pase yon deja Ranje lis, li ta mande pou menm kantite etap kòm li ta lè kouri sou yon lis konplètman klase. Se konsa, sòt seleksyon an gen yon pèfòmans pi bon nan ka okib n, ki nou reprezante ak Omega n okib. Epi sa a, li pou sòt seleksyon. Jis youn nan algoritm yo anpil nou kapab sèvi ak sòt yon lis. Non mwen se Tommy, e sa se cs50.