1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] ТОММИ: Хајде да погледамо на избор врсте, алгоритам

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
Време са великим О нотацији.

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
Интуитивно, ово звучи као О н квадрат рада.

140
00:07:08,430 --> 00:07:12,050
Гледајући наше Псеудокод, ми такође имамо петљу угнежђену унутра

141
00:07:12,050 --> 00:07:14,420
друга петља, која заиста звучи као О

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
н минус 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
Дакле, избор врста је О од н квадрат.

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
које представљају са омега н квадрат.

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
Моје име је Томи, а ово је цс50.