1
00:00:00,000 --> 00:00:03,360
>> [Играет музыка]

2
00:00:03,360 --> 00:00:04,522

3
00:00:04,522 --> 00:00:06,730
ДАГ Lloyd: Ладно,
пузырьковой сортировки является алгоритм

4
00:00:06,730 --> 00:00:08,730
Вы можете использовать для сортировки набора элементов.

5
00:00:08,730 --> 00:00:10,850
Давайте взглянем на то, как это работает.

6
00:00:10,850 --> 00:00:13,240
>> Таким образом, основная идея
пузырьковой сортировки заключается в следующем.

7
00:00:13,240 --> 00:00:17,340
Как правило, мы хотим, чтобы двигаться выше
значения элементов, как правило вправо,

8
00:00:17,340 --> 00:00:20,340
и снизить сумму элементов, как правило
слева, как и следовало ожидать.

9
00:00:20,340 --> 00:00:23,256
Мы хотим, чтобы нижние вещи, чтобы быть в
начало, и более высокие вещи

10
00:00:23,256 --> 00:00:24,970
чтобы быть в конце.

11
00:00:24,970 --> 00:00:26,130
>> как нам это сделать?

12
00:00:26,130 --> 00:00:28,040
Ну в псевдокода кода,
мы могли бы сказать, давайте

13
00:00:28,040 --> 00:00:30,320
установить счетчик на своп не-нулевое значение.

14
00:00:30,320 --> 00:00:32,570
Мы увидим, почему мы делаем, что в секунду.

15
00:00:32,570 --> 00:00:36,090
А потом мы повторяем следующие
Процесс пока счетчик не подкачки равен 0,

16
00:00:36,090 --> 00:00:39,910
или пока мы не делаем никаких свопы на всех.

17
00:00:39,910 --> 00:00:43,170
>> Сброс подкачки счетчик
0, если это не уже 0.

18
00:00:43,170 --> 00:00:46,420
Тогда посмотрите на каждый
соседней парой элементов.

19
00:00:46,420 --> 00:00:49,550
Если эти два элемента
не в порядке, поменять их местами,

20
00:00:49,550 --> 00:00:51,620
и добавить 1 к прилавку подкачки.

21
00:00:51,620 --> 00:00:53,870
Если вы думаете о
это, прежде чем визуализировать его,

22
00:00:53,870 --> 00:00:57,471
заметить, что это будет двигаться ниже
значения элементов слева

23
00:00:57,471 --> 00:01:00,720
и выше ценится элементы права,
эффективно делать то, что мы хотим сделать,

24
00:01:00,720 --> 00:01:03,940
что двигаться те группы
элементов таким образом.

25
00:01:03,940 --> 00:01:07,035
Давайте себе, как это
может выглядеть с помощью нашего массива

26
00:01:07,035 --> 00:01:10,504
что мы использовали для тестирования
из этих алгоритмов.

27
00:01:10,504 --> 00:01:13,420
У нас есть несортированный массив здесь,
указывает все элементы

28
00:01:13,420 --> 00:01:14,840
находясь в красный цвет.

29
00:01:14,840 --> 00:01:17,970
И я могу установить счетчик подкачки
в ненулевое значение.

30
00:01:17,970 --> 00:01:20,610
Я выбрал произвольно
отрицательное 1-- это не 0.

31
00:01:20,610 --> 00:01:23,840
Мы хотим, чтобы повторить этот процесс
до счетчика подкачки не равно 0.

32
00:01:23,840 --> 00:01:26,540
Вот почему я могу установить своп
вразрез с какой-то ненулевое значение,

33
00:01:26,540 --> 00:01:29,400
поскольку в противном случае
Счетчик подкачки будет 0.

34
00:01:29,400 --> 00:01:31,610
Мы даже не начать
Процесс алгоритма.

35
00:01:31,610 --> 00:01:33,610
Итак, еще раз, шаги are--
сбросить счетчик подкачки

36
00:01:33,610 --> 00:01:37,900
0, а затем посмотреть на каждый рядом
пара, и если они не в порядке,

37
00:01:37,900 --> 00:01:40,514
обменять их, и добавить 1
к прилавку подкачки.

38
00:01:40,514 --> 00:01:41,680
Итак, давайте начнем этот процесс.

39
00:01:41,680 --> 00:01:44,430
Поэтому первое, что мы делаем, это
мы устанавливаем счетчик подкачки на 0,

40
00:01:44,430 --> 00:01:46,660
и тогда мы начинаем глядя
на каждой смежной пары.

41
00:01:46,660 --> 00:01:49,140
>> Так мы впервые начать смотреть на 5 и 2.

42
00:01:49,140 --> 00:01:52,410
Мы видим, что они находятся вне
заказать и поэтому мы поменять их местами.

43
00:01:52,410 --> 00:01:53,830
И мы добавляем 1 к прилавку подкачки.

