1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] Tommy: Poďme sa pozrieť na výber druhu, algoritmus

2
00:00:09,980 --> 00:00:12,800
pre prijatie zoznamu čísel a triedenie.

3
00:00:12,800 --> 00:00:15,750
Algoritmus, pamätajte, je jednoducho krok-za-krokom

4
00:00:15,750 --> 00:00:18,370
Postup pre dosiahnutie úlohy.

5
00:00:18,370 --> 00:00:21,470
Základnou myšlienkou výberu druhu je rozdeliť

6
00:00:21,470 --> 00:00:23,390
náš zoznam na dve časti -

7
00:00:23,390 --> 00:00:26,810
sú zoradené časť a netriedené časť.

8
00:00:26,810 --> 00:00:30,200
Na každom kroku algoritmu, je číslo presunutá zo

9
00:00:30,200 --> 00:00:33,800
netriedeného časť do triedeného časti až nakoniec

10
00:00:33,800 --> 00:00:35,880
Celý zoznam je zoradený.

11
00:00:35,880 --> 00:00:38,510
Takže tu je zoznam šiestich čí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áve teraz celý zoznam sa považuje za netriedený.

14
00:00:47,680 --> 00:00:51,770
Aj keď počet ako 16 už môže byť v jeho správne

15
00:00:51,770 --> 00:00:56,040
zaradenie, náš algoritmus nemá spôsob, ako zistiť, že do

16
00:00:56,040 --> 00:00:57,980
Celý zoznam je zoradený.

17
00:00:57,980 --> 00:01:01,355
Takže budeme považovať každé číslo má byť netriedené, kým triedime

18
00:01:01,355 --> 00:01:03,800
to sami.

19
00:01:03,800 --> 00:01:06,890
Vieme, že chceme, aby zoznam, ktorý bude vo vzostupnom poradí.

20
00:01:06,890 --> 00:01:10,200
Takže budeme chcieť vybudovať zoradená časť nášho zoznamu

21
00:01:10,200 --> 00:01:13,280
zľava doprava, najmenšie k najväčšej.

22
00:01:13,280 --> 00:01:17,970
K tomu, budeme musieť nájsť minimálne zmiešaný prvok

23
00:01:17,970 --> 00:01:21,350
a dať na konci triedeného časti.

24
00:01:21,350 --> 00:01:25,370
Vzhľadom k tomu, tento zoznam nie je zoradený, jediný spôsob, ako to urobiť, je

25
00:01:25,370 --> 00:01:29,330
pozrieť sa na každý prvok v netriedeného časti, spomenul

26
00:01:29,330 --> 00:01:32,010
, Ktorá zložka je najnižšia a porovnávanie

27
00:01:32,010 --> 00:01:33,770
každý prvok k tomu.

28
00:01:33,770 --> 00:01:36,150
Takže budeme sa pozrieť na prvý 23.

29
00:01:36,150 --> 00:01:38,650
Toto je prvý prvok sme videli, takže budeme pamätať

30
00:01:38,650 --> 00:01:40,050
to ako minimum.

31
00:01:40,050 --> 00:01:42,320
Ďalej sa pozrieme na 42.

32
00:01:42,320 --> 00:01:46,720
42 je väčší ako 23, takže 23 je ešte minimálne.

33
00:01:46,720 --> 00:01:51,210
Ďalšia je 4, čo je menej ako 23, takže budeme pamätať 4

34
00:01:51,210 --> 00:01:52,880
ako nový minimum.

35
00:01:52,880 --> 00:01:56,380
Ďalej je 16, ktorý je väčší ako 4, takže 4

36
00:01:56,380 --> 00:01:57,980
je stále minimálne.

37
00:01:57,980 --> 00:02:03,670
8 je väčší ako 4 a 15, je väčší ako 4, takže 4 musí byť

38
00:02:03,670 --> 00:02:05,980
najmenšie netriedeného element.

39
00:02:05,980 --> 00:02:09,350
Takže aj keď ako ľudia môžeme okamžite vidieť, že 4 je

40
00:02:09,350 --> 00:02:12,300
minimálny prvok, náš algoritmus potrebuje pozrieť na

41
00:02:12,300 --> 00:02:15,710
každý netriedený element, aj potom, čo sme našli 4 -

42
00:02:15,710 --> 00:02:16,860
minimálny prvok.

43
00:02:16,860 --> 00:02:19,900
Takže teraz, že sme našli minimálne prvok, 4, budeme chcieť

44
00:02:19,900 --> 00:02:23,410
pohybovať do triedeného časti zoznamu.

