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
псевдокод.

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
Время с большой обозначение 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
Интуитивно, это звучит как O п квадрат операции.

140
00:07:08,430 --> 00:07:12,050
Глядя на нашем псевдокоде, мы также имеем цикл вложен в

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
Мы не будем вдаваться в суммах здесь.

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
Или, что эквивалентно, п квадрат более 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
Таким образом, выбор сортировки O п квадрат.

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
которые мы представляем с омега 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.