44
00:01:53,830 --> 00:01:57,860
Так что теперь наша подкачки счетчик 1,
и 2 и 5 были включены.

45
00:01:57,860 --> 00:01:59,370
Теперь мы повторяем этот процесс снова.

46
00:01:59,370 --> 00:02:03,540
>> Мы смотрим на следующей смежной пары,
5 и 1-- они также вышли из строя,

47
00:02:03,540 --> 00:02:06,960
таким образом, мы поменять их и добавить
1 к прилавку подкачки.

48
00:02:06,960 --> 00:02:08,900
Затем мы рассмотрим 5 и 3.

49
00:02:08,900 --> 00:02:13,830
Они вышли из строя, поэтому мы переставляем
их и добавить 1 к прилавку подкачки.

50
00:02:13,830 --> 00:02:15,550
Затем мы рассмотрим 5 и 6.

51
00:02:15,550 --> 00:02:18,630
Они в порядке, так что мы на самом деле не
нужно поменять что-нибудь в этот раз.

52
00:02:18,630 --> 00:02:20,250
Затем мы рассмотрим 6 и 4.

53
00:02:20,250 --> 00:02:24,920
Они также не в порядке, таким образом, мы поменять
их и добавить 1 к прилавку подкачки.

54
00:02:24,920 --> 00:02:26,230
>> Теперь обратите внимание, что произошло.

55
00:02:26,230 --> 00:02:29,514
Мы переехали 6 весь путь до конца.

56
00:02:29,514 --> 00:02:32,180
Таким образом, в выборе рода, если у Вас есть
видно, что видео, то, что мы делали, было

57
00:02:32,180 --> 00:02:35,290
мы закончили перемещение
маленькие элементы здания

58
00:02:35,290 --> 00:02:39,640
отсортированный массив по существу из
слева направо, от меньшего к большему.

59
00:02:39,640 --> 00:02:43,200
В случае пузырьковой сортировки, если мы
после этого конкретного алгоритма,

60
00:02:43,200 --> 00:02:46,720
мы на самом деле собираетесь строить
отсортированный массив справа

61
00:02:46,720 --> 00:02:49,100
налево, от большего к меньшему.

62
00:02:49,100 --> 00:02:53,840
Мы эффективно пропускают 6,
Наибольшее значение, весь путь до конца.

63
00:02:53,840 --> 00:02:56,165
>> И таким образом мы можем объявить сегодня
что это сортируется,

64
00:02:56,165 --> 00:02:59,130
и в будущем iterations--
переживает массива again--

65
00:02:59,130 --> 00:03:01,280
мы не должны рассматривать 6 больше.

66
00:03:01,280 --> 00:03:03,850
У нас есть только рассмотреть
неотсортированной элементы

67
00:03:03,850 --> 00:03:06,299
когда мы смотрим на соседних пар.

68
00:03:06,299 --> 00:03:08,340
Таким образом, мы закончили один
пройти через пузырьковой сортировки.

69
00:03:08,340 --> 00:03:11,941
Так что теперь мы вернемся к вопросу,
повторять, пока счетчик замены не равно 0.

70
00:03:11,941 --> 00:03:13,690
Ну счетчик подкачки
4, так что мы собираемся

71
00:03:13,690 --> 00:03:15,410
чтобы повторять этот процесс снова.

72
00:03:15,410 --> 00:03:19,180
>> Мы собираемся, чтобы сбросить счетчик подкачки
0, и смотреть на каждой смежной пары.

73
00:03:19,180 --> 00:03:21,890
Итак, мы начинаем с 2 и 1-- они
в порядке, так что мы обменять их

74
00:03:21,890 --> 00:03:23,620
и мы добавляем 1 к прилавку подкачки.

75
00:03:23,620 --> 00:03:25,490
2 и 3, они в порядке.

76
00:03:25,490 --> 00:03:27,060
Нам не нужно ничего делать.

77
00:03:27,060 --> 00:03:28,420
3 и 5 в порядке.

78
00:03:28,420 --> 00:03:30,150
Нам не нужно, чтобы сделать что-нибудь там.

79
00:03:30,150 --> 00:03:32,515
>> 5 и 4, они находятся вне
порядка, и поэтому мы

80
00:03:32,515 --> 00:03:35,130
нужно поменять их и добавить
1 к прилавку подкачки.

81
00:03:35,130 --> 00:03:38,880
А теперь мы переехали 5,
второй по величине элемент,

82
00:03:38,880 --> 00:03:40,920
к концу несортированных части.

83
00:03:40,920 --> 00:03:44,360
Так что теперь мы можем назвать, что
часть отсортированной части.

84
00:03:44,360 --> 00:03:47,180
>> Теперь вы глядя на
Экран и, вероятно, может сказать,

85
00:03:47,180 --> 00:03:50,130
а я могу, что массив
отсортировано прямо сейчас.

86
00:03:50,130 --> 00:03:51,820
Но мы не можем доказать, что еще.

