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