[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.