[Powered by Google Translate] Tommy: Ni rigardu selektado varo, algoritmo
por preni listo de nombroj kaj ordigi ilin.
Algoritmo, memoru, estas simple iom post paŝo
proceduro por plenumi taskon.
La baza ideo malantaŭ selektado varo estas dividi
nia listo en du partojn -
a ordo parton kaj unsorted parton.
Je ĉiu paŝo de la algoritmo, numero estas movita de la
unsorted porcion al la ordo parton ĝis fine la
tuta listo estas ordigita.
Do jen listo de ses nombroj -
23, 42, 4, 16, 8, kaj 15.
Ĝuste nun la tutan liston konsideras Unsorted.
Kvankam kelkaj kiel 16 povus jam esti en lia ĝentila
situo, nia algoritmo ne havas manieron de scii ke ĝis la
tuta listo estas ordigita.
Do ni opinias ĉiun numeron por esti Unsorted ĝis ni ordigi
ĝin.
Ni scias, ke ni deziras ke la listo esti en suprenira ordo.
Do ni volas konstrui la ordo parton de nia listo
de maldekstre al dekstre, la plej malgranda al granda.
Por fari tion, ni devos trovi la minimuma unsorted elemento
kaj metis ĝin ĉe la fino de la ordo parton.
Ekde ĉi tiu listo estas ne ordigita, la sola maniero por fari tion estas
rigardi ĉiu elemento en la unsorted parton, memorante
kiu elemento estas la plej malalta kaj komparante
ĉiu elemento al tiu.
Do ni unue rigardu la 23.
Ĉi tiu estas la unua ero ni vidis, do ni devos memori
kiel la minimumo.
Sekva ni rigardu 42.
42 estas pli granda ol 23, do 23 estas ankoraŭ la minimumo.
Sekva estas la 4 kiu estas malpli ol 23, do ni devos memori 4
kiel la nova minimumo.
Sekva estas la 16 kiu estas pli granda ol 4, do 4
ankoraŭ estas la minimumo.
8 estas pli granda ol 4, kaj 15 estas pli granda ol 4, do 4 devas esti
la plej malgranda unsorted elemento.
Do eĉ se kiel homoj povas tuj vidi, ke 4 estas
la minimuma elemento, nia algoritmo bezonas rigardi
ĉiun unsorted elemento, eĉ post ni trovis la 4 - la
minimuma elemento.
Do nun ni trovis la minimuman elementon, 4, ni volas
movi ĝin en la ordo parton de la listo.
Ekde ĉi tiu estas la unua paŝo, tiu signifas ke ni volas meti 4, je
la komenco de la listo.
Ĝuste nun 23 estas ĉe la komenco de la listo, tiel
ni interŝanĝas la 4 kaj la 23.
Do nun nia listo similas ĉi.
Ni scias ke 4 devas esti en lia fina loko, ĉar ĝi estas
ambaŭ la plej malgranda elemento kaj la elemento komence
de la listo.
Do tio signifas ke ni ne bezonos por movi ĝin denove.
Do ni ripetu ĉi tiun procezon por aldoni alian elementon al la
ordo parton de la listo.
Ni scias, ke ni ne bezonas rigardi la 4, ĉar ĝi estas
Jam ordo.
Do ni povas starti je la 42, kiun ni devos memori kiel la
minimuma elemento.
Tiel proksima ni rigardu la 23 kiu estas malpli ol 42, do ni
memori 23 estas la nova minimumo.
Ni tuj vidos la 16 kiu estas malpli ol 23, do
16 estas la nova minimumo.
Nun ni rigardu la 8 kiu estas malpli ol 16, do
8 estas la nova minimumo.
Kaj fine 8 estas malpli ol 15, do ni scias, ke 8 estas minimumo
unsorted elemento.
Do tio signifas ke ni devas aldonas 8 al la ordo
parton de la listo.
Ĝuste nun 4 estas la sola ordo elemento, do ni volas meti
la 8 apud la 4.
Ekde 42 estas la unua ero en la unsorted parto de la
listo, ni volas interŝanĝi la 42 kaj la 8.
Do nun nia listo similas ĉi.
4 kaj 8 reprezentas la ordo parton de la listo, kaj la
ceteraj numeroj reprezentas la unsorted
parton de la listo.
Do ni daŭrigas kun alia ripeto.
Ni komencas kun 23 ĉi tiu tempo, kiam ni ne bezonas rigardi
la 4 kaj la 8 plu ĉar mi
jam ordo.
16 estas malpli ol 23, do ni devos memori
16 kiel la nova minimumo.
16 estas malpli ol 42, sed 15 estas malpli ol 16, do 15 devas esti
la minimuma unsorted elemento.
Do nun ni volas interŝanĝi la 15 kaj la 23 al
doni al ni ĉi listo.
La ordo parton de la listo konsistas de 4, 8 kaj 15, kaj
tiuj elementoj estas ankoraŭ Unsorted.
Sed ĝuste tial okazas, ke la venonta unsorted elemento, 16,
Jam ordo.
Tamen, ne estas maniero por nia algoritmo por scii ke 16
jam estas en ĝia ĝusta loko, do ni ankoraŭ bezonas
ripeti ĝuste la sama procezo.
Do ni vidas, ke 16 estas malpli ol 42, kaj 16 estas malpli ol 23, do
16 devas esti la minimuma elemento.
Estas neeble interŝanĝi ĉi elemento kun sin, do ni povas
simple lasi ĝin en ĉi tiu loko.
Do ni bezonas unu pli pasas de nia algoritmo.
42 estas pli granda ol 23, do 23 devas esti la
minimuma unsorted elemento.
Iam ni interŝanĝas la 23 kaj la 42, ni finu kun niaj fino
ordo listo -
4, 8, 15, 16, 23, 42.
Ni scias 42 devas esti en la ĝentila loko pro tio estas la
nur elemento forlasis, kaj tio estas elekto varon.
Ni nun formaligi nian algoritmon kun iuj
_pseudocode_.
On line, ni povas vidi ke ni bezonas por integri super
ĉiu ero de la listo.
Krom la lasta elemento, ekde la 1 elemento
listo estas jam ordo.
On line du, ni konsideras la unua elemento de la unsorted
parton de la listo esti la minimumo, kiel ni faris kun niaj
Ekzemple, do ni havas ion por kompari al.
Linio tri komencas dua iteracio en kiu ni persisti super
ĉiu unsorted elemento.
Ni scias, ke post i iteraciones, la ordo parto
de nia listo devas havi i elementojn en ĝi ekde ĉiu paŝo
specoj unu elemento.
Do la unua unsorted elemento devas esti en pozicio i plus 1.
On line kvar, ni komparu la nunan elementon al la minimumo
elemento kiu ni vidis ĝis nun.
Se la nuna ero estas pli malgranda ol la minimumo
ero, tiam ni memoros la nuna ero kiel nova
minimuma on line kvin.
Fine, la linioj ses kaj sep, ni interŝanĝas la minimuma
ero kun la unua unsorted elemento, tiel
aldoni ĝin al la ordo parton de la listo.
Iam ni havi algoritmo, grava demando
nin kiel programistoj estas kiom da tempo kiun portas?
Ni unue demandi la demandon kiom da tempo necesas por ĉi
algoritmo por kuri en la plej malbona kazo?
Memori ni reprezentas ĉi kurado
tempon kun granda O skribmaniero.
Por determini la minimuma unsorted elemento, ni
esence devis kompari ĉiu elemento en la listo de
ĉiu alia ero en la listo.
Intuicie, ĉi sonojn kiel ho de n kvadrataj operacio.
Rigardante nian _pseudocode_, ni ankaŭ havas buklo anidado interne
alia buklo, kio efektive sonas kiel ho
de n kvadrataj operacio.
Tamen, memoru, ke ni ne bezonas rigardi super la
tutan liston kiam determinante la minimuma unsorted elemento?
Iam ni sciis ke la 4 estis ordo, ekzemple, ni ne
bezonas rigardi ĝin denove.
Do faras ĉi suba la rula tempo?
Por nia listo de longo 6, ni bezonas por fari kvin
komparoj por la unua elemento, kvar komparojn por
la dua elemento, kaj tiel plu.
Tio signifas ke la tuta nombro de paŝoj estas la sumo de
la entjeroj de 1 al la longo de la listo minus 1.
Ni povas reprezenti ĉi kun sumado.
Ni ne iros al sumadoj, sumadas tie.
Sed ĝi rezultas ke tiu sumado estas egala al n fojoj
n minus 1 pli ol 2.
Aŭ ekvivalente, n kvadrata super 2 minus n super 2.
Kiam parolante pri asimptota runtime, ĉi n kvadrataj termino
tuj regi tiun n termino.
Do selektado varo estas ho de n kvadratoj.
Rememoru, ke en nia ekzemplo, selektado speco ankoraŭ bezonis
kontroli ĉu numero kiu jam ordo
bezonis esti movita.
Do tio signifas ke se ni kuris selektado speco super jam
ordo listo, ĝi postulus la sama nombro de paŝoj kiel
would kiam alveturante tute unsorted listo.
Do selektado speco havas pli bona kazo agado de n kvadratoj,
kiuj ni reprezentas kun omega n kvadratoj.
Kaj tio estas por selektado varon.
Nur unu el la multaj algoritmoj ni povas
uzi ordigi liston.
Mia nomo estas Tommy, kaj ĉi tiu estas cs50.