1 00:00:06,762 --> 00:00:09,980 [Powered by Google Translate] Tommy: Paimkime atrankoje rūšiuoti išvaizdą, algoritmas 2 00:00:09,980 --> 00:00:12,800 numerių sąrašą ir rūšiavimą. 3 00:00:12,800 --> 00:00:15,750 Algoritmas, atminkite, kad yra tiesiog žingsnis po žingsnio 4 00:00:15,750 --> 00:00:18,370 tvarka įvykdyti užduotį. 5 00:00:18,370 --> 00:00:21,470 Pagrindinė idėja atrankos rūšiuoti yra suskirstyti 6 00:00:21,470 --> 00:00:23,390 mūsų sąrašą į dvi dalis - 7 00:00:23,390 --> 00:00:26,810 surūšiuoti dalis ir nerūšiuotų dalis. 8 00:00:26,810 --> 00:00:30,200 Kiekvieno algoritmo žingsnyje, numeris bus perkeltas iš 9 00:00:30,200 --> 00:00:33,800 nerūšiuotų dalis išrūšiuotų dalis, kol galiausiai 10 00:00:33,800 --> 00:00:35,880 Visas sąrašas surūšiuotas. 11 00:00:35,880 --> 00:00:38,510 Taigi čia šešių numerių sąrašas - 12 00:00:38,510 --> 00:00:44,010 23, 42, 4, 16, 8, ir 15. 13 00:00:44,010 --> 00:00:47,680 Dabar visas sąrašas yra laikomas nerūšiuotų. 14 00:00:47,680 --> 00:00:51,770 Nors kaip 16 jau gali būti jo teisingas 15 00:00:51,770 --> 00:00:56,040 vieta, mūsų algoritmas neturi žinodami, kad, kol kelią 16 00:00:56,040 --> 00:00:57,980 Visas sąrašas surūšiuotas. 17 00:00:57,980 --> 00:01:01,355 Taigi, mes atsižvelgsime į kiekvieną numerį, kurį nerūšiuotų, kol mes rūšiuoti 18 00:01:01,355 --> 00:01:03,800 tai patys. 19 00:01:03,800 --> 00:01:06,890 Mes žinome, kad mes norime, sąrašas sudaromas didėjančia seka. 20 00:01:06,890 --> 00:01:10,200 Taigi, mes norime sukurti surūšiuoti dalį mūsų sąraše 21 00:01:10,200 --> 00:01:13,280 iš kairės į dešinę, mažiausio iki didžiausio. 22 00:01:13,280 --> 00:01:17,970 Norėdami tai padaryti, mums reikia rasti mažiausią nerūšiuotų elementas 23 00:01:17,970 --> 00:01:21,350 ir įdėti jį išrūšiuotų dalies pabaigoje. 24 00:01:21,350 --> 00:01:25,370 Kadangi šis sąrašas nėra rūšiuojamos, vienintelis būdas tai padaryti yra 25 00:01:25,370 --> 00:01:29,330 pažvelgti į kiekvieno elemento į nerūšiuotų dalis, prisimindamas 26 00:01:29,330 --> 00:01:32,010 , kuris elementas yra žemiausias ir lyginant 27 00:01:32,010 --> 00:01:33,770 kiekvienas elementas, kad. 28 00:01:33,770 --> 00:01:36,150 Taigi, mes pirmą kartą pažvelgti į 23 d. 29 00:01:36,150 --> 00:01:38,650 Tai yra pirmasis elementas, mes matėme, todėl mes prisiminti 30 00:01:38,650 --> 00:01:40,050 kaip minimum. 31 00:01:40,050 --> 00:01:42,320 Kitas mes pažvelgti į 42. 32 00:01:42,320 --> 00:01:46,720 42 yra didesnis nei 23, todėl 23 yra dar minimalus. 33 00:01:46,720 --> 00:01:51,210 Kitas yra 4, kuris yra mažesnis kaip 23, todėl mes prisiminti 4 34 00:01:51,210 --> 00:01:52,880 su nauju minimaliu. 35 00:01:52,880 --> 00:01:56,380 Kitas yra 16, kuris yra didesnis nei 4, SO 4 36 00:01:56,380 --> 00:01:57,980 vis dar yra minimalus. 37 00:01:57,980 --> 00:02:03,670 8 yra didesnis nei 4, ir 15 yra didesnis nei 4, tad 4 turi būti 38 00:02:03,670 --> 00:02:05,980 mažiausias nerūšiuotų elementas. 39 00:02:05,980 --> 00:02:09,350 Taigi, nors, kaip žmogui, mes galime iš karto pamatyti, kad 4 yra 40 00:02:09,350 --> 00:02:12,300 minimalus elementas, mūsų algoritmas turi išnagrinėti 41 00:02:12,300 --> 00:02:15,710 kas nerūšiuotų elementas, net po to, kai mes pastebėjome, 4 - 42 00:02:15,710 --> 00:02:16,860 minimalus elementas. 43 00:02:16,860 --> 00:02:19,900 Taigi dabar, kad mes pastebėjome, minimalų elementą, 4, mes nori 44 00:02:19,900 --> 00:02:23,410 perkelti jį į išrūšiuotų sąrašo dalį. 45 00:02:23,410 --> 00:02:27,320 , Nes tai yra pirmasis žingsnis, tai reiškia, kad mes norime įdėti 4 46 00:02:27,320 --> 00:02:29,680 sąrašo pradžioje. 47 00:02:29,680 --> 00:02:33,040 Dabar 23 yra sąrašo pradžioje, todėl 48 00:02:33,040 --> 00:02:36,080 tegul apsikeitimo 4 ir 23. 49 00:02:36,080 --> 00:02:38,870 Taigi dabar mūsų sąrašas atrodo taip. 50 00:02:38,870 --> 00:02:42,710 Mes žinome, kad 4 turi būti savo galutinę vietą, nes ji yra 51 00:02:42,710 --> 00:02:45,890 mažiausias elementas ir elementas pradžioje 52 00:02:45,890 --> 00:02:46,960 iš sąrašo. 53 00:02:46,960 --> 00:02:50,650 Taigi, tai reiškia, kad mes neturime kada nors reikės perkelti jį dar kartą. 54 00:02:50,650 --> 00:02:53,910 Taigi leiskite pakartoti šį procesą įtraukti kitą elementą į 55 00:02:53,910 --> 00:02:55,910 surūšiuoti dalis sąrašo. 56 00:02:55,910 --> 00:02:58,950 Mes žinome, kad mums nereikia pažvelgti į 4, nes tai 57 00:02:58,950 --> 00:03:00,000 jau surūšiuoti. 58 00:03:00,000 --> 00:03:03,540 , Kad galėtume pradėti 42, kuriuos mes prisiminti, kaip 59 00:03:03,540 --> 00:03:05,290 minimalus elementas. 60 00:03:05,290 --> 00:03:08,700 Taigi, kitą mes pažvelgti į 23, kuris yra mažesnis nei 42, todėl mes 61 00:03:08,700 --> 00:03:11,620 prisiminti 23 yra naujas minimalus. 62 00:03:11,620 --> 00:03:14,870 Toliau matome 16, kuris yra mažiau nei 23, todėl 63 00:03:14,870 --> 00:03:16,800 16 yra naujas minimalus. 64 00:03:16,800 --> 00:03:19,720 Dabar pažvelgsime 8, kuris yra mažesnis nei 16, todėl 65 00:03:19,720 --> 00:03:21,130 8 yra naujas minimalus. 66 00:03:21,130 --> 00:03:25,900 Ir pagaliau 8 yra mažesnis kaip 15, todėl mes žinome, kad 8 yra minimalus 67 00:03:25,900 --> 00:03:27,780 nerūśiuota elementas. 68 00:03:27,780 --> 00:03:30,660 Taigi, tai reiškia, kad mes turime pridėti 8 surūšiuoti 69 00:03:30,660 --> 00:03:32,450 dalis iš sąrašo. 70 00:03:32,450 --> 00:03:35,990 Dabar 4 yra tik surūšiuoti elementas, todėl mes norime įdėti 71 00:03:35,990 --> 00:03:38,410 8 kitas į 4. 72 00:03:38,410 --> 00:03:41,920 Nuo 42 yra pirmasis elementas nerūšiuotų dalis 73 00:03:41,920 --> 00:03:47,260 sąrašas, mes norime sukeisti 42 ir 8. 74 00:03:47,260 --> 00:03:49,680 Taigi dabar mūsų sąrašas atrodo taip. 75 00:03:49,680 --> 00:03:53,830 4 ir 8 atstovauti surūšiuoti sąrašo dalį, o 76 00:03:53,830 --> 00:03:56,440 likę skaičiai atspindi nerūšiuotų 77 00:03:56,440 --> 00:03:58,260 dalis iš sąrašo. 78 00:03:58,260 --> 00:04:00,630 Taigi tegul toliau su kitu iteracijos. 79 00:04:00,630 --> 00:04:03,850 Mes pradedame su 23 šį kartą, nes mums nereikia ieškoti 80 00:04:03,850 --> 00:04:05,770 4 ir 8 nebėra, nes jie jau 81 00:04:05,770 --> 00:04:07,660 jau buvo išrūšiuotos. 82 00:04:07,660 --> 00:04:10,270 16 yra mažiau nei 23, todėl mes prisiminti 83 00:04:10,270 --> 00:04:12,070 16 nauju minimaliu. 84 00:04:12,070 --> 00:04:18,149 16 yra mažiau nei 42, bet 15 yra mažiau nei 16, kad 15 turi buti 85 00:04:18,149 --> 00:04:20,480 minimalus nerūšiuotų elementas. 86 00:04:20,480 --> 00:04:24,580 Taigi, dabar mes norime sukeisti 15 ir nuo 23 iki 87 00:04:24,580 --> 00:04:26,310 suteikia mums šį sąrašą. 88 00:04:26,310 --> 00:04:30,500 Surūšiuoti sąrašo dalis susideda iš 4, 8 ir 15, ir 89 00:04:30,500 --> 00:04:33,210 šie elementai dar nerūšiuotų. 90 00:04:33,210 --> 00:04:36,900 Bet jis tiesiog taip atsitinka, kad šalia nerūšiuotų elementas, 16, 91 00:04:36,900 --> 00:04:38,480 jau rūšiuojamos. 92 00:04:38,480 --> 00:04:42,060 Tačiau ten nėra taip, kad mūsų algoritmas žinoti, kad 16 93 00:04:42,060 --> 00:04:45,230 jau teisingą vietą, todėl mes vis dar reikia 94 00:04:45,230 --> 00:04:47,870 pakartoti lygiai tą patį procesą. 95 00:04:47,870 --> 00:04:53,750 Taigi matome, kad 16 yra mažiau nei 42, o 16 yra mažiau nei 23, todėl 96 00:04:53,750 --> 00:04:56,230 16 turi būti minimalus elementas. 97 00:04:56,230 --> 00:04:59,010 Tai neįmanoma apsikeitimo šį elementą su savimi, kad galėtume 98 00:04:59,010 --> 00:05:01,780 tiesiog palikite jį šioje vietoje. 99 00:05:01,780 --> 00:05:04,660 Taigi, mes turime dar vieną perėją algoritmą. 100 00:05:04,660 --> 00:05:09,370 42 yra didesnis nei 23, kad 23 turi būti 101 00:05:09,370 --> 00:05:10,970 minimalus nerūšiuotų elementas. 102 00:05:10,970 --> 00:05:17,410 Kai mes sukeisti 23 ir 42, mes galų gale su mūsų galutinis 103 00:05:17,410 --> 00:05:18,530 surūšiuoti sąrašas 104 00:05:18,530 --> 00:05:23,390 4, 8, 15, 16, 23, 42. 105 00:05:23,390 --> 00:05:26,830 Mes žinome, 42 turi būti tinkamoje vietoje, nes tai 106 00:05:26,830 --> 00:05:30,210 vienintelis elementas, į kairę, ir kad atranka rūšiuoti. 107 00:05:30,210 --> 00:05:32,100 Tegul dabar oficialiai įforminti mūsų algoritmas su kai 108 00:05:32,100 --> 00:05:34,540 Pseudocode. 109 00:05:34,540 --> 00:05:37,760 On line vieną, mes galime pamatyti, kad turime integruoti per 110 00:05:37,760 --> 00:05:39,530 kiekvienas sąrašo elementas. 111 00:05:39,530 --> 00:05:42,150 Išskyrus paskutinį elementą, nes 1 elementas 112 00:05:42,150 --> 00:05:44,230 sąrašas jau yra rūšiuojamos. 113 00:05:44,230 --> 00:05:48,100 On line du, mes manome, kad pirmasis elementas nerūšiuotų 114 00:05:48,100 --> 00:05:51,080 sąrašo dalis, kad tai yra minimalus, kaip pasielgė su mūsų 115 00:05:51,080 --> 00:05:53,750 pavyzdys, todėl mes turime ką palyginti. 116 00:05:53,750 --> 00:05:57,260 3 linija prasideda antrą kilpą, kurioje mes pakartoti per 117 00:05:57,260 --> 00:05:59,170 kiekvienas nerūšiuotų elementas. 118 00:05:59,170 --> 00:06:02,150 Mes žinome, kad po to, kai aš iteracijų, surūšiuoti dalis 119 00:06:02,150 --> 00:06:05,330 mūsų sąraše turi būti i elementai, nes kiekviename žingsnyje 120 00:06:05,330 --> 00:06:06,890 rūšių vieną aspektą. 121 00:06:06,890 --> 00:06:11,770 Taigi pirmas nerūšiuotų elementas turi būti i padėtyje plius 1. 122 00:06:11,770 --> 00:06:15,440 On line keturi, mes palyginti dabartinę elementas iki minimumo 123 00:06:15,440 --> 00:06:17,750 elementas, kad mes matėme iki šiol. 124 00:06:17,750 --> 00:06:20,560 , Jei dabartinis elementas yra mažesnis nei minimalus 125 00:06:20,560 --> 00:06:23,870 elementas, tada mes prisimename dabartinį elementą kaip nauja 126 00:06:23,870 --> 00:06:26,250 minimalus 5 on-line. 127 00:06:26,250 --> 00:06:29,900 Galiausiai, šešių ir septynių linijų, apsikeitimo mažiausiai 128 00:06:29,900 --> 00:06:33,080 su pirmuoju nerūšiuotų elemento elementas, tokiu būdu 129 00:06:33,080 --> 00:06:36,990 pridedant jį prie išrūšiuotų sąrašo dalį. 130 00:06:36,990 --> 00:06:40,030 Kai mes turime algoritmą, svarbus klausimas paklausti 131 00:06:40,030 --> 00:06:43,370 save programuotojais, kiek laiko tai užtruks? 132 00:06:43,370 --> 00:06:46,970 Mes pirmą kartą užduoti klausimą, kiek laiko užtruks šis 133 00:06:46,970 --> 00:06:50,070 algoritmas paleisti blogiausiu atveju? 134 00:06:50,070 --> 00:06:51,640 Prisimenu, mes atstovaujame šį skaičiavimą 135 00:06:51,640 --> 00:06:55,060 laikas su Big O notacijos. 136 00:06:55,060 --> 00:06:58,650 , Siekiant nustatyti minimalų nerūšiuotų elementą, mes 137 00:06:58,650 --> 00:07:01,880 iš esmės buvo palyginti kiekvieną elementą sąraše 138 00:07:01,880 --> 00:07:04,040 kiekvienas kitas elementas sąraše. 139 00:07:04,040 --> 00:07:08,430 Intuityviai, tai, pavyzdžiui, n kvadrato operacijos O garsai. 140 00:07:08,430 --> 00:07:12,050 Žiūri mūsų pseudocode, mes taip pat turime kilpa įdėtos viduje 141 00:07:12,050 --> 00:07:14,420 kita kilpa, kuri iš tikrųjų skamba tarsi O 142 00:07:14,420 --> 00:07:16,480 iš n kvadrato operacijos. 143 00:07:16,480 --> 00:07:19,250 Tačiau atminkite, kad mes ne reikia ieškoti per 144 00:07:19,250 --> 00:07:23,460 visą sąrašą, nustatant minimalų nerūšiuotų elementą? 145 00:07:23,460 --> 00:07:26,600 Kai mes žinojome, kad 4 buvo rūšiuojami, pavyzdžiui, mes ne 146 00:07:26,600 --> 00:07:28,170 reikia dar kartą pažvelgti į jį. 147 00:07:28,170 --> 00:07:31,020 Taigi ar tai mažesnė veikimo laiką? 148 00:07:31,020 --> 00:07:34,510 Dėl mūsų sąraše ilgis 6, mums reikia padaryti 5 149 00:07:34,510 --> 00:07:37,990 palyginimų pirmojo elemento, keturi palyginimų 150 00:07:37,990 --> 00:07:40,750 Antrasis elementas, ir taip toliau. 151 00:07:40,750 --> 00:07:44,690 Tai reiškia, kad priemonių yra iš viso suma 152 00:07:44,690 --> 00:07:49,160 sveikieji skaičiai nuo 1 iki sąrašo ilgio minus 1. 153 00:07:49,160 --> 00:07:51,005 Mes galime atstovauti tai su sumavimo. 154 00:07:57,980 --> 00:07:59,910 Mes negalime eiti į summations čia. 155 00:07:59,910 --> 00:08:04,900 Tačiau paaiškėja, kad tai sumavimas yra lygus n kartų 156 00:08:04,900 --> 00:08:07,540 n atėmus 1 per 2. 157 00:08:07,540 --> 00:08:14,220 Arba analogiškai n kvadrato per 2 minus n per 2. 158 00:08:14,220 --> 00:08:18,860 Kai kalbame apie asimptotinio runtime, tai n kvadrato terminas 159 00:08:18,860 --> 00:08:22,070 vyksta dominuoti, n terminą. 160 00:08:22,070 --> 00:08:27,850 Taigi pasirinkimas rūšiuoti yra O n kvadrato. 161 00:08:27,850 --> 00:08:31,460 Prisiminkite, kad mūsų pavyzdyje, atranka tarsi vis dar reikia 162 00:08:31,460 --> 00:08:33,850 patikrinti, ar numeris, kuri jau buvo surūšiuoti 163 00:08:33,850 --> 00:08:35,450 reikia būti perkeltas. 164 00:08:35,450 --> 00:08:38,929 Taigi, tai reiškia, kad jei mes per jau vyko atrankos rūšiuoti 165 00:08:38,929 --> 00:08:43,070 surūšiuoti sąrašą, jam reikėtų tą patį skaičių priemonių, kurias jis 166 00:08:43,070 --> 00:08:46,340 būtų važiuojant visiškai nerūšiuotų sąrašo. 167 00:08:46,340 --> 00:08:51,470 Taigi pasirinkimas rūšiuoti yra geriausiu atveju atlikimą n kvadrato, 168 00:08:51,470 --> 00:08:56,820 kurią mes atstovaujame su omega n kvadrato. 169 00:08:56,820 --> 00:08:58,600 Ir štai Pasirinkimo rūšiuoti. 170 00:08:58,600 --> 00:09:00,630 Tik vienas iš daugelio algoritmų, mes galime 171 00:09:00,630 --> 00:09:02,390 rūšiuoti sąrašą. 172 00:09:02,390 --> 00:09:05,910 My name is Tommy, ir tai yra CS50.