1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [BUBBLE SORT]

2
00:00:02,840 --> 00:00:04,560
[JACKSON STEINKAMP Харвардския университет]

3
00:00:04,560 --> 00:00:07,500
[Това е CS50. CS50TV]

4
00:00:08,000 --> 00:00:11,730
Bubble Sort е пример за алгоритъм за сортиране -

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], правилното прилагане на Bubble Sort ще се върне на

9
00:00:23,060 --> 00:00:26,260
сортират масив [2, 3, 5, 9] във възходящ ред.

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

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
Сега, нека да го напиша в pseudocode.

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] - най-лошия случай е, че с три елемента, сортирани назад,

50
00:02:33,060 --> 00:02:34,830
ще отнеме две повторения за сортиране.

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 пъти, където N е броя на елементите на масива.

55
00:02:47,090 --> 00:02:50,470
Тя се нарича Bubble Sort, защото най-големите елементи не са "балон"

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
на първата итерация - ще трябва да сортирате всички елементи - първият N-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
че <б, б <в и др.

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 Sort никакъв случай не е много ефикасен и бърз алгоритъм за сортиране.

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

108
00:05:12,370 --> 00:05:14,810
защото трябва да се направи н повторения чрез списък

109
00:05:14,810 --> 00:05:18,430
проверка на всички н елементи всяко преминаване през nxn = N ².

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

111
00:05:22,730 --> 00:05:24,330
време на изпълнение се увеличава quadratically.

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 Sort полезна, защото

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
Е, това е Bubble Sort за вас. Благодаря за гледане.

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