1 00:00:06,762 --> 00:00:09,980 [Powered by Google Translate] Tommy: Pojďme se podívat na výběr druhu, algoritmus 2 00:00:09,980 --> 00:00:12,800 pro přijetí seznamu čísel a třídění. 3 00:00:12,800 --> 00:00:15,750 Algoritmus, pamatujte, je prostě krok-za-krokem 4 00:00:15,750 --> 00:00:18,370 Postup pro dosažení úkolu. 5 00:00:18,370 --> 00:00:21,470 Základní myšlenkou výběru druhu je rozdělit 6 00:00:21,470 --> 00:00:23,390 náš seznam na dvě části - 7 00:00:23,390 --> 00:00:26,810 jsou seřazena část a netříděné část. 8 00:00:26,810 --> 00:00:30,200 Na každém kroku algoritmu, je číslo přesunuta ze 9 00:00:30,200 --> 00:00:33,800 netříděného část do tříděného části až nakonec 10 00:00:33,800 --> 00:00:35,880 Celý seznam je seřazen. 11 00:00:35,880 --> 00:00:38,510 Takže tady je seznam šesti čísel - 12 00:00:38,510 --> 00:00:44,010 23, 42, 4, 16, 8, a 15. 13 00:00:44,010 --> 00:00:47,680 Právě teď se celý seznam se považuje za netříděný. 14 00:00:47,680 --> 00:00:51,770 I když počet jako 16 již může být v jeho správné 15 00:00:51,770 --> 00:00:56,040 zařazení, náš algoritmus nemá způsob, jak zjistit, že do 16 00:00:56,040 --> 00:00:57,980 Celý seznam je seřazen. 17 00:00:57,980 --> 00:01:01,355 Takže budeme považovat každé číslo má být netříděné, dokud třídíme 18 00:01:01,355 --> 00:01:03,800 to sami. 19 00:01:03,800 --> 00:01:06,890 Víme, že chceme, aby seznam, který bude ve vzestupném pořadí. 20 00:01:06,890 --> 00:01:10,200 Takže budeme chtít vybudovat seřazena část našeho seznamu 21 00:01:10,200 --> 00:01:13,280 zleva doprava, nejmenší k největší. 22 00:01:13,280 --> 00:01:17,970 K tomu, budeme muset najít minimální směsný prvek 23 00:01:17,970 --> 00:01:21,350 a dát na konci tříděného části. 24 00:01:21,350 --> 00:01:25,370 Vzhledem k tomu, tento seznam není seřazen, jediný způsob, jak to udělat, je 25 00:01:25,370 --> 00:01:29,330 podívat se na každý prvek v netříděného části, vzpomněl 26 00:01:29,330 --> 00:01:32,010 , která složka je nejnižší a porovnávání 27 00:01:32,010 --> 00:01:33,770 každý prvek k tomu. 28 00:01:33,770 --> 00:01:36,150 Takže budeme se podívat na první 23. 29 00:01:36,150 --> 00:01:38,650 Toto je první prvek jsme viděli, takže budeme pamatovat 30 00:01:38,650 --> 00:01:40,050 to jako minimum. 31 00:01:40,050 --> 00:01:42,320 Dále se podíváme na 42. 32 00:01:42,320 --> 00:01:46,720 42 je větší než 23, takže 23 je ještě minimální. 33 00:01:46,720 --> 00:01:51,210 Další je 4, což je méně než 23, takže budeme pamatovat 4 34 00:01:51,210 --> 00:01:52,880 jako nový minimum. 35 00:01:52,880 --> 00:01:56,380 Dále je 16, který je větší než 4, takže 4 36 00:01:56,380 --> 00:01:57,980 je stále minimální. 37 00:01:57,980 --> 00:02:03,670 8 je větší než 4 a 15, je větší než 4, takže 4 musí být 38 00:02:03,670 --> 00:02:05,980 nejmenší netříděného element. 39 00:02:05,980 --> 00:02:09,350 Takže i když jako lidé můžeme okamžitě vidět, že 4 je 40 00:02:09,350 --> 00:02:12,300 minimální prvek, náš algoritmus musí se dívat na 41 00:02:12,300 --> 00:02:15,710 každý netříděný element, i poté, co jsme našli 4 - 42 00:02:15,710 --> 00:02:16,860 minimální prvek. 43 00:02:16,860 --> 00:02:19,900 Takže teď, že jsme našli minimální prvek, 4, budeme chtít 44 00:02:19,900 --> 00:02:23,410 pohybovat do tříděného části seznamu. 45 00:02:23,410 --> 00:02:27,320 Vzhledem k tomu, je první krok, to znamená, že chceme dát 4 na 46 00:02:27,320 --> 00:02:29,680 začátek seznamu. 47 00:02:29,680 --> 00:02:33,040 V současné době je 23 na začátku seznamu, tak 48 00:02:33,040 --> 00:02:36,080 pojďme vyměnit 4 a 23. 49 00:02:36,080 --> 00:02:38,870 Takže teď náš seznam vypadá takto. 50 00:02:38,870 --> 00:02:42,710 Je známo, že 4 musí být v konečné poloze, protože je to 51 00:02:42,710 --> 00:02:45,890 jak nejmenší prvek a prvek na začátku 52 00:02:45,890 --> 00:02:46,960 seznamu. 53 00:02:46,960 --> 00:02:50,650 Takže to znamená, že jsme se nikdy potřebovat přesunout znovu. 54 00:02:50,650 --> 00:02:53,910 Takže pojďme zopakovat tento proces přidat další prvek na 55 00:02:53,910 --> 00:02:55,910 seřazeny část seznamu. 56 00:02:55,910 --> 00:02:58,950 Víme, že nepotřebujeme se podívat na 4, protože je to 57 00:02:58,950 --> 00:03:00,000 již řazeno. 58 00:03:00,000 --> 00:03:03,540 Takže můžeme začít na 42, což budeme pamatovat jako 59 00:03:03,540 --> 00:03:05,290 minimální prvek. 60 00:03:05,290 --> 00:03:08,700 Takže příště se podíváme na 23, což je méně než 42, takže jsme 61 00:03:08,700 --> 00:03:11,620 pamatovat 23 je nové minimální. 62 00:03:11,620 --> 00:03:14,870 Dále vidíme 16, který je nižší než 23, tak 63 00:03:14,870 --> 00:03:16,800 16 je nový minimální. 64 00:03:16,800 --> 00:03:19,720 Teď se podíváme na 8, což je méně než 16, tak 65 00:03:19,720 --> 00:03:21,130 8 je nová minimum. 66 00:03:21,130 --> 00:03:25,900 A konečně 8 je menší než 15, takže víme, že 8 je minimální 67 00:03:25,900 --> 00:03:27,780 netříděného element. 68 00:03:27,780 --> 00:03:30,660 Takže to znamená, že bychom měli připojit 8 do seřazena 69 00:03:30,660 --> 00:03:32,450 část seznamu. 70 00:03:32,450 --> 00:03:35,990 Právě teď 4 je jediným seřazena prvek, a tak chceme umístit 71 00:03:35,990 --> 00:03:38,410 8 vedle 4. 72 00:03:38,410 --> 00:03:41,920 Vzhledem k tomu, 42 je první prvek v netříděného části 73 00:03:41,920 --> 00:03:47,260 Seznam, budeme chtít vyměnit 42 a 8. 74 00:03:47,260 --> 00:03:49,680 Takže teď náš seznam vypadá takto. 75 00:03:49,680 --> 00:03:53,830 4 a 8 představují seřazena část seznamu, a 76 00:03:53,830 --> 00:03:56,440 Zbývající čísla představují netříděného 77 00:03:56,440 --> 00:03:58,260 část seznamu. 78 00:03:58,260 --> 00:04:00,630 Takže pojďme pokračovat s další iterace. 79 00:04:00,630 --> 00:04:03,850 Začneme s 23 tentokrát, protože nepotřebujeme se dívat na 80 00:04:03,850 --> 00:04:05,770 je 4 a 8 už proto, že jsem 81 00:04:05,770 --> 00:04:07,660 již seřazeny. 82 00:04:07,660 --> 00:04:10,270 16 je nižší než 23, takže se budeme pamatovat 83 00:04:10,270 --> 00:04:12,070 16 jako nové minimum. 84 00:04:12,070 --> 00:04:18,149 16 je nižší než 42, ale 15 je menší než 16, takže 15 musí být 85 00:04:18,149 --> 00:04:20,480 minimální netříděného element. 86 00:04:20,480 --> 00:04:24,580 Takže teď chceme vyměnit 15 a 23, aby se 87 00:04:24,580 --> 00:04:26,310 nám tento seznam. 88 00:04:26,310 --> 00:04:30,500 Pořadí seřazených část seznamu se skládá ze 4, 8 a 15, a 89 00:04:30,500 --> 00:04:33,210 tyto prvky jsou stále netříděné. 90 00:04:33,210 --> 00:04:36,900 Ale to jen tak se stane, že další netříděný prvek, 16, 91 00:04:36,900 --> 00:04:38,480 je již řazeno. 92 00:04:38,480 --> 00:04:42,060 Nicméně, neexistuje žádný způsob, jak pro náš algoritmus na to, že 16 93 00:04:42,060 --> 00:04:45,230 je již ve své správné místo, takže musíme ještě 94 00:04:45,230 --> 00:04:47,870 opakovat přesně stejný postup. 95 00:04:47,870 --> 00:04:53,750 Takže vidíme, že 16 je nižší než 42, a 16 je nižší než 23, takže 96 00:04:53,750 --> 00:04:56,230 16 musí být minimální prvek. 97 00:04:56,230 --> 00:04:59,010 Je nemožné vyměnit tento prvek sám se sebou, takže můžeme 98 00:04:59,010 --> 00:05:01,780 prostě nechat to v tomto místě. 99 00:05:01,780 --> 00:05:04,660 Takže potřebujeme ještě jeden průchod našeho algoritmu. 100 00:05:04,660 --> 00:05:09,370 42 je větší než 23, takže 23 musí být 101 00:05:09,370 --> 00:05:10,970 Minimální netříděného element. 102 00:05:10,970 --> 00:05:17,410 Jakmile vyměníme na 23 a 42, skončíme s naším konečným 103 00:05:17,410 --> 00:05:18,530 seřazený seznam - 104 00:05:18,530 --> 00:05:23,390 4, 8, 15, 16, 23, 42. 105 00:05:23,390 --> 00:05:26,830 Víme, že 42 musí být na správném místě, protože je to 106 00:05:26,830 --> 00:05:30,210 Jediný prvek doleva, a to je výběr sort. 107 00:05:30,210 --> 00:05:32,100 Pojďme se nyní formalizovat náš algoritmus s některými 108 00:05:32,100 --> 00:05:34,540 pseudokód. 109 00:05:34,540 --> 00:05:37,760 Na prvním řádku, můžeme vidět, že potřebujeme integrovat přes 110 00:05:37,760 --> 00:05:39,530 každý prvek seznamu. 111 00:05:39,530 --> 00:05:42,150 Kromě posledního prvku, protože 1 prvek 112 00:05:42,150 --> 00:05:44,230 Seznam je již řazeno. 113 00:05:44,230 --> 00:05:48,100 Na druhé lince, považujeme první prvek netříděného 114 00:05:48,100 --> 00:05:51,080 Část seznamu být minimální, jak jsme s naší 115 00:05:51,080 --> 00:05:53,750 Například, takže máme něco pro porovnání na. 116 00:05:53,750 --> 00:05:57,260 Řádek tři začíná druhý cyklus, ve kterém se iteraci 117 00:05:57,260 --> 00:05:59,170 Každý netříděného element. 118 00:05:59,170 --> 00:06:02,150 Víme, že poté, co jsem iteracích, jsou seřazeny část 119 00:06:02,150 --> 00:06:05,330 našeho seznamu musí mít i prvky v něm od každého kroku 120 00:06:05,330 --> 00:06:06,890 druhy jeden prvek. 121 00:06:06,890 --> 00:06:11,770 Takže první netříděného prvek musí být v poloze I plus 1. 122 00:06:11,770 --> 00:06:15,440 Na řadový čtyřválec, srovnáme aktuální prvek na minimum 123 00:06:15,440 --> 00:06:17,750 prvek, který jsme viděli doposud. 124 00:06:17,750 --> 00:06:20,560 Pokud aktuální prvek je menší než minimální 125 00:06:20,560 --> 00:06:23,870 prvek, pak bychom mít na paměti aktuální element jako nové 126 00:06:23,870 --> 00:06:26,250 minimum na lince pět. 127 00:06:26,250 --> 00:06:29,900 Konečně, na tratích šest a sedm, vyměníme minimální 128 00:06:29,900 --> 00:06:33,080 prvek s prvním netříděného prvku, a tím 129 00:06:33,080 --> 00:06:36,990 přidáním do tříděného části seznamu. 130 00:06:36,990 --> 00:06:40,030 Jakmile budeme mít algoritmus, důležitá otázka se zeptat 131 00:06:40,030 --> 00:06:43,370 sami sebe jako programátory je, jak dlouho to trvalo? 132 00:06:43,370 --> 00:06:46,970 Ukážeme si klást otázku, jak dlouho to trvá, než to 133 00:06:46,970 --> 00:06:50,070 algoritmus běžet v nejhorším případě? 134 00:06:50,070 --> 00:06:51,640 Vzpomínám si, že jsme reprezentovat tento běh 135 00:06:51,640 --> 00:06:55,060 čas s velkým O notace. 136 00:06:55,060 --> 00:06:58,650 Aby bylo možné určit minimální směsný prvek, jsme 137 00:06:58,650 --> 00:07:01,880 v podstatě musel srovnat každý prvek v seznamu na 138 00:07:01,880 --> 00:07:04,040 každý jiný prvek v seznamu. 139 00:07:04,040 --> 00:07:08,430 Intuitivně, toto zní jako O n na druhou operaci. 140 00:07:08,430 --> 00:07:12,050 Při pohledu na našem pseudokódu, máme také smyčky vnořené uvnitř 141 00:07:12,050 --> 00:07:14,420 další smyčka, která opravdu zní jako O 142 00:07:14,420 --> 00:07:16,480 z n čtvercový provozu. 143 00:07:16,480 --> 00:07:19,250 Pamatujte však, že jsme nemuseli dívat na 144 00:07:19,250 --> 00:07:23,460 Celý seznam při stanovení minimální směsný element? 145 00:07:23,460 --> 00:07:26,600 Jakmile jsme věděli, že 4 byla seřazena, například, my ne 146 00:07:26,600 --> 00:07:28,170 je třeba se na to podívat znovu. 147 00:07:28,170 --> 00:07:31,020 Takže to dělá nižší provozní dobu? 148 00:07:31,020 --> 00:07:34,510 Pro našeho seznamu délky 6, potřebovali jsme dělají pět 149 00:07:34,510 --> 00:07:37,990 srovnání za první prvek, čtyři srovnání pro 150 00:07:37,990 --> 00:07:40,750 druhý prvek, a tak dále. 151 00:07:40,750 --> 00:07:44,690 To znamená, že celkový počet kroků je součet 152 00:07:44,690 --> 00:07:49,160 celá čísla od 1 do délky seznamu mínus 1. 153 00:07:49,160 --> 00:07:51,005 Můžeme reprezentovat to s sumace. 154 00:07:57,980 --> 00:07:59,910 Nebudeme zacházet do summations zde. 155 00:07:59,910 --> 00:08:04,900 Ale ukazuje se, že toto shrnutí je rovna n krát 156 00:08:04,900 --> 00:08:07,540 n minus 1 nad 2. 157 00:08:07,540 --> 00:08:14,220 Nebo ekvivalentně, n narovnal nad 2 minus n nad 2. 158 00:08:14,220 --> 00:08:18,860 Když se mluví o asymptotické běhu, to n squared termín 159 00:08:18,860 --> 00:08:22,070 bude ovládat tento n termín. 160 00:08:22,070 --> 00:08:27,850 Takže výběr sort O z n na druhou. 161 00:08:27,850 --> 00:08:31,460 Připomeňme si, že v našem příkladu, výběr sort stále potřeba 162 00:08:31,460 --> 00:08:33,850 zkontrolujte, zda číslo, které bylo již řazeno 163 00:08:33,850 --> 00:08:35,450 potřebné k přesunu. 164 00:08:35,450 --> 00:08:38,929 Takže to znamená, že pokud jsme běželi výběr druhu přes již 165 00:08:38,929 --> 00:08:43,070 seřazený seznam, vyžadovalo by to stejný počet kroků jako to 166 00:08:43,070 --> 00:08:46,340 by při jízdě na zcela netříděného seznamu. 167 00:08:46,340 --> 00:08:51,470 Takže výběr způsob má nejlepší případovou výkon n na druhou, 168 00:08:51,470 --> 00:08:56,820 které představují s omega n mocninou. 169 00:08:56,820 --> 00:08:58,600 A to je pro výběr druhu. 170 00:08:58,600 --> 00:09:00,630 Pouze jeden z mnoha algoritmů se můžeme 171 00:09:00,630 --> 00:09:02,390 použít k seřazení seznamu. 172 00:09:02,390 --> 00:09:05,910 Mé jméno je Tommy, a to je cs50.