1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [Пузырьковой сортировки]

2
00:00:02,840 --> 00:00:04,560
[JACKSON Steinkamp HARVARD UNIVERSITY]

3
00:00:04,560 --> 00:00:07,500
[Это CS50. CS50TV]

4
00:00:08,000 --> 00:00:11,730
Bubble Сортировка пример алгоритма сортировки -

5
00:00:11,730 --> 00:00:14,460
то есть, порядок сортировки набор элементов в

6
00:00:14,460 --> 00:00:15,840
возрастанию или по убыванию.

7
00:00:15,840 --> 00:00:18,710
Например, если вы хотите отсортировать массив, состоящий из чисел

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], правильное применение пузырьковой сортировки вернется

9
00:00:23,060 --> 00:00:26,260
упорядоченный массив [2, 3, 5, 9] в порядке возрастания.

10
00:00:26,260 --> 00:00:28,850
Теперь, я собираюсь объяснить, в псевдокоде, как работает алгоритм.

11
00:00:28,850 --> 00:00:34,000
>> Скажем, мы сортировка список из 5 чисел - 3, 2, 9, 6 и 5.

12
00:00:34,000 --> 00:00:37,650
Алгоритм начинается, глядя на первые два элемента, 3 и 2,

13
00:00:37,650 --> 00:00:40,850
и проверки, если они вышли из строя по отношению друг к другу.

14
00:00:40,850 --> 00:00:43,150
Они - 3 больше, чем 2.

15
00:00:43,150 --> 00:00:45,190
Чтобы быть в порядке возрастания, они должны быть наоборот.

16
00:00:45,190 --> 00:00:46,610
Таким образом, мы поменять их местами.

17
00:00:46,610 --> 00:00:49,760
Теперь список выглядит следующим образом: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Далее мы посмотрим на второй и третий элементы, 3 и 9.

19
00:00:52,450 --> 00:00:55,770
Они в правильном порядке относительно друг друга.

20
00:00:55,770 --> 00:00:58,800
То есть, 3 меньше, чем 9, так что алгоритм не поменять их местами.

21
00:00:58,800 --> 00:01:01,900
Далее, мы смотрим на 9 и 6. Они вышли из строя.

22
00:01:01,900 --> 00:01:04,260
>> Итак, нам нужно, чтобы поменять их местами, потому что 9 больше, чем 6.

23
00:01:04,260 --> 00:01:08,840
Наконец, мы посмотрим на последние два целых числа, 9 и 5.

24
00:01:08,840 --> 00:01:10,850
Они вышли из строя, поэтому они должны быть заменены.

25
00:01:10,850 --> 00:01:13,360
После первого полного прохода по списку,

26
00:01:13,360 --> 00:01:17,140
это выглядит так: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Не плохо. Это почти отсортирован.

28
00:01:19,690 --> 00:01:22,450
Но нам нужно запустить через список еще раз, чтобы получить его полностью отсортирован.

29
00:01:22,450 --> 00:01:29,250
Два меньше, чем 3, поэтому мы не поменять их местами.

30
00:01:29,250 --> 00:01:31,700
>> Три составляет менее 6, так что мы не поменять их местами.

31
00:01:31,700 --> 00:01:35,500
Шесть превышает 5. Мы поменялись местами.

32
00:01:35,500 --> 00:01:38,460
Шесть меньше, чем 9. Мы не поменять.

33
00:01:38,460 --> 00:01:42,170
После второй проход, она выглядит следующим образом: [2, 3, 5, 6, 9]. Perfect.

34
00:01:42,170 --> 00:01:44,680
Теперь, давайте запишем его в псевдокоде.

35
00:01:44,680 --> 00:01:48,450
В принципе, для каждого элемента в списке, мы должны смотреть на это

36
00:01:48,450 --> 00:01:50,060
и элемент непосредственно в своем праве.

37
00:01:50,060 --> 00:01:53,420
Если они не в порядке относительно друг друга - то есть, если элемент слева

38
00:01:53,420 --> 00:01:56,810
больше, чем тот, на правом - мы должны поменять местами два элемента.

39
00:01:56,810 --> 00:02:01,270
>> Мы делаем это для каждого элемента списка, и мы сделали один проход.