87
00:03:51,820 --> 00:03:54,359
Мы не имеем гарантию
что это сортируется.

88
00:03:54,359 --> 00:03:56,900
Но это, где своп
Счетчик собирается вступить в игру.

89
00:03:56,900 --> 00:03:59,060
>> Таким образом, мы завершили проход.

90
00:03:59,060 --> 00:04:00,357
Счетчик своп 2.

91
00:04:00,357 --> 00:04:02,190
Так что мы собираемся повторить
этот процесс снова,

92
00:04:02,190 --> 00:04:04,290
повторять, пока счетчик замены не равно 0.

93
00:04:04,290 --> 00:04:05,550
Сброс счетчика подкачки 0.

94
00:04:05,550 --> 00:04:06,820
Таким образом, мы сбросить его.

95
00:04:06,820 --> 00:04:09,810
>> Теперь посмотрим на каждой смежной пары.

96
00:04:09,810 --> 00:04:11,880
Это в порядке, 1 и 2.

97
00:04:11,880 --> 00:04:13,590
2 и 3 в порядке.

98
00:04:13,590 --> 00:04:15,010
3 и 4 находятся в порядке.

99
00:04:15,010 --> 00:04:19,250
Таким образом, на данный момент, обратите внимание, мы завершили
глядя на каждого соседней пары,

100
00:04:19,250 --> 00:04:22,530
но счетчик своп по-прежнему 0.

101
00:04:22,530 --> 00:04:25,520
>> Если мы не придется переключаться
любые элементы, то они

102
00:04:25,520 --> 00:04:28,340
должны быть в порядке, от
Достоинство этого процесса.

103
00:04:28,340 --> 00:04:32,000
И так что эффективность сортов,
что мы любим компьютерные ученые,

104
00:04:32,000 --> 00:04:35,560
Теперь мы можем объявить
весь массив должен

105
00:04:35,560 --> 00:04:38,160
быть отсортированы, потому что мы не сделали
есть, чтобы поменять какие-либо элементы.

106
00:04:38,160 --> 00:04:40,380
Это очень приятно.

107
00:04:40,380 --> 00:04:43,260
>> Так что в худшем случае
Сценарий с пузырьковой сортировки?

108
00:04:43,260 --> 00:04:46,240
В худшем случае массив
В полностью обратном порядке,

109
00:04:46,240 --> 00:04:49,870
и поэтому мы должны друг пузыря
крупных элементов всего

110
00:04:49,870 --> 00:04:51,780
путь через массив.

111
00:04:51,780 --> 00:04:55,350
И мы эффективно также должны
пузырь все маленькие элементы обратно

112
00:04:55,350 --> 00:04:57,050
весь путь через массив, тоже.

113
00:04:57,050 --> 00:05:01,950
Таким образом, каждый из п элементов должен двигаться
по всем другим п элементов.

114
00:05:01,950 --> 00:05:04,102
Так что это наихудший сценарий.

115
00:05:04,102 --> 00:05:05,810
В лучшем случае
сценарий, хотя это

116
00:05:05,810 --> 00:05:07,880
немного отличается от выбора рода.

117
00:05:07,880 --> 00:05:10,040
Массив уже
отсортировано когда мы идем в.

118
00:05:10,040 --> 00:05:12,550
Мы не должны делать какие-либо
свопы на первом проходе.

119
00:05:12,550 --> 00:05:14,940
Таким образом, мы, возможно, придется искать
в меньшем количестве элементов, правильно?

120
00:05:14,940 --> 00:05:18,580
Мы не должны повторить это
обрабатывать несколько раз.

121
00:05:18,580 --> 00:05:19,540
>> Так что это значит?

122
00:05:19,540 --> 00:05:22,390
Так что в худшем случае
для пузырьковой сортировки, и то, что

123
00:05:22,390 --> 00:05:25,330
лучший сценарий для пузырьковой сортировки?

124
00:05:25,330 --> 00:05:27,770
Вы догадались это?

125
00:05:27,770 --> 00:05:32,420
В худшем случае вам придется повторять
по всем п элементов п раз.

126
00:05:32,420 --> 00:05:34,220
Таким образом, в худшем случае будет н в квадрате.

127
00:05:34,220 --> 00:05:36,550
>> Если массив прекрасно
отсортированный хотя, вы только

128
00:05:36,550 --> 00:05:38,580
должны смотреть друг на
элементов сразу.

129
00:05:38,580 --> 00:05:42,670
И если счетчик своп по-прежнему 0,
Вы можете сказать, что это массив отсортирован.

130
00:05:42,670 --> 00:05:45,780
И так, в лучшем случае, это
на самом деле лучше, чем выбор

131
00:05:45,780 --> 00:05:49,230
sort-- это омега п.

132
00:05:49,230 --> 00:05:50,270
>> Я Дуг Ллойд.

133
00:05:50,270 --> 00:05:52,140
Это CS50.

134
00:05:52,140 --> 00:05:54,382