1 00:00:06,762 --> 00:00:09,980 [Powered by Google Translate] TOMMY: Să aruncăm o privire la fel de selecție, un algoritm 2 00:00:09,980 --> 00:00:12,800 pentru a lua o listă de numere și sortarea lor. 3 00:00:12,800 --> 00:00:15,750 Un algoritm, amintiți-vă, este pur și simplu un pas-cu-pas 4 00:00:15,750 --> 00:00:18,370 Procedura pentru realizarea unei sarcini. 5 00:00:18,370 --> 00:00:21,470 Ideea de bază din spatele fel de selecție este de a diviza 6 00:00:21,470 --> 00:00:23,390 Lista noastră în două părți - 7 00:00:23,390 --> 00:00:26,810 o parte sortati si o parte nesortate. 8 00:00:26,810 --> 00:00:30,200 La fiecare pas al algoritmului, un numar este mutat de la 9 00:00:30,200 --> 00:00:33,800 porțiunea nesortate la porțiunea sortate până în cele din urmă 10 00:00:33,800 --> 00:00:35,880 întreaga listă este sortată. 11 00:00:35,880 --> 00:00:38,510 Deci, aici este o listă de șase numere - 12 00:00:38,510 --> 00:00:44,010 23, 42, 4, 16, 8, și 15. 13 00:00:44,010 --> 00:00:47,680 Chiar acum întreaga listă este considerat nesortate. 14 00:00:47,680 --> 00:00:51,770 Chiar dacă un număr ca 16 pot fi deja în corect sa 15 00:00:51,770 --> 00:00:56,040 Locul de amplasare, algoritmul nostru nu are nici o modalitate de a ști că, până la 16 00:00:56,040 --> 00:00:57,980 întreaga listă este sortată. 17 00:00:57,980 --> 00:01:01,355 Deci, vom lua în considerare fiecare număr să fie sortate până când vom rezolva 18 00:01:01,355 --> 00:01:03,800 o noi înșine. 19 00:01:03,800 --> 00:01:06,890 Știm că vrem lista să fie în ordine crescătoare. 20 00:01:06,890 --> 00:01:10,200 Deci, vom dori să construiască partea de sortat lista noastră de 21 00:01:10,200 --> 00:01:13,280 de la stânga la dreapta, mai mic la cel mai mare. 22 00:01:13,280 --> 00:01:17,970 Pentru a face acest lucru, vom avea nevoie pentru a găsi elementul minim nesortate 23 00:01:17,970 --> 00:01:21,350 și pune-l la sfârșitul porțiunii sortate. 24 00:01:21,350 --> 00:01:25,370 Deoarece această listă nu este sortată, singura modalitate de a face asta este de a 25 00:01:25,370 --> 00:01:29,330 uita-te la fiecare element în parte nesortate, amintindu- 26 00:01:29,330 --> 00:01:32,010 care element este mai mic și compararea 27 00:01:32,010 --> 00:01:33,770 fiecare element de asta. 28 00:01:33,770 --> 00:01:36,150 Deci, ne vom uita mai intai la 23. 29 00:01:36,150 --> 00:01:38,650 Acesta este primul element care le-am văzut, așa că vom aminti 30 00:01:38,650 --> 00:01:40,050 ca minim. 31 00:01:40,050 --> 00:01:42,320 Apoi, vom uita la 42. 32 00:01:42,320 --> 00:01:46,720 42 este mai mare decât 23, deci 23 este încă minimă. 33 00:01:46,720 --> 00:01:51,210 Următorul este 4, care este mai mică de 23, deci vom aminti 4 34 00:01:51,210 --> 00:01:52,880 ca minim. 35 00:01:52,880 --> 00:01:56,380 Următorul este 16, care este mai mare de 4, deci 4 36 00:01:56,380 --> 00:01:57,980 este încă minimă. 37 00:01:57,980 --> 00:02:03,670 8 este mai mare de 4, iar 15 este mai mare de 4, deci 4 trebuie să fie 38 00:02:03,670 --> 00:02:05,980 cel mai mic element de nesortate. 39 00:02:05,980 --> 00:02:09,350 Deci, chiar dacă, ca oameni, putem vedea imediat că 4 este 40 00:02:09,350 --> 00:02:12,300 elementul minim, algoritmul nostru are nevoie să se uite la 41 00:02:12,300 --> 00:02:15,710 fiecare element nesortate, chiar și după ce am gasit 4 - 42 00:02:15,710 --> 00:02:16,860 minim element. 43 00:02:16,860 --> 00:02:19,900 Deci, acum că ne-am găsit elementul minim, 4, vom dori 44 00:02:19,900 --> 00:02:23,410 pentru ao muta în partea de sortat lista. 45 00:02:23,410 --> 00:02:27,320 Deoarece acesta este primul pas, aceasta înseamnă că doriți să puneți 4 la 46 00:02:27,320 --> 00:02:29,680 începutul listei. 47 00:02:29,680 --> 00:02:33,040 Chiar acum 23 este de la inceputul listei, astfel încât 48 00:02:33,040 --> 00:02:36,080 hai sa schimb 4 și 23. 49 00:02:36,080 --> 00:02:38,870 Deci, acum, lista noastră de arată așa. 50 00:02:38,870 --> 00:02:42,710 Știm că 4 trebuie să fie în poziția sa finală, pentru că este 51 00:02:42,710 --> 00:02:45,890 atât mai mic element și elementul de la început 52 00:02:45,890 --> 00:02:46,960 a listei. 53 00:02:46,960 --> 00:02:50,650 Deci asta înseamnă că nu avem nevoie niciodată să-l mute din nou. 54 00:02:50,650 --> 00:02:53,910 Așa că hai să repetați acest proces pentru a adăuga un alt element la 55 00:02:53,910 --> 00:02:55,910 parte din lista de sortat. 56 00:02:55,910 --> 00:02:58,950 Noi știm că nu avem nevoie să se uite la 4, pentru că este 57 00:02:58,950 --> 00:03:00,000 deja sortate. 58 00:03:00,000 --> 00:03:03,540 Deci, putem incepe de la 42, pe care ne vom aminti ca 59 00:03:03,540 --> 00:03:05,290 minim element. 60 00:03:05,290 --> 00:03:08,700 Deci, data viitoare ne vom uita la 23, care este mai mică de 42, așa că am 61 00:03:08,700 --> 00:03:11,620 amintesc 23 este minim. 62 00:03:11,620 --> 00:03:14,870 În continuare vom vedea 16, care este mai puțin de 23, așa 63 00:03:14,870 --> 00:03:16,800 16 este minim. 64 00:03:16,800 --> 00:03:19,720 Acum ne uităm la 8, care este mai mică de 16, așa 65 00:03:19,720 --> 00:03:21,130 8 este minim. 66 00:03:21,130 --> 00:03:25,900 Și, în cele din urmă 8 este mai mic de 15, așa că știm că 8 este un minim 67 00:03:25,900 --> 00:03:27,780 nesortate element. 68 00:03:27,780 --> 00:03:30,660 Deci asta înseamnă că ar trebui să adauge la 8 la sortat 69 00:03:30,660 --> 00:03:32,450 porțiune din listă. 70 00:03:32,450 --> 00:03:35,990 Acum 4 este singurul element sortate, astfel încât dorim să plaseze 71 00:03:35,990 --> 00:03:38,410 următor 8 la 4. 72 00:03:38,410 --> 00:03:41,920 Deoarece 42 este primul element din partea nesortata a 73 00:03:41,920 --> 00:03:47,260 listă, vom dori să facă schimb de 42 și 8. 74 00:03:47,260 --> 00:03:49,680 Deci, acum, lista noastră de arată așa. 75 00:03:49,680 --> 00:03:53,830 4 și 8 reprezintă porțiunea sortate din listă și 76 00:03:53,830 --> 00:03:56,440 Numerele rămase reprezintă nesortate 77 00:03:56,440 --> 00:03:58,260 porțiune din listă. 78 00:03:58,260 --> 00:04:00,630 Așa că să continuăm cu o altă iterație. 79 00:04:00,630 --> 00:04:03,850 Vom începe cu 23 de data asta, din moment ce nu trebuie să se uite la 80 00:04:03,850 --> 00:04:05,770 4 și 8 mai, deoarece le-am 81 00:04:05,770 --> 00:04:07,660 fost deja sortate. 82 00:04:07,660 --> 00:04:10,270 16 este mai puțin de 23, deci vom aminti 83 00:04:10,270 --> 00:04:12,070 16 ca minim. 84 00:04:12,070 --> 00:04:18,149 16 este mai mică de 42, dar 15 este mai mică de 16, deci 15 trebuie să fie 85 00:04:18,149 --> 00:04:20,480 elementul minim nesortate. 86 00:04:20,480 --> 00:04:24,580 Deci, acum vrem să schimb 15 și 23 la 87 00:04:24,580 --> 00:04:26,310 să ne dea această listă. 88 00:04:26,310 --> 00:04:30,500 Partea sortate a listei este format din 4, 8 și 15, precum și 89 00:04:30,500 --> 00:04:33,210 aceste elemente sunt încă nesortate. 90 00:04:33,210 --> 00:04:36,900 Dar doar așa se întâmplă că elementul următor nesortate, 16, 91 00:04:36,900 --> 00:04:38,480 este deja sortat. 92 00:04:38,480 --> 00:04:42,060 Cu toate acestea, nu există nici o cale pentru algoritmul nostru să știe că 16 93 00:04:42,060 --> 00:04:45,230 este deja în locația corectă, așa că încă mai trebuie să 94 00:04:45,230 --> 00:04:47,870 repetați exact același proces. 95 00:04:47,870 --> 00:04:53,750 Deci, vedem că 16 este mai mică de 42, iar 16 este mai puțin de 23, așa 96 00:04:53,750 --> 00:04:56,230 16 trebuie să fie elementul minim. 97 00:04:56,230 --> 00:04:59,010 Este imposibil de a schimba acest element cu el însuși, astfel încât să putem 98 00:04:59,010 --> 00:05:01,780 pur și simplu lăsați-l în această locație. 99 00:05:01,780 --> 00:05:04,660 Deci, avem nevoie de pașaport una mai mult a algoritmului nostru. 100 00:05:04,660 --> 00:05:09,370 42 este mai mare de 23, deci 23 trebuie să fie 101 00:05:09,370 --> 00:05:10,970 minim nesortate element. 102 00:05:10,970 --> 00:05:17,410 După ce vom schimba 23 și 42, vom ajunge cu finala nostru 103 00:05:17,410 --> 00:05:18,530 sortate lista - 104 00:05:18,530 --> 00:05:23,390 4, 8, 15, 16, 23, 42. 105 00:05:23,390 --> 00:05:26,830 Stim 42 trebuie să fie în locul corect, deoarece este 106 00:05:26,830 --> 00:05:30,210 singurul element rămas, și asta e un fel de selecție. 107 00:05:30,210 --> 00:05:32,100 Să formalizeze acum algoritmul nostru, cu unele 108 00:05:32,100 --> 00:05:34,540 pseudocod. 109 00:05:34,540 --> 00:05:37,760 Pe linia unu, putem vedea că avem nevoie pentru a integra peste 110 00:05:37,760 --> 00:05:39,530 fiecare element al listei. 111 00:05:39,530 --> 00:05:42,150 Cu excepția ultimul element, deoarece elementul 1 112 00:05:42,150 --> 00:05:44,230 Lista este deja sortat. 113 00:05:44,230 --> 00:05:48,100 Pe linia doi, considerăm primul element al nesortate 114 00:05:48,100 --> 00:05:51,080 parte din lista pentru a fi minim, așa cum am procedat cu 115 00:05:51,080 --> 00:05:53,750 de exemplu, deci avem ceva pentru a compara cu. 116 00:05:53,750 --> 00:05:57,260 Linia trei începe o buclă al doilea în care am itera peste 117 00:05:57,260 --> 00:05:59,170 fiecare element de nesortate. 118 00:05:59,170 --> 00:06:02,150 Știm că după ce am iterații, sortate porțiunea 119 00:06:02,150 --> 00:06:05,330 din lista noastră trebuie să aibă elemente i în ea, deoarece fiecare pas 120 00:06:05,330 --> 00:06:06,890 sortează un element. 121 00:06:06,890 --> 00:06:11,770 Deci, primul element nesortate trebuie să fie în poziția I, plus 1. 122 00:06:11,770 --> 00:06:15,440 Pe linia patru, vom compara elementul curent la minim 123 00:06:15,440 --> 00:06:17,750 Elementul pe care le-am văzut până acum. 124 00:06:17,750 --> 00:06:20,560 Dacă elementul curent este mai mic decât minimul 125 00:06:20,560 --> 00:06:23,870 element, apoi ne amintim elementul curent ca noua 126 00:06:23,870 --> 00:06:26,250 minim pe linia cinci. 127 00:06:26,250 --> 00:06:29,900 În cele din urmă, pe liniile șase și șapte, am schimba minim 128 00:06:29,900 --> 00:06:33,080 element cu element nesortate în primul rând, astfel 129 00:06:33,080 --> 00:06:36,990 adăugându-l la partea de sortat lista. 130 00:06:36,990 --> 00:06:40,030 Odată ce avem un algoritm, o întrebare importantă de a cere 131 00:06:40,030 --> 00:06:43,370 noi înșine ca programatori este cât de mult a dura asta? 132 00:06:43,370 --> 00:06:46,970 Vom întreba mai întâi întrebarea cât timp durează pentru acest 133 00:06:46,970 --> 00:06:50,070 algoritm pentru a rula în cel mai rău caz? 134 00:06:50,070 --> 00:06:51,640 Amintesc să ne reprezentăm această funcționare 135 00:06:51,640 --> 00:06:55,060 timp cu notația O mare. 136 00:06:55,060 --> 00:06:58,650 În scopul de a determina elementul minim nesortate, am 137 00:06:58,650 --> 00:07:01,880 în esență, a trebuit să compare fiecare element în listă pentru a 138 00:07:01,880 --> 00:07:04,040 orice alt element din listă. 139 00:07:04,040 --> 00:07:08,430 Intuitiv, acest lucru sună ca o operațiune de O, N pătrat. 140 00:07:08,430 --> 00:07:12,050 Privind la pseudocod nostru, avem, de asemenea, o buclă imbricată în interiorul 141 00:07:12,050 --> 00:07:14,420 o altă buclă, care într-adevăr sună ca un O 142 00:07:14,420 --> 00:07:16,480 de funcționare pătrat nr. 143 00:07:16,480 --> 00:07:19,250 Cu toate acestea, amintiți-vă că nu am nevoie să se uite peste 144 00:07:19,250 --> 00:07:23,460 listă întreagă atunci când se determină elementul minim nesortate? 145 00:07:23,460 --> 00:07:26,600 Odată ce am știut că 4 a fost sortate, de exemplu, nu am făcut-o 146 00:07:26,600 --> 00:07:28,170 trebuie să se uite la el din nou. 147 00:07:28,170 --> 00:07:31,020 Deci, face acest lucru mai mic timpul de execuție? 148 00:07:31,020 --> 00:07:34,510 Pentru lista noastră de lungime 6, avem nevoie pentru a face cinci 149 00:07:34,510 --> 00:07:37,990 comparații pentru primul element, patru comparații pentru 150 00:07:37,990 --> 00:07:40,750 al doilea element, și așa mai departe. 151 00:07:40,750 --> 00:07:44,690 Asta înseamnă că numărul total de pași este suma de 152 00:07:44,690 --> 00:07:49,160 de numere întregi de la 1 la lungimea listei minus 1. 153 00:07:49,160 --> 00:07:51,005 Ne putem reprezenta acest lucru cu o însumare. 154 00:07:57,980 --> 00:07:59,910 Nu vom intra în somații aici. 155 00:07:59,910 --> 00:08:04,900 Dar se pare că acest însumării este egală cu de n ori 156 00:08:04,900 --> 00:08:07,540 n minus 1 peste 2. 157 00:08:07,540 --> 00:08:14,220 Sau echivalent, n pătrat de peste 2 minus n. peste 2. 158 00:08:14,220 --> 00:08:18,860 Atunci când vorbim despre timpul rulării asimptotică, acest termen n pătrat 159 00:08:18,860 --> 00:08:22,070 este de gând să domine acest termen nr. 160 00:08:22,070 --> 00:08:27,850 Deci, un fel de selecție este O de n pătrat. 161 00:08:27,850 --> 00:08:31,460 Reamintim că, în exemplul nostru, un fel de selecție încă necesare pentru a 162 00:08:31,460 --> 00:08:33,850 verifica dacă un număr care a fost deja sortate 163 00:08:33,850 --> 00:08:35,450 necesare pentru a fi mutate. 164 00:08:35,450 --> 00:08:38,929 Asta înseamnă că, dacă am alergat un fel de selecție peste o deja 165 00:08:38,929 --> 00:08:43,070 sortate listă, ar fi nevoie de același număr de pași în care 166 00:08:43,070 --> 00:08:46,340 ar fi atunci când rulează pe o listă complet nesortate. 167 00:08:46,340 --> 00:08:51,470 Deci, un fel de selecție are o performanță mai bun caz de pătrat N, 168 00:08:51,470 --> 00:08:56,820 pe care le reprezintă cu omega n pătrat. 169 00:08:56,820 --> 00:08:58,600 Și asta e tot un fel de selecție. 170 00:08:58,600 --> 00:09:00,630 Doar unul din algoritmii de mai multe, putem 171 00:09:00,630 --> 00:09:02,390 utilizați pentru a sorta o listă. 172 00:09:02,390 --> 00:09:05,910 Numele meu este Tommy, iar acest lucru este CS50.