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
Ние знаем, че не е нужно да търсите в четири, защото това е

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
С изключение на последния елемент, тъй като един елемент

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
Така че първо несортирани елемент трябва да бъде в позиция плюс един.

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

140
00:07:08,430 --> 00:07:12,050
Търсите в нашия pseudocode, ние също имаме една линия, вплетена в

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

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
Или еквивалентно, N квадрат над 2 минус N над 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 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
, които ние представляваме с омега-н квадрат.

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.