45
00:02:23,410 --> 00:02:27,320
Vzhľadom k tomu, je prvý krok, to znamená, že chceme dať 4 na

46
00:02:27,320 --> 00:02:29,680
začiatok zoznamu.

47
00:02:29,680 --> 00:02:33,040
V súčasnej dobe je 23 na začiatku zoznamu, tak

48
00:02:33,040 --> 00:02:36,080
poďme vymeniť 4 a 23.

49
00:02:36,080 --> 00:02:38,870
Takže teraz náš zoznam vyzerá takto.

50
00:02:38,870 --> 00:02:42,710
Je známe, že 4 musí byť v konečnej polohe, pretože je to

51
00:02:42,710 --> 00:02:45,890
ako najmenší prvok a prvok na začiatku

52
00:02:45,890 --> 00:02:46,960
zoznamu.

53
00:02:46,960 --> 00:02:50,650
Takže to znamená, že sme sa nikdy potrebovať presunúť znova.

54
00:02:50,650 --> 00:02:53,910
Takže poďme zopakovať tento proces pridať ďalší prvok do

55
00:02:53,910 --> 00:02:55,910
zoradené časť zoznamu.

56
00:02:55,910 --> 00:02:58,950
Vieme, že nepotrebujeme sa pozrieť na 4, pretože je to

57
00:02:58,950 --> 00:03:00,000
už je zoradený.

58
00:03:00,000 --> 00:03:03,540
Takže môžeme začať na 42, čo budeme pamätať ako

59
00:03:03,540 --> 00:03:05,290
minimálny prvok.

60
00:03:05,290 --> 00:03:08,700
Takže nabudúce sa pozrieme na 23, čo je menej ako 42, takže sme

61
00:03:08,700 --> 00:03:11,620
pamätať 23 je nové minimálne.

62
00:03:11,620 --> 00:03:14,870
Ďalej vidíme 16, ktorý je nižší ako 23, tak

63
00:03:14,870 --> 00:03:16,800
16 je nová minimum.

64
00:03:16,800 --> 00:03:19,720
Teraz sa pozrieme na 8, čo je menej ako 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čne 8 je menší ako 15, takže vieme, že 8 je minimálna

67
00:03:25,900 --> 00:03:27,780
netriedeného element.

68
00:03:27,780 --> 00:03:30,660
Takže to znamená, že by sme mali pripojiť 8 do zoradená

69
00:03:30,660 --> 00:03:32,450
časť zoznamu.

70
00:03:32,450 --> 00:03:35,990
Práve teraz 4 je jediným zoradená prvok, a tak chceme umiestniť

71
00:03:35,990 --> 00:03:38,410
8 vedľa 4.

72
00:03:38,410 --> 00:03:41,920
Vzhľadom k tomu, 42 je prvý prvok v netriedeného časti

73
00:03:41,920 --> 00:03:47,260
Zoznam, budeme chcieť vymeniť 42 a 8.

74
00:03:47,260 --> 00:03:49,680
Takže teraz náš zoznam vyzerá takto.

75
00:03:49,680 --> 00:03:53,830
4 a 8 predstavujú zoradená časť zoznamu, a

76
00:03:53,830 --> 00:03:56,440
Zvyšné čísla predstavujú netriedeného

77
00:03:56,440 --> 00:03:58,260
časť zoznamu.

78
00:03:58,260 --> 00:04:00,630
Takže poďme pokračovať s ďalšie iterácie.

79
00:04:00,630 --> 00:04:03,850
Začneme s 23 tentoraz, pretože nepotrebujeme sa pozerať na

80
00:04:03,850 --> 00:04:05,770
je 4 a 8 už preto, že som

81
00:04:05,770 --> 00:04:07,660
už zoradené.

82
00:04:07,660 --> 00:04:10,270
16 je nižší ako 23, takže sa budeme pamätať

83
00:04:10,270 --> 00:04:12,070
16 ako nové minimum.

84
00:04:12,070 --> 00:04:18,149
16 je nižší ako 42, ale 15 je menší ako 16, takže 15 musí byť

85
00:04:18,149 --> 00:04:20,480
minimálny netriedeného element.

86
00:04:20,480 --> 00:04:24,580
Takže teraz chceme vymeniť 15 a 23, aby sa

87
00:04:24,580 --> 00:04:26,310
nám tento zoznam.

88
00:04:26,310 --> 00:04:30,500
Zoradené časť zoznamu sa skladá zo 4, 8 a 15, a

