1 00:00:06,762 --> 00:00:09,980 [Powered by Google Translate] Tommy: Sabihin isang pagtingin sa pagpili-uuri, isang algorithm 2 00:00:09,980 --> 00:00:12,800 para sa paglalaan ng isang listahan ng mga numero at pag-uuri-uri ang mga ito. 3 00:00:12,800 --> 00:00:15,750 Isang algorithm, tandaan, ay lamang ng isang hakbang-hakbang na 4 00:00:15,750 --> 00:00:18,370 pamamaraan para sa accomplishing isang gawain. 5 00:00:18,370 --> 00:00:21,470 Ang pangunahing ideya sa likod ng pagpili-uuri ay upang hatiin 6 00:00:21,470 --> 00:00:23,390 aming listahan sa dalawang bahagi - 7 00:00:23,390 --> 00:00:26,810 isang pinagsunod-sunod na bahagi at unsorted bahagi. 8 00:00:26,810 --> 00:00:30,200 Sa bawat hakbang ng algorithm, ang bilang ay inilipat mula sa 9 00:00:30,200 --> 00:00:33,800 unsorted bahagi sa pinagsunod-sunod bahagi hanggang sa kalaunan ang 10 00:00:33,800 --> 00:00:35,880 ang buong listahan pinagsunod-sunod. 11 00:00:35,880 --> 00:00:38,510 Kaya narito ang isang listahan ng mga anim na numero - 12 00:00:38,510 --> 00:00:44,010 23, 42, 4, 16, 8, at 15. 13 00:00:44,010 --> 00:00:47,680 Sa ngayon ang buong listahan ay itinuturing unsorted. 14 00:00:47,680 --> 00:00:51,770 Kahit na ang isang numero tulad ng 16 ay maaaring mayroon na sa tamang 15 00:00:51,770 --> 00:00:56,040 lokasyon, ang aming mga algorithm ay walang paraan ng alam na hanggang sa 16 00:00:56,040 --> 00:00:57,980 ang buong listahan pinagsunod-sunod. 17 00:00:57,980 --> 00:01:01,355 Kaya naming isaalang-alang ang bawat numero sa unsorted hanggang namin-uri-uriin 18 00:01:01,355 --> 00:01:03,800 ito ating sarili. 19 00:01:03,800 --> 00:01:06,890 Alam namin na gusto namin ang listahan sa pataas na pagkakasunod-sunod. 20 00:01:06,890 --> 00:01:10,200 Kaya makikita namin nais na bumuo ng ang pinagsunod-sunod na bahagi ng aming listahan 21 00:01:10,200 --> 00:01:13,280 mula kaliwa papuntang kanan, pinakamaliit na sa pinakamalaking. 22 00:01:13,280 --> 00:01:17,970 Upang gawin iyon, kailangan naming hanapin ang minimum unsorted elemento 23 00:01:17,970 --> 00:01:21,350 at ilagay ang mga ito sa dulo ng ang pinagsunod-sunod na bahagi. 24 00:01:21,350 --> 00:01:25,370 Dahil ang listahan na ito ay hindi pinagsunod-sunod, ang tanging paraan upang gawin iyon ay sa 25 00:01:25,370 --> 00:01:29,330 tumingin sa bawat elemento sa unsorted bahagi, pagtanda 26 00:01:29,330 --> 00:01:32,010 kung aling mga elemento ang pinakamababang at paghahambing 27 00:01:32,010 --> 00:01:33,770 sa bawat elemento na iyon. 28 00:01:33,770 --> 00:01:36,150 Kaya ipapakita muna namin tumingin sa 23. 29 00:01:36,150 --> 00:01:38,650 Ito ay ang unang elemento na nakakita kami, kaya namin tandaan 30 00:01:38,650 --> 00:01:40,050 ito bilang ang minimum. 31 00:01:40,050 --> 00:01:42,320 Susunod titingnan namin sa 42. 32 00:01:42,320 --> 00:01:46,720 42 ay mas malaki kaysa sa 23, kaya 23 pa rin ang minimum. 33 00:01:46,720 --> 00:01:51,210 Susunod na 4 na mas mababa kaysa sa 23, kaya namin tandaan 4 34 00:01:51,210 --> 00:01:52,880 bilang ang bagong minimum. 35 00:01:52,880 --> 00:01:56,380 Susunod ay 16 na mas malaki kaysa sa 4, kaya 4 36 00:01:56,380 --> 00:01:57,980 ay pa rin ang minimum. 37 00:01:57,980 --> 00:02:03,670 8 ay mas malaki kaysa sa 4, at 15 ay mas malaki kaysa sa 4, kaya 4 ay dapat na 38 00:02:03,670 --> 00:02:05,980 ang pinakamaliit na unsorted elemento. 39 00:02:05,980 --> 00:02:09,350 Kaya kahit na bilang tao agad naming makita na 4 ay 40 00:02:09,350 --> 00:02:12,300 ang minimum na elemento, ang aming mga algorithm ay kailangan upang tumingin sa 41 00:02:12,300 --> 00:02:15,710 bawat unsorted elemento, kahit pagkatapos namin natagpuan ang 4 - ang 42 00:02:15,710 --> 00:02:16,860 minimum na elemento. 43 00:02:16,860 --> 00:02:19,900 Kaya ngayon na nalaman namin na ang minimum na elemento, 4, makikita namin gusto 44 00:02:19,900 --> 00:02:23,410 upang ilipat ang mga ito sa ang pinagsunod-sunod na bahagi ng listahan. 45 00:02:23,410 --> 00:02:27,320 Dahil ito ay ang unang hakbang, ang ibig sabihin nito ay gusto naming ilagay ang 4 sa 46 00:02:27,320 --> 00:02:29,680 simula ng listahan. 47 00:02:29,680 --> 00:02:33,040 Sa ngayon 23 ay sa simula ng listahan, kaya 48 00:02:33,040 --> 00:02:36,080 sabihin magpalitan ng 4 at ang 23. 49 00:02:36,080 --> 00:02:38,870 Kaya ngayon ang aming listahan ay ganito ang hitsura. 50 00:02:38,870 --> 00:02:42,710 Alam namin na 4 ay dapat na sa huling lokasyon, sapagkat ito ay 51 00:02:42,710 --> 00:02:45,890 parehong pinakamaliit na elemento at ang mga elemento sa simula 52 00:02:45,890 --> 00:02:46,960 ng listahan. 53 00:02:46,960 --> 00:02:50,650 Kaya ay nangangahulugan ito na hindi namin kailanman kailangan upang ilipat ito muli. 54 00:02:50,650 --> 00:02:53,910 Kaya sabihin ulitin ang prosesong ito upang magdagdag ng isa pang elemento sa 55 00:02:53,910 --> 00:02:55,910 pinagsunod-sunod bahagi ng listahan. 56 00:02:55,910 --> 00:02:58,950 Alam namin na hindi namin kailangan upang tumingin sa 4, dahil ito ay 57 00:02:58,950 --> 00:03:00,000 na pinagsunod-sunod. 58 00:03:00,000 --> 00:03:03,540 Upang maaari naming magsimula sa 42, na makikita namin tandaan na rin ang 59 00:03:03,540 --> 00:03:05,290 minimum na elemento. 60 00:03:05,290 --> 00:03:08,700 Kaya susunod na titingnan namin sa 23 na mas mababa kaysa sa 42, kaya namin 61 00:03:08,700 --> 00:03:11,620 tandaan 23 ang bagong minimum. 62 00:03:11,620 --> 00:03:14,870 Susunod nakita namin ang 16 na mas mababa sa 23, kaya 63 00:03:14,870 --> 00:03:16,800 16 ang bagong minimum. 64 00:03:16,800 --> 00:03:19,720 Ngayon namin tumingin sa 8 na mas mababa sa 16, kaya 65 00:03:19,720 --> 00:03:21,130 8 ang bagong minimum. 66 00:03:21,130 --> 00:03:25,900 At sa wakas ay 8 ay mas mababa sa 15, kaya alam namin na 8 ay isang minimum 67 00:03:25,900 --> 00:03:27,780 unsorted elemento. 68 00:03:27,780 --> 00:03:30,660 Kaya na nangangahulugan na dapat naming ikabit ang 8 sa pinagsunod-sunod 69 00:03:30,660 --> 00:03:32,450 bahagi ng listahan. 70 00:03:32,450 --> 00:03:35,990 Sa ngayon 4 ay ang tanging na pinagsunod-sunod elemento, kaya gusto naming upang ilagay 71 00:03:35,990 --> 00:03:38,410 ang 8 susunod sa 4. 72 00:03:38,410 --> 00:03:41,920 Dahil 42 ang unang elemento sa unsorted bahagi ng 73 00:03:41,920 --> 00:03:47,260 listahan, makikita namin gusto swap sa 42 at ang 8. 74 00:03:47,260 --> 00:03:49,680 Kaya ngayon ang aming listahan ay ganito ang hitsura. 75 00:03:49,680 --> 00:03:53,830 4 at 8 kumakatawan ang pinagsunod-sunod na bahagi ng listahan, at ang 76 00:03:53,830 --> 00:03:56,440 natitirang numero ay kumakatawan sa unsorted 77 00:03:56,440 --> 00:03:58,260 bahagi ng listahan. 78 00:03:58,260 --> 00:04:00,630 Kaya sabihin magpatuloy sa isa pang ulit. 79 00:04:00,630 --> 00:04:03,850 Magsisimula kami sa 23 oras na ito, dahil hindi namin kailangan upang tumingin sa 80 00:04:03,850 --> 00:04:05,770 ang 4 at ang 8 ito dahil na sila 81 00:04:05,770 --> 00:04:07,660 na ang pinagsunod-sunod. 82 00:04:07,660 --> 00:04:10,270 16 ay mas mababa sa 23, kaya ipapakita namin tandaan 83 00:04:10,270 --> 00:04:12,070 16 bilang bagong minimum. 84 00:04:12,070 --> 00:04:18,149 16 ay mas mababa sa 42, ngunit 15 ay mas mababa sa 16, kaya 15 ay dapat na 85 00:04:18,149 --> 00:04:20,480 ang minimum unsorted elemento. 86 00:04:20,480 --> 00:04:24,580 Kaya ngayon gusto naming swap sa 15 at ang 23 sa 87 00:04:24,580 --> 00:04:26,310 bigyan kami ng listahang ito. 88 00:04:26,310 --> 00:04:30,500 Ang pinagsunod-sunod na bahagi ng listahan ay binubuo ng 4, 8 at 15, at 89 00:04:30,500 --> 00:04:33,210 pa rin ang mga elementong ito ay unsorted. 90 00:04:33,210 --> 00:04:36,900 Ngunit ito lang kaya ang mangyayari na ang susunod na unsorted elemento, 16, 91 00:04:36,900 --> 00:04:38,480 na pinagsunod-sunod. 92 00:04:38,480 --> 00:04:42,060 Gayunpaman, walang paraan para sa aming algorithm upang malaman na 16 93 00:04:42,060 --> 00:04:45,230 ay nasa tamang lokasyon nito, kaya kailangan pa rin namin upang 94 00:04:45,230 --> 00:04:47,870 ulitin eksakto ang parehong proseso. 95 00:04:47,870 --> 00:04:53,750 Kaya naming makita na 16 ay mas mababa sa 42, at 16 ay mas mababa sa 23, kaya 96 00:04:53,750 --> 00:04:56,230 16 dapat ang minimum na elemento. 97 00:04:56,230 --> 00:04:59,010 Imposibleng magpalitan elemento na ito na may mismo, kaya kaya namin 98 00:04:59,010 --> 00:05:01,780 iwan lamang ito sa lokasyon na ito. 99 00:05:01,780 --> 00:05:04,660 Kaya kailangan namin ng isa pang pass ng aming algorithm. 100 00:05:04,660 --> 00:05:09,370 42 ay mas malaki kaysa sa 23, kaya 23 ay dapat na ang 101 00:05:09,370 --> 00:05:10,970 minimum unsorted elemento. 102 00:05:10,970 --> 00:05:17,410 Sandaling namin swap sa 23 at ang 42, magtapos namin sa aming panghuling 103 00:05:17,410 --> 00:05:18,530 pinagsunod-sunod listahan - 104 00:05:18,530 --> 00:05:23,390 4, 8, 15, 16, 23, 42. 105 00:05:23,390 --> 00:05:26,830 Alam namin na 42 ay dapat na sa tamang lugar dahil ito ang 106 00:05:26,830 --> 00:05:30,210 lamang elemento umalis, at na seleksyon-uuri. 107 00:05:30,210 --> 00:05:32,100 Natin ngayon gawing pormal ang aming algorithm na may ilang 108 00:05:32,100 --> 00:05:34,540 pseudocode. 109 00:05:34,540 --> 00:05:37,760 Sa linya ng isa, maaari naming makita na kailangan namin na isama ang sa paglipas ng 110 00:05:37,760 --> 00:05:39,530 bawat elemento ng listahan. 111 00:05:39,530 --> 00:05:42,150 Maliban sa huling elemento, dahil ang 1 elemento 112 00:05:42,150 --> 00:05:44,230 listahan pinagsunod-sunod. 113 00:05:44,230 --> 00:05:48,100 Sa ika-dalawang linya, namin isaalang-alang ang unang elemento ng unsorted 114 00:05:48,100 --> 00:05:51,080 bahagi ng listahan na ang minimum, tulad ng ginawa namin sa aming 115 00:05:51,080 --> 00:05:53,750 Halimbawa, kaya kami ay may isang bagay upang ihambing. 116 00:05:53,750 --> 00:05:57,260 Line tatlong nagsisimula ng pangalawang loop kung saan kami umulit sa paglipas ng 117 00:05:57,260 --> 00:05:59,170 bawat unsorted elemento. 118 00:05:59,170 --> 00:06:02,150 Alam namin na pagkatapos i iterations, ang pinagsunod-sunod na bahagi 119 00:06:02,150 --> 00:06:05,330 ng aming mga listahan ay dapat i elemento sa ito dahil sa bawat hakbang 120 00:06:05,330 --> 00:06:06,890 uri isang elemento. 121 00:06:06,890 --> 00:06:11,770 Kaya ang unang unsorted elemento ay dapat na sa posisyon i plus 1. 122 00:06:11,770 --> 00:06:15,440 Sa ika-apat na linya, ihambing namin ang kasalukuyang elemento sa minimum 123 00:06:15,440 --> 00:06:17,750 elemento na nasaksihan namin sa ngayon. 124 00:06:17,750 --> 00:06:20,560 Kung ang kasalukuyang elemento ay mas maliit kaysa sa minimum 125 00:06:20,560 --> 00:06:23,870 elemento, pagkatapos tandaan namin ang kasalukuyang elemento bilang bagong 126 00:06:23,870 --> 00:06:26,250 minimum sa linya limang. 127 00:06:26,250 --> 00:06:29,900 Sa wakas, sa linya anim at pitong, swap namin ang minimum 128 00:06:29,900 --> 00:06:33,080 elemento sa unang unsorted elemento, at dahil doon 129 00:06:33,080 --> 00:06:36,990 pagdagdag nito sa pinagsunod-sunod na bahagi ng listahan. 130 00:06:36,990 --> 00:06:40,030 Sa sandaling mayroon kami ng isang algorithm, isang mahalagang tanong sa magtanong 131 00:06:40,030 --> 00:06:43,370 ating sarili bilang programmer kung gaano katagal na? 132 00:06:43,370 --> 00:06:46,970 Ipapakita muna namin tanungin ang tanong kung gaano katagal aabutin para sa 133 00:06:46,970 --> 00:06:50,070 algorithm upang tumakbo sa ang pinakamasama kaso? 134 00:06:50,070 --> 00:06:51,640 Manariwa sa diwa kumakatawan namin ito tumatakbo 135 00:06:51,640 --> 00:06:55,060 oras na may malaking O pagtatanda. 136 00:06:55,060 --> 00:06:58,650 Upang matukoy ang minimum unsorted elemento, namin 137 00:06:58,650 --> 00:07:01,880 mahalagang ay upang ihambing ang bawat elemento sa listahan upang 138 00:07:01,880 --> 00:07:04,040 bawat iba pang mga elemento sa listahan. 139 00:07:04,040 --> 00:07:08,430 Intuitively, ito tunog tulad ng isang O ng n squared operasyon. 140 00:07:08,430 --> 00:07:12,050 Naghahanap sa aming pseudocode, kami ay mayroon ding isang loop na nested sa loob 141 00:07:12,050 --> 00:07:14,420 isa pang loop, na sa katunayan Mukhang isang O 142 00:07:14,420 --> 00:07:16,480 ng n squared operasyon. 143 00:07:16,480 --> 00:07:19,250 Gayunpaman, tandaan na hindi namin kailangan upang tumingin sa ibabaw ng 144 00:07:19,250 --> 00:07:23,460 buong listahan kapag tinutukoy ang minimum unsorted elemento? 145 00:07:23,460 --> 00:07:26,600 Sa sandaling alam namin na 4 ay pinagsunod-sunod, halimbawa, hindi namin ginawa 146 00:07:26,600 --> 00:07:28,170 kailangang tingnan itong muli. 147 00:07:28,170 --> 00:07:31,020 Kaya ito mas mababa ang oras? 148 00:07:31,020 --> 00:07:34,510 Para sa aming listahan ng haba 6, kailangan naming gumawa ng limang 149 00:07:34,510 --> 00:07:37,990 paghahambing para sa unang elemento, apat na mga paghahambing para sa 150 00:07:37,990 --> 00:07:40,750 ang pangalawang elemento, at iba pa. 151 00:07:40,750 --> 00:07:44,690 Iyon ay nangangahulugan na ang kabuuang bilang ng mga hakbang ay ang kabuuan ng 152 00:07:44,690 --> 00:07:49,160 ang mga integer mula sa 1 sa haba ng listahan minus 1. 153 00:07:49,160 --> 00:07:51,005 Maaari naming kumatawan ang mga ito gamit ang isang kabuuan. 154 00:07:57,980 --> 00:07:59,910 Hindi namin pumunta sa summations dito. 155 00:07:59,910 --> 00:08:04,900 Ngunit ito lumiliko ang kabuuan na ito ay katumbas sa n beses 156 00:08:04,900 --> 00:08:07,540 n minus 1 sa 2. 157 00:08:07,540 --> 00:08:14,220 O equivalently, n nakalapat sa 2 minus n paglipas ng 2. 158 00:08:14,220 --> 00:08:18,860 Kapag pakikipag-usap tungkol sa asymptotic runtime, ito n squared termino 159 00:08:18,860 --> 00:08:22,070 ay upang dominahin ito n termino. 160 00:08:22,070 --> 00:08:27,850 Kaya pagpili-uuri O n squared. 161 00:08:27,850 --> 00:08:31,460 Manariwa sa diwa na sa aming halimbawa, pagpili-uuri pa rin na kinakailangan upang 162 00:08:31,460 --> 00:08:33,850 suriin kung ang isang numero na ay na pinagsunod-sunod 163 00:08:33,850 --> 00:08:35,450 kinakailangan upang ililipat. 164 00:08:35,450 --> 00:08:38,929 Sa gayon ay nangangahulugan na kung tumakbo kami ng pagpili ng uri sa isang na 165 00:08:38,929 --> 00:08:43,070 pinagsunod-sunod listahan, nangangailangan ang parehong bilang ng mga hakbang habang ito 166 00:08:43,070 --> 00:08:46,340 gagawin kapag tumatakbo sa loob ng isang ganap na unsorted listahan. 167 00:08:46,340 --> 00:08:51,470 Kaya pagpili-uuri ay may pinakamahusay na pagganap ng kaso ng n squared, 168 00:08:51,470 --> 00:08:56,820 kung saan ay kumakatawan namin may wakas n squared. 169 00:08:56,820 --> 00:08:58,600 At na ito para sa pagpili-uuri. 170 00:08:58,600 --> 00:09:00,630 Isa lamang ng maraming mga algorithm ng aming makakaya 171 00:09:00,630 --> 00:09:02,390 gamitin upang pag-uri-uriin ang isang listahan. 172 00:09:02,390 --> 00:09:05,910 Ang pangalan ko ay Tommy, at ito ay cs50.