1 00:00:06,762 --> 00:00:09,980 [Powered by Google Translate] TOMMY: Chcę spojrzeć na rodzaj karnetu, algorytm 2 00:00:09,980 --> 00:00:12,800 podejmowania listę numerów i sortowania ich. 3 00:00:12,800 --> 00:00:15,750 Algorytm, pamiętasz, to po prostu krok po kroku 4 00:00:15,750 --> 00:00:18,370 Procedura realizacji zadania. 5 00:00:18,370 --> 00:00:21,470 Podstawową ideą rodzaju selekcji jest podzielenie 6 00:00:21,470 --> 00:00:23,390 Nasza lista jest na dwie części - 7 00:00:23,390 --> 00:00:26,810 posortowane część i unsorted porcję. 8 00:00:26,810 --> 00:00:30,200 Na każdym etapie algorytmu numer przeniesiony z 9 00:00:30,200 --> 00:00:33,800 unsorted część do sortowanie części, aż w końcu 10 00:00:33,800 --> 00:00:35,880 Cała lista jest posortowana. 11 00:00:35,880 --> 00:00:38,510 Więc oto lista sześciu liczb - 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 Teraz cała lista jest uważany nieposortowane. 14 00:00:47,680 --> 00:00:51,770 Nawet jeśli ilość jak 16 maja być już w odpowiedniej 15 00:00:51,770 --> 00:00:56,040 lokalizacja, nasz algorytm nie ma możliwości dowiedzenia się, że do 16 00:00:56,040 --> 00:00:57,980 Cała lista jest posortowana. 17 00:00:57,980 --> 00:01:01,355 Więc będziemy rozpatrywać każdy numer do sortowania aż sortować 18 00:01:01,355 --> 00:01:03,800 to sami. 19 00:01:03,800 --> 00:01:06,890 My wiemy, że lista ma być w porządku rosnącym. 20 00:01:06,890 --> 00:01:10,200 Więc chcemy budować posortowaną część naszej listy 21 00:01:10,200 --> 00:01:13,280 od lewej do prawej, od najmniejszych do największych. 22 00:01:13,280 --> 00:01:17,970 Aby to zrobić, musimy znaleźć minimalną niesortowanych elementu 23 00:01:17,970 --> 00:01:21,350 i umieścić na końcu części sortowanie. 24 00:01:21,350 --> 00:01:25,370 Ponieważ ta lista nie jest posortowana, jedynym sposobem na to jest do 25 00:01:25,370 --> 00:01:29,330 patrzeć na każdy element w nieposortowanych części, pamiętając 26 00:01:29,330 --> 00:01:32,010 który to element jest najniższą i porównanie 27 00:01:32,010 --> 00:01:33,770 każdy element do tego. 28 00:01:33,770 --> 00:01:36,150 Więc najpierw spojrzeć na 23. 29 00:01:36,150 --> 00:01:38,650 Jest to pierwszy element widzieliśmy, więc będziemy pamiętać 30 00:01:38,650 --> 00:01:40,050 jest jak najmniej. 31 00:01:40,050 --> 00:01:42,320 Dalej przyjrzymy 42. 32 00:01:42,320 --> 00:01:46,720 42 jest większy niż 23, to 23 jest nadal minimalna. 33 00:01:46,720 --> 00:01:51,210 Dalej jest 4 co jest mniej niż 23, więc musimy pamiętać, 4 34 00:01:51,210 --> 00:01:52,880 jako nowego minimum. 35 00:01:52,880 --> 00:01:56,380 Dalej jest 16, który jest większy niż 4, SO 4 36 00:01:56,380 --> 00:01:57,980 pozostaje minimalna. 37 00:01:57,980 --> 00:02:03,670 8 jest większa niż 4, i 15 jest większy niż 4, tak, 4 są 38 00:02:03,670 --> 00:02:05,980 Najmniejszy unsorted element. 39 00:02:05,980 --> 00:02:09,350 Dlatego, mimo że jako ludzie możemy od razu zauważyć, że 4 jest 40 00:02:09,350 --> 00:02:12,300 Minimalny element, nasz algorytm musi spojrzeć na 41 00:02:12,300 --> 00:02:15,710 każdy unsorted element, nawet po znalazłeś 4 - 42 00:02:15,710 --> 00:02:16,860 Minimalny element. 43 00:02:16,860 --> 00:02:19,900 Więc teraz, że odkryliśmy minimalny element, 4, my chcemy 44 00:02:19,900 --> 00:02:23,410 , aby przenieść go do sortowanie części listy. 45 00:02:23,410 --> 00:02:27,320 Ponieważ jest to pierwszy krok, to znaczy, że chcesz umieścić 4 na 46 00:02:27,320 --> 00:02:29,680 początek listy. 47 00:02:29,680 --> 00:02:33,040 23 jest teraz na początku na liście, to 48 00:02:33,040 --> 00:02:36,080 Wymieńmy się 4 i 23. 49 00:02:36,080 --> 00:02:38,870 Więc teraz nasza lista wygląda tak. 50 00:02:38,870 --> 00:02:42,710 Wiadomo, że 4 są w miejscu docelowym, ponieważ 51 00:02:42,710 --> 00:02:45,890 jak najmniejszy element i element w początku 52 00:02:45,890 --> 00:02:46,960 wykazu. 53 00:02:46,960 --> 00:02:50,650 Więc oznacza to, że nie zawsze trzeba przenieść go ponownie. 54 00:02:50,650 --> 00:02:53,910 Więc powtórzyć ten proces, aby dodać kolejny element do 55 00:02:53,910 --> 00:02:55,910 posortowane część listy. 56 00:02:55,910 --> 00:02:58,950 Wiemy, że nie musimy patrzeć na 4, ponieważ jest to 57 00:02:58,950 --> 00:03:00,000 już posortowane. 58 00:03:00,000 --> 00:03:03,540 Tak więc możemy rozpocząć na 42, które będziemy pamiętać jako 59 00:03:03,540 --> 00:03:05,290 Minimalny element. 60 00:03:05,290 --> 00:03:08,700 Więc następnym będziemy patrzeć na 23, która jest mniejsza niż 42, więc mamy 61 00:03:08,700 --> 00:03:11,620 Pamiętam 23 jest nowym minimum. 62 00:03:11,620 --> 00:03:14,870 Dalej widzimy 16, która jest mniejsza niż 23, więc 63 00:03:14,870 --> 00:03:16,800 16 to nowe minimum. 64 00:03:16,800 --> 00:03:19,720 Teraz patrzymy na 8, który jest mniej niż 16, więc 65 00:03:19,720 --> 00:03:21,130 8 jest nowe minimum. 66 00:03:21,130 --> 00:03:25,900 I w końcu 8 jest mniejsza niż 15, to wiadomo, że jest co najmniej 8 67 00:03:25,900 --> 00:03:27,780 unsorted element. 68 00:03:27,780 --> 00:03:30,660 To znaczy, że powinniśmy dodać 8 do posortowane 69 00:03:30,660 --> 00:03:32,450 część listy. 70 00:03:32,450 --> 00:03:35,990 Teraz 4 jest jedynym posortowane element, więc chcemy, aby umieścić 71 00:03:35,990 --> 00:03:38,410 8 obok 4. 72 00:03:38,410 --> 00:03:41,920 Od 42 jest pierwszym elementem w nieposortowanych części 73 00:03:41,920 --> 00:03:47,260 lista, będziemy chcieli, aby zamienić 42 i 8. 74 00:03:47,260 --> 00:03:49,680 Więc teraz nasza lista wygląda tak. 75 00:03:49,680 --> 00:03:53,830 4 i 8 przedstawiają część sortowane na liście, a 76 00:03:53,830 --> 00:03:56,440 Pozostałe numery reprezentują unsorted 77 00:03:56,440 --> 00:03:58,260 część listy. 78 00:03:58,260 --> 00:04:00,630 Więc nadal z innym iteracji. 79 00:04:00,630 --> 00:04:03,850 Zaczynamy 23 ten czas, ponieważ nie musimy patrzeć na 80 00:04:03,850 --> 00:04:05,770 4 i 8 więcej, bo już 81 00:04:05,770 --> 00:04:07,660 już posortowane. 82 00:04:07,660 --> 00:04:10,270 16 jest mniejsza niż 23, więc będziemy pamiętać 83 00:04:10,270 --> 00:04:12,070 16 jako nowe minimum. 84 00:04:12,070 --> 00:04:18,149 16 jest mniejsza niż 42, 15, ale jest mniejsza niż 16, 15 musi być więc 85 00:04:18,149 --> 00:04:20,480 minimum unsorted element. 86 00:04:20,480 --> 00:04:24,580 Więc teraz chcemy zamienić 15 i 23 do 87 00:04:24,580 --> 00:04:26,310 dać nam tę listę. 88 00:04:26,310 --> 00:04:30,500 Posortowane część listy składa się z 4, 8 i 15, a 89 00:04:30,500 --> 00:04:33,210 elementy te są jeszcze nieposortowane. 90 00:04:33,210 --> 00:04:36,900 Ale tak się składa, że ​​następny unsorted element, 16, 91 00:04:36,900 --> 00:04:38,480 jest już posortowana. 92 00:04:38,480 --> 00:04:42,060 Jednakże, nie ma mowy, dla naszego algorytmu wiedzieć, że 16 93 00:04:42,060 --> 00:04:45,230 jest już w odpowiednim miejscu, więc musimy jeszcze 94 00:04:45,230 --> 00:04:47,870 powtórzyć dokładnie ten sam proces. 95 00:04:47,870 --> 00:04:53,750 Widzimy zatem, że 16 jest mniejsza niż 42, i 16, jest mniejsza niż 23, to 96 00:04:53,750 --> 00:04:56,230 16 musi być minimalna elementem. 97 00:04:56,230 --> 00:04:59,010 To niemożliwe, aby zamienić ten element, z samym sobą, więc możemy 98 00:04:59,010 --> 00:05:01,780 po prostu zostawić go w tym miejscu. 99 00:05:01,780 --> 00:05:04,660 Musimy więc jeszcze jeden karnet naszego algorytmu. 100 00:05:04,660 --> 00:05:09,370 42 jest większy niż 23, 23 musi być więc 101 00:05:09,370 --> 00:05:10,970 minimum unsorted element. 102 00:05:10,970 --> 00:05:17,410 Kiedy zamienić 23 i 42, ale kończy się z naszym ostatnim 103 00:05:17,410 --> 00:05:18,530 posortowane list - 104 00:05:18,530 --> 00:05:23,390 4, 8, 15, 16, 23, 42. 105 00:05:23,390 --> 00:05:26,830 Wiemy, 42 musi być w odpowiednim miejscu, ponieważ jest to 106 00:05:26,830 --> 00:05:30,210 Jedynym elementem, w lewo, a to rodzaj selekcji. 107 00:05:30,210 --> 00:05:32,100 Zróbmy teraz sformalizować nasz algorytm z niektórymi 108 00:05:32,100 --> 00:05:34,540 pseudokod. 109 00:05:34,540 --> 00:05:37,760 Na pierwszej linii, widzimy, że musimy zintegrować ponad 110 00:05:37,760 --> 00:05:39,530 każdy element listy. 111 00:05:39,530 --> 00:05:42,150 Wyjątkiem ostatniego elementu, od 1 element 112 00:05:42,150 --> 00:05:44,230 lista jest już posortowana. 113 00:05:44,230 --> 00:05:48,100 Na drugiej linii, uważamy pierwszy element unsorted 114 00:05:48,100 --> 00:05:51,080 część listy jest minimum, jak to zrobiliśmy z naszym 115 00:05:51,080 --> 00:05:53,750 przykładem, więc mamy coś do porównania do. 116 00:05:53,750 --> 00:05:57,260 Trzecia linijka rozpoczyna drugą pętlę, w której iteracji 117 00:05:57,260 --> 00:05:59,170 każdy unsorted element. 118 00:05:59,170 --> 00:06:02,150 Wiemy, że po I iteracji, posortowane część 119 00:06:02,150 --> 00:06:05,330 naszej liście musi ja w nim elementy od każdego kroku 120 00:06:05,330 --> 00:06:06,890 sortuje jeden element. 121 00:06:06,890 --> 00:06:11,770 Tak więc pierwszym elementem unsorted musi być w pozycji I plus 1. 122 00:06:11,770 --> 00:06:15,440 W linii cztery, porównana z elementem do minimum 123 00:06:15,440 --> 00:06:17,750 Element, który widzieliśmy do tej pory. 124 00:06:17,750 --> 00:06:20,560 Jeśli obecny jest elementem mniejszych od 125 00:06:20,560 --> 00:06:23,870 element, a następnie pamiętać bieżący element jak nowy 126 00:06:23,870 --> 00:06:26,250 minimum w wierszu piątym. 127 00:06:26,250 --> 00:06:29,900 Wreszcie, na liniach sześć i siedem, zamienimy minimum 128 00:06:29,900 --> 00:06:33,080 elementu z pierwszym elementem niesegregowanych, co 129 00:06:33,080 --> 00:06:36,990 dodanie go do części sortowanie listy. 130 00:06:36,990 --> 00:06:40,030 Gdy już mamy algorytm, istotne pytanie 131 00:06:40,030 --> 00:06:43,370 siebie jako programistów jest jak długo to potrwa? 132 00:06:43,370 --> 00:06:46,970 Zaczniemy zadawać sobie pytanie, jak długo trzeba czekać na to 133 00:06:46,970 --> 00:06:50,070 Algorytm do uruchomienia w najgorszym przypadku? 134 00:06:50,070 --> 00:06:51,640 Przypominam, że reprezentujemy ten bieg 135 00:06:51,640 --> 00:06:55,060 razem z wielkim notacji O. 136 00:06:55,060 --> 00:06:58,650 W celu określenia minimalnego niesortowanych elementu, że 137 00:06:58,650 --> 00:07:01,880 zasadniczo miał porównać każdy element w liście do 138 00:07:01,880 --> 00:07:04,040 każdy inny element na liście. 139 00:07:04,040 --> 00:07:08,430 Intuicyjnie, to brzmi jak O n kwadratu operacji. 140 00:07:08,430 --> 00:07:12,050 Patrząc na Pseudokod, mamy także pętlę zagnieżdżone 141 00:07:12,050 --> 00:07:14,420 inna pętla, która rzeczywiście brzmi jak O 142 00:07:14,420 --> 00:07:16,480 n kwadratu operacji. 143 00:07:16,480 --> 00:07:19,250 Należy jednak pamiętać, że nie należy patrzeć na 144 00:07:19,250 --> 00:07:23,460 Cała lista przy określaniu minimalnego niesortowanych element? 145 00:07:23,460 --> 00:07:26,600 Po wiedział, że 4 sortowano, na przykład, nie 146 00:07:26,600 --> 00:07:28,170 trzeba spojrzeć na nią ponownie. 147 00:07:28,170 --> 00:07:31,020 Więc robi to obniżyć czas pracy? 148 00:07:31,020 --> 00:07:34,510 Na naszej liście długości 6, musieliśmy zrobić pięć 149 00:07:34,510 --> 00:07:37,990 porównania dla pierwszego elementu, cztery dla porównania 150 00:07:37,990 --> 00:07:40,750 drugi element, i tak dalej. 151 00:07:40,750 --> 00:07:44,690 To oznacza, że ​​całkowita liczba stopni jest suma 152 00:07:44,690 --> 00:07:49,160 liczby całkowite od 1 do długości listy minus 1.. 153 00:07:49,160 --> 00:07:51,005 Możemy reprezentować to z sumowaniu. 154 00:07:57,980 --> 00:07:59,910 Nie pójdziemy do podsumowań tutaj. 155 00:07:59,910 --> 00:08:04,900 Ale okazuje się, że to podsumowanie jest równy n razy 156 00:08:04,900 --> 00:08:07,540 n minus 1 na 2. 157 00:08:07,540 --> 00:08:14,220 Lub równoważnie, n do kwadratu przez 2 minus n nad 2. 158 00:08:14,220 --> 00:08:18,860 Kiedy mówimy o asymptotycznej wykonywania, to n squared termin 159 00:08:18,860 --> 00:08:22,070 ma zamiar zdominować tę n kadencję. 160 00:08:22,070 --> 00:08:27,850 Wybór jest więc rodzajem O n kwadratu. 161 00:08:27,850 --> 00:08:31,460 Przypomnijmy, że w naszym przykładzie, sort wybór nadal potrzebne do 162 00:08:31,460 --> 00:08:33,850 sprawdzić, czy numer, który został już posortowane 163 00:08:33,850 --> 00:08:35,450 musiał zostać przeniesiony. 164 00:08:35,450 --> 00:08:38,929 Więc to oznacza, że ​​jeśli prowadził rodzaj wyboru ponad już 165 00:08:38,929 --> 00:08:43,070 sortowana lista, wymagałoby to taką samą liczbę kroków, jak to 166 00:08:43,070 --> 00:08:46,340 by podczas pracy nad liście całkowicie nieposortowanych. 167 00:08:46,340 --> 00:08:51,470 Więc wybór sort ma najlepszą wydajność przypadku n kwadratu, 168 00:08:51,470 --> 00:08:56,820 które stanowią o omega n kwadratu. 169 00:08:56,820 --> 00:08:58,600 I to za rodzaj selekcji. 170 00:08:58,600 --> 00:09:00,630 To tylko jeden z wielu algorytmów możemy 171 00:09:00,630 --> 00:09:02,390 użyć, aby posortować listę. 172 00:09:02,390 --> 00:09:05,910 Nazywam się Tommy, i to jest CS50.