1 00:00:06,762 --> 00:00:09,980 [Powered by Google Translate] TOMMY: Давайце зірнем на выбар роду, алгарытм 2 00:00:09,980 --> 00:00:12,800 для прыняцця спісу лікаў і сартаванне іх. 3 00:00:12,800 --> 00:00:15,750 Алгарытм, памятаеце, гэта проста крок за крокам 4 00:00:15,750 --> 00:00:18,370 Працэдура для выканання задачы. 5 00:00:18,370 --> 00:00:21,470 Асноўная ідэя выбару роду заключаецца ў падзеле 6 00:00:21,470 --> 00:00:23,390 наш спіс на дзве часткі - 7 00:00:23,390 --> 00:00:26,810 Сартаваць часткі і несортированные частку. 8 00:00:26,810 --> 00:00:30,200 На кожным кроку алгарытму, ліку перамяшчаецца з 9 00:00:30,200 --> 00:00:33,800 несортированные часткі да адсартаваныя частка пакуль у рэшце рэшт 10 00:00:33,800 --> 00:00:35,880 Увесь спіс адсартаваны. 11 00:00:35,880 --> 00:00:38,510 Такім чынам, вось спіс з шасці лічбаў - 12 00:00:38,510 --> 00:00:44,010 23, 42, 4, 16, 8 і 15. 13 00:00:44,010 --> 00:00:47,680 Цяпер ўвесь спіс лічыцца адсартаваныя. 14 00:00:47,680 --> 00:00:51,770 Хоць лік як 16 ужо можа быць у правільным 15 00:00:51,770 --> 00:00:56,040 месца, наш алгарытм не мае магчымасці даведацца, што да 16 00:00:56,040 --> 00:00:57,980 Увесь спіс адсартаваны. 17 00:00:57,980 --> 00:01:01,355 Такім чынам, мы будзем разглядаць кожны нумар, які будзе несортированные, пакуль мы не сартаваць 18 00:01:01,355 --> 00:01:03,800 гэта самі. 19 00:01:03,800 --> 00:01:06,890 Мы ведаем, што мы хочам, каб спіс, які будзе ў парадку ўзрастання. 20 00:01:06,890 --> 00:01:10,200 Таму мы хочам стварыць адсартаваны частка нашага спісу 21 00:01:10,200 --> 00:01:13,280 злева направа, ад меншага да большага. 22 00:01:13,280 --> 00:01:17,970 Каб зрабіць гэта, нам трэба знайсці мінімальны элемент несортированные 23 00:01:17,970 --> 00:01:21,350 і паклаў яго ў канцы адсартаваныя частку. 24 00:01:21,350 --> 00:01:25,370 Паколькі гэты спіс не адсартаваны, адзіны спосаб зрабіць гэта, каб 25 00:01:25,370 --> 00:01:29,330 глядзець на кожны элемент у несортированный частка, успомніўшы 26 00:01:29,330 --> 00:01:32,010 якой элемент з'яўляецца самым нізкім і параўноўваючы 27 00:01:32,010 --> 00:01:33,770 кожны элемент гэтага. 28 00:01:33,770 --> 00:01:36,150 Такім чынам, мы спачатку глядзім на 23. 29 00:01:36,150 --> 00:01:38,650 Гэта першы элемент, які мы бачылі, таму мы будзем памятаць 30 00:01:38,650 --> 00:01:40,050 гэта як мінімум. 31 00:01:40,050 --> 00:01:42,320 Далей мы разгледзім 42. 32 00:01:42,320 --> 00:01:46,720 42 больш чым 23, таму 23 па-ранейшаму з'яўляецца мінімальным. 33 00:01:46,720 --> 00:01:51,210 Далей ідзе 4, які з'яўляецца менш, чым 23, так што мы памятаем 4 34 00:01:51,210 --> 00:01:52,880 як новы мінімум. 35 00:01:52,880 --> 00:01:56,380 Далей ідзе 16, якая больш за 4, таму 4 36 00:01:56,380 --> 00:01:57,980 па-ранейшаму з'яўляецца мінімальным. 37 00:01:57,980 --> 00:02:03,670 8, памер якіх перавышае 4, а 15 больш за 4, таму 4 павінна быць 38 00:02:03,670 --> 00:02:05,980 найменшы элемент несортированные. 39 00:02:05,980 --> 00:02:09,350 Так што, хоць, як і людзі, мы можам адразу ўбачыць, што 4 40 00:02:09,350 --> 00:02:12,300 мінімальнага элемента, наш алгарытм павінен глядзець на 41 00:02:12,300 --> 00:02:15,710 кожны элемент несортированные, нават пасля таго, як мы знайшлі 4 - 42 00:02:15,710 --> 00:02:16,860 мінімальны элемент. 43 00:02:16,860 --> 00:02:19,900 Так што цяпер мы знайшлі мінімальны элемент, 4, мы хочам 44 00:02:19,900 --> 00:02:23,410 каб перамясціць яго ў адсартаваным частка спісу. 45 00:02:23,410 --> 00:02:27,320 Так як гэта першы крок, гэта азначае, што мы хочам паставіць 4 на 46 00:02:27,320 --> 00:02:29,680 У пачатку спісу. 47 00:02:29,680 --> 00:02:33,040 Зараз 23 знаходзіцца ў пачатку спісу, так 48 00:02:33,040 --> 00:02:36,080 Давайце абменьвацца 4 і 23. 49 00:02:36,080 --> 00:02:38,870 Так што цяпер наш спіс выглядае наступным чынам. 50 00:02:38,870 --> 00:02:42,710 Мы ведаем, што 4 павінен знаходзіцца ў сваім канчатковым месцы, таму што гэта 51 00:02:42,710 --> 00:02:45,890 як найменшы элемент і элемент у пачатку 52 00:02:45,890 --> 00:02:46,960 спісу. 53 00:02:46,960 --> 00:02:50,650 Такім чынам, гэта азначае, што мы ніколі не павінны перамясціць яго зноў. 54 00:02:50,650 --> 00:02:53,910 Так давайце паўторым гэты працэс, каб дадаць яшчэ адзін элемент 55 00:02:53,910 --> 00:02:55,910 Сартаваць частка спісу. 56 00:02:55,910 --> 00:02:58,950 Мы ведаем, што мы не павінны глядзець на 4, таму што гэта 57 00:02:58,950 --> 00:03:00,000 ўжо адсартаваныя. 58 00:03:00,000 --> 00:03:03,540 Такім чынам, мы можам пачаць у 42, у якой мы будзем памятаць, як 59 00:03:03,540 --> 00:03:05,290 мінімальны элемент. 60 00:03:05,290 --> 00:03:08,700 Так што ў наступны мы будзем глядзець на 23, што менш, чым 42, таму мы 61 00:03:08,700 --> 00:03:11,620 памятаю 23 з'яўляецца новым мінімумам. 62 00:03:11,620 --> 00:03:14,870 Далей мы бачым 16, які менш, чым 23, таму 63 00:03:14,870 --> 00:03:16,800 16 з'яўляецца новым мінімумам. 64 00:03:16,800 --> 00:03:19,720 Цяпер мы глядзім на 8, які менш, чым 16, так 65 00:03:19,720 --> 00:03:21,130 8 з'яўляецца новым мінімумам. 66 00:03:21,130 --> 00:03:25,900 І, нарэшце, 8 менш, чым 15, так што мы ведаем, што 8 з'яўляецца мінімальным 67 00:03:25,900 --> 00:03:27,780 несортированные элемент. 68 00:03:27,780 --> 00:03:30,660 Значыць, мы павінны дадаць 8 да адсартаваны 69 00:03:30,660 --> 00:03:32,450 частка спісу. 70 00:03:32,450 --> 00:03:35,990 Цяпер 4 з'яўляецца адзіным адсартаваны элемент, таму мы хочам змясціць 71 00:03:35,990 --> 00:03:38,410 8 наперад на 4. 72 00:03:38,410 --> 00:03:41,920 З 42 з'яўляецца першым элементам у несортированный частка 73 00:03:41,920 --> 00:03:47,260 Спіс, мы хочам, каб абмяняць 42 і 8. 74 00:03:47,260 --> 00:03:49,680 Так што цяпер наш спіс выглядае наступным чынам. 75 00:03:49,680 --> 00:03:53,830 4 і 8 ўяўляюць сабой спарадкаваныя частцы спісу, а 76 00:03:53,830 --> 00:03:56,440 Астатнія лічбы ўяўляюць несортированные 77 00:03:56,440 --> 00:03:58,260 частка спісу. 78 00:03:58,260 --> 00:04:00,630 Так што давайце працягваць з другога ітэрацыі. 79 00:04:00,630 --> 00:04:03,850 Мы пачынаем з 23 на гэты раз, так як мы не павінны глядзець на 80 00:04:03,850 --> 00:04:05,770 4 і на 8 больш, таму што яны 81 00:04:05,770 --> 00:04:07,660 ўжо адсартаваныя. 82 00:04:07,660 --> 00:04:10,270 16 менш 23, таму мы будзем памятаць 83 00:04:10,270 --> 00:04:12,070 16 у якасці новага мінімуму. 84 00:04:12,070 --> 00:04:18,149 16 менш 42, а 15 менш 16, так 15 павінна быць 85 00:04:18,149 --> 00:04:20,480 мінімальны несортированные элемент. 86 00:04:20,480 --> 00:04:24,580 Такім чынам, зараз мы хочам, каб памяняць 15 і 23 па 87 00:04:24,580 --> 00:04:26,310 дайце нам гэты спіс. 88 00:04:26,310 --> 00:04:30,500 Сартаваць частка спісу складаецца з 4, 8 і 15, і 89 00:04:30,500 --> 00:04:33,210 гэтыя элементы па-ранейшаму адсартаваныя. 90 00:04:33,210 --> 00:04:36,900 Але так ужо здарылася, што наступны элемент несортированные, 16, 91 00:04:36,900 --> 00:04:38,480 ўжо адсартаваныя. 92 00:04:38,480 --> 00:04:42,060 Аднак, няма ніякага спосабу для нашага алгарытму, каб даведацца, што 16 93 00:04:42,060 --> 00:04:45,230 ўжо ў правільным месцы, таму мы ўсё яшчэ павінны 94 00:04:45,230 --> 00:04:47,870 Паўтараю сапраўды такі ж працэс. 95 00:04:47,870 --> 00:04:53,750 Такім чынам, мы бачым, што 16 менш, чым 42, і 16 менш 23, таму 96 00:04:53,750 --> 00:04:56,230 16 павінен быць мінімальным элементам. 97 00:04:56,230 --> 00:04:59,010 Немагчыма абмяняць гэты элемент сам з сабой, таму мы можам 98 00:04:59,010 --> 00:05:01,780 Проста пакіньце яго ў гэтым месцы. 99 00:05:01,780 --> 00:05:04,660 Так што нам трэба яшчэ адзін праход нашага алгарытму. 100 00:05:04,660 --> 00:05:09,370 42 больш 23, таму 23 павінна быць 101 00:05:09,370 --> 00:05:10,970 мінімальная несортированные элемент. 102 00:05:10,970 --> 00:05:17,410 Пасля таго як мы перастаўляць 23 і 42, мы ў канчатковым выніку з нашай апошняй 103 00:05:17,410 --> 00:05:18,530 адсартаваны спіс - 104 00:05:18,530 --> 00:05:23,390 4, 8, 15, 16, 23, 42. 105 00:05:23,390 --> 00:05:26,830 Мы ведаем, што 42 павінны быць у правільным месцы, так як гэта 106 00:05:26,830 --> 00:05:30,210 Адзіны элемент пакінулі, і гэта выбар роду. 107 00:05:30,210 --> 00:05:32,100 Давайце зараз аформіць наш алгарытм з некаторымі 108 00:05:32,100 --> 00:05:34,540 псевдокод. 109 00:05:34,540 --> 00:05:37,760 На першай лініі, мы бачым, што нам трэба інтэграваць па 110 00:05:37,760 --> 00:05:39,530 кожны элемент спісу. 111 00:05:39,530 --> 00:05:42,150 За выключэннем апошняга элемента, так як 1 элемент 112 00:05:42,150 --> 00:05:44,230 спіс ужо адсартаваны. 113 00:05:44,230 --> 00:05:48,100 На другой лініі, мы разгледзім першы элемент несортированные 114 00:05:48,100 --> 00:05:51,080 Частка спісу, каб быць мінімальным, як мы зрабілі з нашым 115 00:05:51,080 --> 00:05:53,750 Напрыклад, у нас ёсць што-то для параўнання. 116 00:05:53,750 --> 00:05:57,260 Трэцяя радок пачынаецца другі цыкл, у якім мы перабору 117 00:05:57,260 --> 00:05:59,170 кожны несортированные элемент. 118 00:05:59,170 --> 00:06:02,150 Мы ведаем, што пасля таго як я ітэрацый, адсартаваныя часткі 119 00:06:02,150 --> 00:06:05,330 з нашага спісу павінны мець элементы я ў ім з кожным крокам 120 00:06:05,330 --> 00:06:06,890 віды аднаго элемента. 121 00:06:06,890 --> 00:06:11,770 Такім чынам, першы несортированные элемент павінен знаходзіцца ў становішчы я плюс 1. 122 00:06:11,770 --> 00:06:15,440 На чацвёртай радку, мы параўноўваем бягучы элемент да мінімуму 123 00:06:15,440 --> 00:06:17,750 элемент, які мы бачылі да гэтага часу. 124 00:06:17,750 --> 00:06:20,560 Калі бягучы элемент менш, чым мінімальная 125 00:06:20,560 --> 00:06:23,870 элемент, то мы памятаем, бягучы элемент у якасці новай 126 00:06:23,870 --> 00:06:26,250 Мінімум на лініі пяць. 127 00:06:26,250 --> 00:06:29,900 Нарэшце, на лініі шэсць і сем, мы перастаўляць мінімальнай 128 00:06:29,900 --> 00:06:33,080 элемент з першым элементам несортированные, такім чынам, 129 00:06:33,080 --> 00:06:36,990 дадаць яго ў адсартаваным частка спісу. 130 00:06:36,990 --> 00:06:40,030 Як толькі мы атрымаем алгарытм, важнае пытанне 131 00:06:40,030 --> 00:06:43,370 сябе ў якасці праграмістаў як доўга гэта зойме? 132 00:06:43,370 --> 00:06:46,970 Мы спачатку задаць пытанне, колькі часу спатрэбіцца для гэтага 133 00:06:46,970 --> 00:06:50,070 Алгарытм для працы ў горшым выпадку? 134 00:06:50,070 --> 00:06:51,640 Нагадаем, мы ўяўляем гэты ход 135 00:06:51,640 --> 00:06:55,060 Час з вялікай пазначэнне O. 136 00:06:55,060 --> 00:06:58,650 Для таго, каб вызначыць мінімальны несортированные элемент, 137 00:06:58,650 --> 00:07:01,880 па сутнасці было параўнаць кожны элемент у спісе 138 00:07:01,880 --> 00:07:04,040 любы іншы элемент у спісе. 139 00:07:04,040 --> 00:07:08,430 Інтуітыўна, гэта гучыць як O п квадрат аперацыі. 140 00:07:08,430 --> 00:07:12,050 Гледзячы на ​​нашым псевдокоде, мы таксама маем цыкл укладзены ў 141 00:07:12,050 --> 00:07:14,420 іншы цыкл, які сапраўды гучыць як O 142 00:07:14,420 --> 00:07:16,480 п квадрат аперацыі. 143 00:07:16,480 --> 00:07:19,250 Аднак памятайце, што мы не павінны глядзець на 144 00:07:19,250 --> 00:07:23,460 Увесь спіс пры вызначэнні мінімальнага несортированные элемент? 145 00:07:23,460 --> 00:07:26,600 Як толькі мы ведалі, што 4 быў адсартаваны, напрыклад, мы не 146 00:07:26,600 --> 00:07:28,170 трэба глядзець на гэта зноў. 147 00:07:28,170 --> 00:07:31,020 Ці значыць гэта, ніжняя час працы? 148 00:07:31,020 --> 00:07:34,510 Для нашага спісу даўжыня 6, нам трэба было зрабіць пяць 149 00:07:34,510 --> 00:07:37,990 параўнанняў для першага элемента, чатыры параўнанняў для 150 00:07:37,990 --> 00:07:40,750 Другі элемент, і так далей. 151 00:07:40,750 --> 00:07:44,690 Гэта азначае, што агульная колькасць крокаў з'яўляецца сумай 152 00:07:44,690 --> 00:07:49,160 лікамі ад 1 да даўжыні спісу мінус 1. 153 00:07:49,160 --> 00:07:51,005 Мы можам прадставіць гэта з дапамогай сумавання. 154 00:07:57,980 --> 00:07:59,910 Мы не будзем удавацца ў сумах тут. 155 00:07:59,910 --> 00:08:04,900 Але аказваецца, што гэта сумаванне роўная п раз 156 00:08:04,900 --> 00:08:07,540 N мінус 1 па 2. 157 00:08:07,540 --> 00:08:14,220 Або, што эквівалентна, п квадрат больш за 2 мінусу п над 2. 158 00:08:14,220 --> 00:08:18,860 Калі гаворка ідзе пра асімптатычнай выканання, гэта п квадрат тэрмін 159 00:08:18,860 --> 00:08:22,070 будзе дамінаваць у гэтай п тэрмін. 160 00:08:22,070 --> 00:08:27,850 Такім чынам, выбар сартавання O п квадрат. 161 00:08:27,850 --> 00:08:31,460 Нагадаем, што ў нашым прыкладзе, выбар роду ўсё яшчэ маюць патрэбу ў 162 00:08:31,460 --> 00:08:33,850 праверце нумар, які быў ужо адсартаваны 163 00:08:33,850 --> 00:08:35,450 Неабходна перамяшчаць. 164 00:08:35,450 --> 00:08:38,929 Такім чынам, гэта азначае, што калі мы пабеглі выбар роду на ўжо 165 00:08:38,929 --> 00:08:43,070 адсартаваны спіс, гэта запатрабуе столькі ж крокаў, як гэта 166 00:08:43,070 --> 00:08:46,340 бы пры працы над цалкам несортированный спіс. 167 00:08:46,340 --> 00:08:51,470 Такім чынам, выбар роду мае лепшым выпадку выканання п квадратаў, 168 00:08:51,470 --> 00:08:56,820 якія мы ўяўляем з амега N ў квадраце. 169 00:08:56,820 --> 00:08:58,600 І вось менавіта для выбару роду. 170 00:08:58,600 --> 00:09:00,630 Гэта толькі адзін з многіх алгарытмаў можна 171 00:09:00,630 --> 00:09:02,390 выкарыстоўваць для сартавання спісу. 172 00:09:02,390 --> 00:09:05,910 Мяне клічуць Томі, і гэта CS50.