40
00:02:01,270 --> 00:02:05,160
Теперь мы просто должны сделать сквозной достаточное количество раз, чтобы убедиться, что список

41
00:02:05,160 --> 00:02:06,480
полностью, правильно сортируются.

42
00:02:06,480 --> 00:02:08,889
Но сколько раз мы должны пройти через список

43
00:02:08,889 --> 00:02:10,400
гарантировать, что мы сделали?

44
00:02:10,400 --> 00:02:14,730
Ну, худшем случае, если мы имеем совершенно обратную списка.

45
00:02:14,730 --> 00:02:17,840
Тогда она принимает ряд пройти проходные равно числу

46
00:02:17,840 --> 00:02:19,730
элементов N-1.

47
00:02:19,730 --> 00:02:24,720
Если это не имеет смысла, интуитивно, думаю простой случай - список [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> Это будет взять один проход, чтобы отсортировать правильно.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - В худшем случае в том, что с 3 элементы сортируются в обратном направлении,

50
00:02:33,060 --> 00:02:34,830
он собирается взять 2 итераций для сортировки.

51
00:02:34,830 --> 00:02:37,980
После одной итерации, это [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
Второй дает упорядоченный массив [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Таким образом, вы знаете, никогда не должны идти через массив, в общем,

54
00:02:43,350 --> 00:02:46,790
больше, чем N-1 раз, где п-число элементов в массиве.

55
00:02:47,090 --> 00:02:50,470
Это называется Bubble Сортировка потому, что крупнейшие элементы, как правило, «пузырь вверх"

56
00:02:50,470 --> 00:02:51,950
справа довольно быстро.

57
00:02:51,950 --> 00:02:53,980
На самом деле, этот алгоритм имеет очень интересное поведение.

58
00:02:53,980 --> 00:02:57,410
>> После т итераций через весь массив,

59
00:02:57,410 --> 00:02:59,000
правые элементы м гарантировано

60
00:02:59,000 --> 00:03:01,000
должны быть отсортированы в их правильном месте.

61
00:03:01,000 --> 00:03:02,280
Если вы хотите в этом убедиться,

62
00:03:02,280 --> 00:03:05,500
мы можем попробовать его на совершенно обратную список [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
После одного прохода через весь список,

64
00:03:08,220 --> 00:03:09,220
[Звук письменной форме]

65
00:03:09,220 --> 00:03:18,790
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]

66
00:03:18,790 --> 00:03:21,250
правый элемент 9 находится в надлежащем месте.

67
00:03:21,250 --> 00:03:24,760
После второй проход, 6 будет иметь "пропускают вверх", чтобы

68
00:03:24,760 --> 00:03:26,220
вторую справа место.

69
00:03:26,220 --> 00:03:28,840
Эти два элемента справа - 6 и 9 - будет в их правильных местах

70
00:03:28,840 --> 00:03:30,580
После первых двух проход проходные.

71
00:03:30,580 --> 00:03:32,590
>> Итак, как мы можем использовать это, чтобы оптимизировать алгоритм?

72
00:03:32,590 --> 00:03:34,850
Ну, а после одной итерации по массиву

73
00:03:34,850 --> 00:03:37,690
Мы на самом деле не нужно проверять правый элемент

74
00:03:37,690 --> 00:03:39,200
потому что мы знаем, что это отсортированы.

75
00:03:39,200 --> 00:03:43,050
После двух итераций, мы знаем наверняка, самая правая из двух элементов на месте.

76
00:03:43,050 --> 00:03:48,260
Так, в общем, после к итераций полный массив,

77
00:03:48,260 --> 00:03:51,550
Проверка последнего к элементов является избыточным, так как мы знаем,

78
00:03:51,550 --> 00:03:52,360
они в нужном месте уже.

79
00:03:52,360 --> 00:03:54,870
>> Так что если вы сортировки массива из п элементов,

80
00:03:54,870 --> 00:03:57,870
на первой итерации - вы будете иметь, чтобы отсортировать все элементы - первые п-0.

81
00:03:57,870 --> 00:04:04,170
На второй итерации, вы должны смотреть на все элементы, кроме последнего -

82
00:04:04,170 --> 00:04:07,090
первые N-1.

83
00:04:07,090 --> 00:04:10,520
Другая оптимизация может быть, чтобы проверить, если список уже отсортирован

84
00:04:10,520 --> 00:04:11,710
после каждой итерации.

85
00:04:11,710 --> 00:04:13,900
Если он уже отсортированы, мы не должны сделать больше итераций

86
00:04:13,900 --> 00:04:15,310
по списку.

87
00:04:15,310 --> 00:04:16,220
Как мы можем это сделать?

88
00:04:16,220 --> 00:04:19,360
Ну, если мы не делаем никаких свопов на проходной части списка,

89
00:04:19,360 --> 00:04:22,350
ясно, что этот список был уже отсортирован, потому что мы не менять ничего.

90
00:04:22,350 --> 00:04:24,160
Таким образом, мы, безусловно, не должны сортировать снова.

91
00:04:24,160 --> 00:04:27,960
>> Может быть, вы могли бы инициализировать флаг переменная называется "Не отсортировано к

92
00:04:27,960 --> 00:04:30,990
ложными и изменить его на истинный если у вас есть, чтобы обменять любые элементы на

93
00:04:30,990 --> 00:04:32,290
одна итерация по массиву.

94
00:04:32,290 --> 00:04:35,350
Или аналогично, сделать встречное подсчитать, сколько свопов вы делаете

95
00:04:35,350 --> 00:04:37,040
на любой итерации.

96
00:04:37,040 --> 00:04:40,040
В конце итерации, если не поменять любой из элементов,

97
00:04:40,040 --> 00:04:41,780
Вы знаете, в список уже отсортирован, и все готово.

98
00:04:41,780 --> 00:04:44,090
Bubble Сортировка, как и другие алгоритмы сортировки, может быть

99
00:04:44,090 --> 00:04:46,960
переделаны, чтобы работать для любых элементов, которые имеют заказа методом.

100
00:04:46,960 --> 00:04:50,610
>> То есть, при наличии двух элементов у вас есть способ сказать, если первая

101
00:04:50,610 --> 00:04:53,770
больше, равно или меньше, чем второй.

102
00:04:53,770 --> 00:04:56,870
Например, вы можете отсортировать буквы алфавита, сказав,

103
00:04:56,870 --> 00:05:00,520
, что <B, B <C, и т.д.

104
00:05:00,520 --> 00:05:03,830
Или вы можете отсортировать дни недели, где воскресенье считается менее понедельника

105
00:05:03,830 --> 00:05:05,110
что меньше, чем во вторник.

106
00:05:05,110 --> 00:05:09,630
>> Bubble Сортировка отнюдь не очень эффективны или быстрый алгоритм сортировки.

107
00:05:09,630 --> 00:05:12,370
В наихудшем случае время работы от батарей Big O н ²

108
00:05:12,370 --> 00:05:14,810
потому что вы должны сделать п итераций по списку

109
00:05:14,810 --> 00:05:18,430
проверка всех п элементов, каждый проход, пхп = п ².

110
00:05:18,430 --> 00:05:22,730
Это время выполнения означает, что как число элементов, вы сортировке увеличивается,

111
00:05:22,730 --> 00:05:24,330
время выполнения увеличивается квадратично.

112
00:05:24,330 --> 00:05:27,330
>> Но если эффективность не является главной заботой вашей программы

113
00:05:27,330 --> 00:05:29,550
или если вы только сортировка небольшого числа элементов,

114
00:05:29,550 --> 00:05:31,660
Вы могли бы найти Bubble Сортировка полезно, потому что

115
00:05:31,660 --> 00:05:33,360
это один из простейших алгоритмов сортировки, чтобы понять

116
00:05:33,360 --> 00:05:34,250
и код.

117
00:05:34,250 --> 00:05:37,270
Это также отличный способ получить опыт работы с переводом теоретических

118
00:05:37,270 --> 00:05:40,220
алгоритм в реальном коде функционирования.

119
00:05:40,220 --> 00:05:43,000
Ну, вот и пузырьковой сортировки для вас. Спасибо за просмотр.

120
00:05:43,000 --> 00:05:44,000
CS50.TV