1 00:00:06,762 --> 00:00:09,980 [Powered by Google Translate] Tommy: Ni rigardu selektado varo, algoritmo 2 00:00:09,980 --> 00:00:12,800 por preni listo de nombroj kaj ordigi ilin. 3 00:00:12,800 --> 00:00:15,750 Algoritmo, memoru, estas simple iom post paŝo 4 00:00:15,750 --> 00:00:18,370 proceduro por plenumi taskon. 5 00:00:18,370 --> 00:00:21,470 La baza ideo malantaŭ selektado varo estas dividi 6 00:00:21,470 --> 00:00:23,390 nia listo en du partojn - 7 00:00:23,390 --> 00:00:26,810 a ordo parton kaj unsorted parton. 8 00:00:26,810 --> 00:00:30,200 Je ĉiu paŝo de la algoritmo, numero estas movita de la 9 00:00:30,200 --> 00:00:33,800 unsorted porcion al la ordo parton ĝis fine la 10 00:00:33,800 --> 00:00:35,880 tuta listo estas ordigita. 11 00:00:35,880 --> 00:00:38,510 Do jen listo de ses nombroj - 12 00:00:38,510 --> 00:00:44,010 23, 42, 4, 16, 8, kaj 15. 13 00:00:44,010 --> 00:00:47,680 Ĝuste nun la tutan liston konsideras Unsorted. 14 00:00:47,680 --> 00:00:51,770 Kvankam kelkaj kiel 16 povus jam esti en lia ĝentila 15 00:00:51,770 --> 00:00:56,040 situo, nia algoritmo ne havas manieron de scii ke ĝis la 16 00:00:56,040 --> 00:00:57,980 tuta listo estas ordigita. 17 00:00:57,980 --> 00:01:01,355 Do ni opinias ĉiun numeron por esti Unsorted ĝis ni ordigi 18 00:01:01,355 --> 00:01:03,800 ĝin. 19 00:01:03,800 --> 00:01:06,890 Ni scias, ke ni deziras ke la listo esti en suprenira ordo. 20 00:01:06,890 --> 00:01:10,200 Do ni volas konstrui la ordo parton de nia listo 21 00:01:10,200 --> 00:01:13,280 de maldekstre al dekstre, la plej malgranda al granda. 22 00:01:13,280 --> 00:01:17,970 Por fari tion, ni devos trovi la minimuma unsorted elemento 23 00:01:17,970 --> 00:01:21,350 kaj metis ĝin ĉe la fino de la ordo parton. 24 00:01:21,350 --> 00:01:25,370 Ekde ĉi tiu listo estas ne ordigita, la sola maniero por fari tion estas 25 00:01:25,370 --> 00:01:29,330 rigardi ĉiu elemento en la unsorted parton, memorante 26 00:01:29,330 --> 00:01:32,010 kiu elemento estas la plej malalta kaj komparante 27 00:01:32,010 --> 00:01:33,770 ĉiu elemento al tiu. 28 00:01:33,770 --> 00:01:36,150 Do ni unue rigardu la 23. 29 00:01:36,150 --> 00:01:38,650 Ĉi tiu estas la unua ero ni vidis, do ni devos memori 30 00:01:38,650 --> 00:01:40,050 kiel la minimumo. 31 00:01:40,050 --> 00:01:42,320 Sekva ni rigardu 42. 32 00:01:42,320 --> 00:01:46,720 42 estas pli granda ol 23, do 23 estas ankoraŭ la minimumo. 33 00:01:46,720 --> 00:01:51,210 Sekva estas la 4 kiu estas malpli ol 23, do ni devos memori 4 34 00:01:51,210 --> 00:01:52,880 kiel la nova minimumo. 35 00:01:52,880 --> 00:01:56,380 Sekva estas la 16 kiu estas pli granda ol 4, do 4 36 00:01:56,380 --> 00:01:57,980 ankoraŭ estas la minimumo. 37 00:01:57,980 --> 00:02:03,670 8 estas pli granda ol 4, kaj 15 estas pli granda ol 4, do 4 devas esti 38 00:02:03,670 --> 00:02:05,980 la plej malgranda unsorted elemento. 39 00:02:05,980 --> 00:02:09,350 Do eĉ se kiel homoj povas tuj vidi, ke 4 estas 40 00:02:09,350 --> 00:02:12,300 la minimuma elemento, nia algoritmo bezonas rigardi 41 00:02:12,300 --> 00:02:15,710 ĉiun unsorted elemento, eĉ post ni trovis la 4 - la 42 00:02:15,710 --> 00:02:16,860 minimuma elemento. 43 00:02:16,860 --> 00:02:19,900 Do nun ni trovis la minimuman elementon, 4, ni volas 44 00:02:19,900 --> 00:02:23,410 movi ĝin en la ordo parton de la listo. 45 00:02:23,410 --> 00:02:27,320 Ekde ĉi tiu estas la unua paŝo, tiu signifas ke ni volas meti 4, je 46 00:02:27,320 --> 00:02:29,680 la komenco de la listo. 47 00:02:29,680 --> 00:02:33,040 Ĝuste nun 23 estas ĉe la komenco de la listo, tiel 48 00:02:33,040 --> 00:02:36,080 ni interŝanĝas la 4 kaj la 23. 49 00:02:36,080 --> 00:02:38,870 Do nun nia listo similas ĉi. 50 00:02:38,870 --> 00:02:42,710 Ni scias ke 4 devas esti en lia fina loko, ĉar ĝi estas 51 00:02:42,710 --> 00:02:45,890 ambaŭ la plej malgranda elemento kaj la elemento komence 52 00:02:45,890 --> 00:02:46,960 de la listo. 53 00:02:46,960 --> 00:02:50,650 Do tio signifas ke ni ne bezonos por movi ĝin denove. 54 00:02:50,650 --> 00:02:53,910 Do ni ripetu ĉi tiun procezon por aldoni alian elementon al la 55 00:02:53,910 --> 00:02:55,910 ordo parton de la listo. 56 00:02:55,910 --> 00:02:58,950 Ni scias, ke ni ne bezonas rigardi la 4, ĉar ĝi estas 57 00:02:58,950 --> 00:03:00,000 Jam ordo. 58 00:03:00,000 --> 00:03:03,540 Do ni povas starti je la 42, kiun ni devos memori kiel la 59 00:03:03,540 --> 00:03:05,290 minimuma elemento. 60 00:03:05,290 --> 00:03:08,700 Tiel proksima ni rigardu la 23 kiu estas malpli ol 42, do ni 61 00:03:08,700 --> 00:03:11,620 memori 23 estas la nova minimumo. 62 00:03:11,620 --> 00:03:14,870 Ni tuj vidos la 16 kiu estas malpli ol 23, do 63 00:03:14,870 --> 00:03:16,800 16 estas la nova minimumo. 64 00:03:16,800 --> 00:03:19,720 Nun ni rigardu la 8 kiu estas malpli ol 16, do 65 00:03:19,720 --> 00:03:21,130 8 estas la nova minimumo. 66 00:03:21,130 --> 00:03:25,900 Kaj fine 8 estas malpli ol 15, do ni scias, ke 8 estas minimumo 67 00:03:25,900 --> 00:03:27,780 unsorted elemento. 68 00:03:27,780 --> 00:03:30,660 Do tio signifas ke ni devas aldonas 8 al la ordo 69 00:03:30,660 --> 00:03:32,450 parton de la listo. 70 00:03:32,450 --> 00:03:35,990 Ĝuste nun 4 estas la sola ordo elemento, do ni volas meti 71 00:03:35,990 --> 00:03:38,410 la 8 apud la 4. 72 00:03:38,410 --> 00:03:41,920 Ekde 42 estas la unua ero en la unsorted parto de la 73 00:03:41,920 --> 00:03:47,260 listo, ni volas interŝanĝi la 42 kaj la 8. 74 00:03:47,260 --> 00:03:49,680 Do nun nia listo similas ĉi. 75 00:03:49,680 --> 00:03:53,830 4 kaj 8 reprezentas la ordo parton de la listo, kaj la 76 00:03:53,830 --> 00:03:56,440 ceteraj numeroj reprezentas la unsorted 77 00:03:56,440 --> 00:03:58,260 parton de la listo. 78 00:03:58,260 --> 00:04:00,630 Do ni daŭrigas kun alia ripeto. 79 00:04:00,630 --> 00:04:03,850 Ni komencas kun 23 ĉi tiu tempo, kiam ni ne bezonas rigardi 80 00:04:03,850 --> 00:04:05,770 la 4 kaj la 8 plu ĉar mi 81 00:04:05,770 --> 00:04:07,660 jam ordo. 82 00:04:07,660 --> 00:04:10,270 16 estas malpli ol 23, do ni devos memori 83 00:04:10,270 --> 00:04:12,070 16 kiel la nova minimumo. 84 00:04:12,070 --> 00:04:18,149 16 estas malpli ol 42, sed 15 estas malpli ol 16, do 15 devas esti 85 00:04:18,149 --> 00:04:20,480 la minimuma unsorted elemento. 86 00:04:20,480 --> 00:04:24,580 Do nun ni volas interŝanĝi la 15 kaj la 23 al 87 00:04:24,580 --> 00:04:26,310 doni al ni ĉi listo. 88 00:04:26,310 --> 00:04:30,500 La ordo parton de la listo konsistas de 4, 8 kaj 15, kaj 89 00:04:30,500 --> 00:04:33,210 tiuj elementoj estas ankoraŭ Unsorted. 90 00:04:33,210 --> 00:04:36,900 Sed ĝuste tial okazas, ke la venonta unsorted elemento, 16, 91 00:04:36,900 --> 00:04:38,480 Jam ordo. 92 00:04:38,480 --> 00:04:42,060 Tamen, ne estas maniero por nia algoritmo por scii ke 16 93 00:04:42,060 --> 00:04:45,230 jam estas en ĝia ĝusta loko, do ni ankoraŭ bezonas 94 00:04:45,230 --> 00:04:47,870 ripeti ĝuste la sama procezo. 95 00:04:47,870 --> 00:04:53,750 Do ni vidas, ke 16 estas malpli ol 42, kaj 16 estas malpli ol 23, do 96 00:04:53,750 --> 00:04:56,230 16 devas esti la minimuma elemento. 97 00:04:56,230 --> 00:04:59,010 Estas neeble interŝanĝi ĉi elemento kun sin, do ni povas 98 00:04:59,010 --> 00:05:01,780 simple lasi ĝin en ĉi tiu loko. 99 00:05:01,780 --> 00:05:04,660 Do ni bezonas unu pli pasas de nia algoritmo. 100 00:05:04,660 --> 00:05:09,370 42 estas pli granda ol 23, do 23 devas esti la 101 00:05:09,370 --> 00:05:10,970 minimuma unsorted elemento. 102 00:05:10,970 --> 00:05:17,410 Iam ni interŝanĝas la 23 kaj la 42, ni finu kun niaj fino 103 00:05:17,410 --> 00:05:18,530 ordo listo - 104 00:05:18,530 --> 00:05:23,390 4, 8, 15, 16, 23, 42. 105 00:05:23,390 --> 00:05:26,830 Ni scias 42 devas esti en la ĝentila loko pro tio estas la 106 00:05:26,830 --> 00:05:30,210 nur elemento forlasis, kaj tio estas elekto varon. 107 00:05:30,210 --> 00:05:32,100 Ni nun formaligi nian algoritmon kun iuj 108 00:05:32,100 --> 00:05:34,540 _pseudocode_. 109 00:05:34,540 --> 00:05:37,760 On line, ni povas vidi ke ni bezonas por integri super 110 00:05:37,760 --> 00:05:39,530 ĉiu ero de la listo. 111 00:05:39,530 --> 00:05:42,150 Krom la lasta elemento, ekde la 1 elemento 112 00:05:42,150 --> 00:05:44,230 listo estas jam ordo. 113 00:05:44,230 --> 00:05:48,100 On line du, ni konsideras la unua elemento de la unsorted 114 00:05:48,100 --> 00:05:51,080 parton de la listo esti la minimumo, kiel ni faris kun niaj 115 00:05:51,080 --> 00:05:53,750 Ekzemple, do ni havas ion por kompari al. 116 00:05:53,750 --> 00:05:57,260 Linio tri komencas dua iteracio en kiu ni persisti super 117 00:05:57,260 --> 00:05:59,170 ĉiu unsorted elemento. 118 00:05:59,170 --> 00:06:02,150 Ni scias, ke post i iteraciones, la ordo parto 119 00:06:02,150 --> 00:06:05,330 de nia listo devas havi i elementojn en ĝi ekde ĉiu paŝo 120 00:06:05,330 --> 00:06:06,890 specoj unu elemento. 121 00:06:06,890 --> 00:06:11,770 Do la unua unsorted elemento devas esti en pozicio i plus 1. 122 00:06:11,770 --> 00:06:15,440 On line kvar, ni komparu la nunan elementon al la minimumo 123 00:06:15,440 --> 00:06:17,750 elemento kiu ni vidis ĝis nun. 124 00:06:17,750 --> 00:06:20,560 Se la nuna ero estas pli malgranda ol la minimumo 125 00:06:20,560 --> 00:06:23,870 ero, tiam ni memoros la nuna ero kiel nova 126 00:06:23,870 --> 00:06:26,250 minimuma on line kvin. 127 00:06:26,250 --> 00:06:29,900 Fine, la linioj ses kaj sep, ni interŝanĝas la minimuma 128 00:06:29,900 --> 00:06:33,080 ero kun la unua unsorted elemento, tiel 129 00:06:33,080 --> 00:06:36,990 aldoni ĝin al la ordo parton de la listo. 130 00:06:36,990 --> 00:06:40,030 Iam ni havi algoritmo, grava demando 131 00:06:40,030 --> 00:06:43,370 nin kiel programistoj estas kiom da tempo kiun portas? 132 00:06:43,370 --> 00:06:46,970 Ni unue demandi la demandon kiom da tempo necesas por ĉi 133 00:06:46,970 --> 00:06:50,070 algoritmo por kuri en la plej malbona kazo? 134 00:06:50,070 --> 00:06:51,640 Memori ni reprezentas ĉi kurado 135 00:06:51,640 --> 00:06:55,060 tempon kun granda O skribmaniero. 136 00:06:55,060 --> 00:06:58,650 Por determini la minimuma unsorted elemento, ni 137 00:06:58,650 --> 00:07:01,880 esence devis kompari ĉiu elemento en la listo de 138 00:07:01,880 --> 00:07:04,040 ĉiu alia ero en la listo. 139 00:07:04,040 --> 00:07:08,430 Intuicie, ĉi sonojn kiel ho de n kvadrataj operacio. 140 00:07:08,430 --> 00:07:12,050 Rigardante nian _pseudocode_, ni ankaŭ havas buklo anidado interne 141 00:07:12,050 --> 00:07:14,420 alia buklo, kio efektive sonas kiel ho 142 00:07:14,420 --> 00:07:16,480 de n kvadrataj operacio. 143 00:07:16,480 --> 00:07:19,250 Tamen, memoru, ke ni ne bezonas rigardi super la 144 00:07:19,250 --> 00:07:23,460 tutan liston kiam determinante la minimuma unsorted elemento? 145 00:07:23,460 --> 00:07:26,600 Iam ni sciis ke la 4 estis ordo, ekzemple, ni ne 146 00:07:26,600 --> 00:07:28,170 bezonas rigardi ĝin denove. 147 00:07:28,170 --> 00:07:31,020 Do faras ĉi suba la rula tempo? 148 00:07:31,020 --> 00:07:34,510 Por nia listo de longo 6, ni bezonas por fari kvin 149 00:07:34,510 --> 00:07:37,990 komparoj por la unua elemento, kvar komparojn por 150 00:07:37,990 --> 00:07:40,750 la dua elemento, kaj tiel plu. 151 00:07:40,750 --> 00:07:44,690 Tio signifas ke la tuta nombro de paŝoj estas la sumo de 152 00:07:44,690 --> 00:07:49,160 la entjeroj de 1 al la longo de la listo minus 1. 153 00:07:49,160 --> 00:07:51,005 Ni povas reprezenti ĉi kun sumado. 154 00:07:57,980 --> 00:07:59,910 Ni ne iros al sumadoj, sumadas tie. 155 00:07:59,910 --> 00:08:04,900 Sed ĝi rezultas ke tiu sumado estas egala al n fojoj 156 00:08:04,900 --> 00:08:07,540 n minus 1 pli ol 2. 157 00:08:07,540 --> 00:08:14,220 Aŭ ekvivalente, n kvadrata super 2 minus n super 2. 158 00:08:14,220 --> 00:08:18,860 Kiam parolante pri asimptota runtime, ĉi n kvadrataj termino 159 00:08:18,860 --> 00:08:22,070 tuj regi tiun n termino. 160 00:08:22,070 --> 00:08:27,850 Do selektado varo estas ho de n kvadratoj. 161 00:08:27,850 --> 00:08:31,460 Rememoru, ke en nia ekzemplo, selektado speco ankoraŭ bezonis 162 00:08:31,460 --> 00:08:33,850 kontroli ĉu numero kiu jam ordo 163 00:08:33,850 --> 00:08:35,450 bezonis esti movita. 164 00:08:35,450 --> 00:08:38,929 Do tio signifas ke se ni kuris selektado speco super jam 165 00:08:38,929 --> 00:08:43,070 ordo listo, ĝi postulus la sama nombro de paŝoj kiel 166 00:08:43,070 --> 00:08:46,340 would kiam alveturante tute unsorted listo. 167 00:08:46,340 --> 00:08:51,470 Do selektado speco havas pli bona kazo agado de n kvadratoj, 168 00:08:51,470 --> 00:08:56,820 kiuj ni reprezentas kun omega n kvadratoj. 169 00:08:56,820 --> 00:08:58,600 Kaj tio estas por selektado varon. 170 00:08:58,600 --> 00:09:00,630 Nur unu el la multaj algoritmoj ni povas 171 00:09:00,630 --> 00:09:02,390 uzi ordigi liston. 172 00:09:02,390 --> 00:09:05,910 Mia nomo estas Tommy, kaj ĉi tiu estas cs50.