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
pseudocode.

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
Линија три започнува вториот циклус во кој ние iterate во текот

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
на нашата листа мора i елементи во него, бидејќи секој чекор

120
00:06:05,330 --> 00:06:06,890
видови еден елемент.

121
00:06:06,890 --> 00:06:11,770
Така, првиот несортиран елемент мора да биде во позиција i плус 1.

122
00:06:11,770 --> 00:06:15,440
On-line четири, ние споредуваат тековниот елемент на минимум

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

140
00:07:08,430 --> 00:07:12,050
Гледајќи нашата pseudocode, ние исто така имаат јамка вгнездени внатре

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

142
00:07:14,420 --> 00:07:16,480
од n квадрат операција.

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
Ние не ќе одат во summations тука.

155
00:07:59,910 --> 00:08:04,900
Но излегува дека овој збир е еднаков на n пати

156
00:08:04,900 --> 00:08:07,540
n минус 1 повеќе од 2.

157
00:08:07,540 --> 00:08:14,220
Или еквивалентно, n квадрат над 2 минус n над 2.

158
00:08:14,220 --> 00:08:18,860
Кога зборуваме за асимптотска траење, овој n квадрат рок

159
00:08:18,860 --> 00:08:22,070
ќе доминираат овој n рок.

160
00:08:22,070 --> 00:08:27,850
Значи селекција вид е о од n квадрат.

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
Значи селекција вид има најдобар случај перформанси од n квадрат,

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.