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