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.