89
00:04:30,500 --> 00:04:33,210
tieto prvky sú stále netriedené.

90
00:04:33,210 --> 00:04:36,900
Ale to len tak sa stane, že ďalšie netriedený prvok, 16,

91
00:04:36,900 --> 00:04:38,480
už je zoradený.

92
00:04:38,480 --> 00:04:42,060
Avšak, neexistuje žiadny spôsob, ako pre náš algoritmus vedieť, že 16

93
00:04:42,060 --> 00:04:45,230
je už vo svojej správne miesto, takže musíme ešte

94
00:04:45,230 --> 00:04:47,870
opakovať presne rovnaký postup.

95
00:04:47,870 --> 00:04:53,750
Takže vidíme, že 16 je nižší ako 42, a 16 je nižší ako 23, takže

96
00:04:53,750 --> 00:04:56,230
16 musí byť minimálne prvok.

97
00:04:56,230 --> 00:04:59,010
Je možné vymeniť tento prvok sám so sebou, takže môžeme

98
00:04:59,010 --> 00:05:01,780
proste nechať to v tomto mieste.

99
00:05:01,780 --> 00:05:04,660
Takže potrebujeme ešte jeden priechod nášho algoritmu.

100
00:05:04,660 --> 00:05:09,370
42 je väčší ako 23, takže 23 musí byť

101
00:05:09,370 --> 00:05:10,970
Minimálna netriedeného element.

102
00:05:10,970 --> 00:05:17,410
Akonáhle sme prestavenie 23 a 42, skončíme s naším konečným

103
00:05:17,410 --> 00:05:18,530
zoradený zoznam -

104
00:05:18,530 --> 00:05:23,390
4, 8, 15, 16, 23, 42.

105
00:05:23,390 --> 00:05:26,830
Vieme, že 42 musí byť na správnom mieste, pretože je to

106
00:05:26,830 --> 00:05:30,210
Jediný prvok doľava, a to je výber sort.

107
00:05:30,210 --> 00:05:32,100
Poďme sa teraz formalizovať náš algoritmus s niektorými

108
00:05:32,100 --> 00:05:34,540
pseudokód.

109
00:05:34,540 --> 00:05:37,760
Na prvom riadku, môžeme vidieť, že potrebujeme integrovať cez

110
00:05:37,760 --> 00:05:39,530
každý prvok zoznamu.

111
00:05:39,530 --> 00:05:42,150
Okrem posledného prvku, pretože 1 prvok

112
00:05:42,150 --> 00:05:44,230
Zoznam už je zoradený.

113
00:05:44,230 --> 00:05:48,100
Na druhej linke, považujeme prvý prvok netriedeného

114
00:05:48,100 --> 00:05:51,080
Časť zoznamu byť minimálny, ako sme s našou

115
00:05:51,080 --> 00:05:53,750
Napríklad, takže máme niečo pre porovnanie na.

116
00:05:53,750 --> 00:05:57,260
Riadok tri začína druhý cyklus, v ktorom sa iterácii

117
00:05:57,260 --> 00:05:59,170
Každý netriedeného element.

118
00:05:59,170 --> 00:06:02,150
Vieme, že potom, čo som iteráciách, sú zoradené časť

119
00:06:02,150 --> 00:06:05,330
nášho zoznamu musí mať aj prvky v ňom od každého kroku

120
00:06:05,330 --> 00:06:06,890
druhy jeden prvok.

121
00:06:06,890 --> 00:06:11,770
Takže prvý netriedeného prvok musí byť v polohe I plus 1.

122
00:06:11,770 --> 00:06:15,440
Na radový štvorvalec, porovnáme aktuálny prvok na minimum

123
00:06:15,440 --> 00:06:17,750
prvok, ktorý sme videli doteraz.

124
00:06:17,750 --> 00:06:20,560
Ak je aktuálna prvok je menší ako minimálny

125
00:06:20,560 --> 00:06:23,870
prvok, potom by sme mať na pamäti aktuálne element ako nové

126
00:06:23,870 --> 00:06:26,250
minimum na linke päť.

127
00:06:26,250 --> 00:06:29,900
Napokon, na tratiach šesť a sedem, vymeníme minimálne

128
00:06:29,900 --> 00:06:33,080
prvok s prvým netriedeného prvku, a tým

129
00:06:33,080 --> 00:06:36,990
pridaním do triedeného časti zoznamu.

130
00:06:36,990 --> 00:06:40,030
Akonáhle budeme mať algoritmus, dôležitá otázka sa opýtať

