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
1. 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