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