131
00:06:40,030 --> 00:06:43,370
sami seba ako programátorov je, ako dlho to trvalo?

132
00:06:43,370 --> 00:06:46,970
Ukážeme si klásť otázku, ako dlho to trvá, než to

133
00:06:46,970 --> 00:06:50,070
algoritmus bežať v najhoršom prípade?

134
00:06:50,070 --> 00:06:51,640
Spomínam si, že sme reprezentovať tento beh

135
00:06:51,640 --> 00:06:55,060
čas s veľkým O notácie.

136
00:06:55,060 --> 00:06:58,650
Aby bolo možné určiť minimálnu zmiešaný prvok, sme

137
00:06:58,650 --> 00:07:01,880
v podstate musel porovnať každý prvok v zozname na

138
00:07:01,880 --> 00:07:04,040
každý iný prvok v zozname.

139
00:07:04,040 --> 00:07:08,430
Intuitívne, toto znie ako O n na druhú operáciu.

140
00:07:08,430 --> 00:07:12,050
Pri pohľade na našom pseudokódu, máme tiež slučky vnorené vo vnútri

141
00:07:12,050 --> 00:07:14,420
ďalšie slučka, ktorá naozaj znie ako O

142
00:07:14,420 --> 00:07:16,480
z n štvorcový prevádzky.

143
00:07:16,480 --> 00:07:19,250
Pamätajte však, že sme nemuseli pozerať na

144
00:07:19,250 --> 00:07:23,460
Celý zoznam pri stanovení minimálnej zmesný element?

145
00:07:23,460 --> 00:07:26,600
Akonáhle sme vedeli, že 4 bola zoradená, napríklad, my nie

146
00:07:26,600 --> 00:07:28,170
treba sa na to pozrieť znova.

147
00:07:28,170 --> 00:07:31,020
Takže to robí nižšiu prevádzkovú dobu?

148
00:07:31,020 --> 00:07:34,510
Pre nášho zoznamu dĺžky 6, potrebovali sme robia päť

149
00:07:34,510 --> 00:07:37,990
porovnaní za prvý prvok, štyri porovnanie pre

150
00:07:37,990 --> 00:07:40,750
druhý prvok, a tak ďalej.

151
00:07:40,750 --> 00:07:44,690
To znamená, že celkový počet krokov je súčet

152
00:07:44,690 --> 00:07:49,160
celé čísla od 1 do dĺžky zoznamu mínus 1.

153
00:07:49,160 --> 00:07:51,005
Môžeme reprezentovať to s sumácia.

154
00:07:57,980 --> 00:07:59,910
Nebudeme zachádzať do summations tu.

155
00:07:59,910 --> 00:08:04,900
Ale ukazuje sa, že toto zhrnutie je rovná n krát

156
00:08:04,900 --> 00:08:07,540
n mínus 1 nad 2.

157
00:08:07,540 --> 00:08:14,220
Alebo ekvivalentne, n narovnal nad 2 mínus n nad 2.

158
00:08:14,220 --> 00:08:18,860
Keď sa hovorí o asymptotickej behu, to n squared termín

159
00:08:18,860 --> 00:08:22,070
bude ovládať tento n termín.

160
00:08:22,070 --> 00:08:27,850
Takže výber sort O z n na druhú.

161
00:08:27,850 --> 00:08:31,460
Pripomeňme si, že v našom príklade, výber sort stále potrebné

162
00:08:31,460 --> 00:08:33,850
skontrolujte, či číslo, ktoré bolo už je zoradený

163
00:08:33,850 --> 00:08:35,450
potrebné k presunu.

164
00:08:35,450 --> 00:08:38,929
Takže to znamená, že ak sme bežali výber druhu cez už

165
00:08:38,929 --> 00:08:43,070
zoradený zoznam, vyžadovalo by to rovnaký počet krokov ako to

166
00:08:43,070 --> 00:08:46,340
by pri jazde na úplne netriedeného zoznamu.

167
00:08:46,340 --> 00:08:51,470
Takže výber spôsob má najlepšiu prípadovú výkon n na druhú,

168
00:08:51,470 --> 00:08:56,820
ktoré predstavujú s omega n mocninou.

169
00:08:56,820 --> 00:08:58,600
A to je pre výber druhu.

170
00:08:58,600 --> 00:09:00,630
Iba jeden z mnohých algoritmov sa môžeme

171
00:09:00,630 --> 00:09:02,390
použiť na zoradenie zoznamu.

172
00:09:02,390 --> 00:09:05,910
Moje meno je Tommy, a to je cs50.