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