1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Сортування злиттям]

2
00:00:02,000 --> 00:00:04,000
[Rob Боуден - Гарвардський університет]

3
00:00:04,000 --> 00:00:07,000
[Це CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Давайте поговоримо про сортування злиттям.

5
00:00:09,000 --> 00:00:14,000
До цих пір ви бачили бульбашкового сортування, сортування вставкою, і вибір роду.

6
00:00:14,000 --> 00:00:17,000
Хоча я начебто хвилі моєї рукою на те, що я маю на увазі краще,

7
00:00:17,000 --> 00:00:21,000
сортування злиттям зазвичай працює краще, ніж будь-який з цих 3 видів.

8
00:00:22,000 --> 00:00:27,000
>> Але перш ніж говорити про роду злиття, давайте поговоримо про злиття 2 відсортованих списків.

9
00:00:27,000 --> 00:00:31,000
Ми називаємо процес займає 2 відсортованих списків, як ці,

10
00:00:31,000 --> 00:00:35,000
і одним відсортований список з них - злиття списків.

11
00:00:35,000 --> 00:00:37,750
Як ми можемо це зробити?

12
00:00:37,750 --> 00:00:41,290
Ну, одна ідея, це просто дотримуватися одного списку в кінець іншого списку

13
00:00:41,290 --> 00:00:43,830
а потім відсортувати отриманий список.

14
00:00:43,830 --> 00:00:47,220
>> Хоча це працює, це багато непотрібної роботи.

15
00:00:47,220 --> 00:00:49,900
Ми можемо зробити це швидше, ніж просто сортування.

16
00:00:49,900 --> 00:00:54,100
Зверніть увагу, що один невірний ідея, щоб просто взяти змінний чашки з кожного списку.

17
00:00:54,100 --> 00:00:56,460
Хоча це може здатися, що роботи на першій,

18
00:00:56,460 --> 00:01:05,760
Роблячи це, ми в кінцевому підсумку з 4, 8, 15, 23, 16 - зверніть увагу, що 16 і 23 є недоречними.

19
00:01:05,760 --> 00:01:09,380
Це тому, що 2 елементи, які повинні з'явитися послідовно в об'єднаному списку

20
00:01:09,380 --> 00:01:11,720
знаходяться в тому ж початковий список.

21
00:01:11,720 --> 00:01:14,850
І 15 і 16 знаходяться в списку ліворуч.

22
00:01:14,850 --> 00:01:19,810
Хитрість полягає в тому, щоб скористатися тим, що в обох списках вже відсортовані.

23
00:01:19,810 --> 00:01:23,320
Це означає, що якщо ми просто подивимося на перші елементи обох списків -

24
00:01:23,320 --> 00:01:29,580
Тут, 4 і 8 - один із них повинен бути першим елементом об'єднаного списку.

25
00:01:29,580 --> 00:01:31,620
Ну, навіщо це?

26
00:01:31,620 --> 00:01:33,520
Обидва ці списки вже відсортовані,

27
00:01:33,520 --> 00:01:38,410
і так 4 або 8 повинне бути найменшим елементом, коли ми об'єднаємо 2 списку.

28
00:01:38,410 --> 00:01:41,770
У цьому випадку є найменшим 4,

29
00:01:41,770 --> 00:01:46,370
так що ми можемо взяти з 4 і зробити його першим елементом нашого об'єднаного списку.

30
00:01:46,370 --> 00:01:50,710
Зараз ми продовжуємо злиття залишилися 3 елементи з першого списку

31
00:01:50,710 --> 00:01:52,920
і 4 елементи другого списку.

32
00:01:52,920 --> 00:01:57,150
>> Знову ж таки, ми тільки повинні дивитися на перший елемент обох списках.

33
00:01:57,150 --> 00:02:01,060
Менше з 2 повинні бути другим елементом нашого об'єднаного списку.

34
00:02:01,060 --> 00:02:05,440
На цей раз, між 8 і 15 є найменшим 8, і так ми вставляємо, що

35
00:02:05,440 --> 00:02:09,240
в якості другого елементу нашої відсортований список.

36
00:02:09,240 --> 00:02:12,180
Ми можемо продовжувати порівнювати перші елементи обох списків

37
00:02:12,180 --> 00:02:14,420
і видалення менше з 2.

38
00:02:14,420 --> 00:02:19,460
Порівняння 15 і 23, 15 і менше, так от наш третій елемент.

39
00:02:21,000 --> 00:02:23,910
Порівнюючи тепер 16 і 23, 16 менше.

40
00:02:23,910 --> 00:02:26,820
Так ось четвертий елемент.

41
00:02:26,820 --> 00:02:30,390
>> Зверніть увагу, що 2 елементи прийшли з того ж списку в ряд.

42
00:02:30,390 --> 00:02:34,400
Саме тому об'єднаний список не може просто альтернативний елементів з 2 списку.

43
00:02:34,400 --> 00:02:40,020
Порівняння 50 і 23, 23 буде менше, тому ми вибираємо це.

44
00:02:40,770 --> 00:02:44,070
Між 50 і 42, 42 менше.

45
00:02:44,070 --> 00:02:48,290
Між 50 і 108, 50 менше.

46
00:02:48,290 --> 00:02:52,330
І, нарешті, ми просто повинні 108, тому вона повинна йти в кінці нашого списку.

47
00:02:53,750 --> 00:02:56,180
Зверніть увагу, що у нас є хороші, відсортований список.

48
00:02:56,180 --> 00:02:59,040
Кожен раз, коли ми порівнювали перші 2 елемента з 2 списки

49
00:02:59,040 --> 00:03:02,730
Ми змогли визначити наступний елемент об'єднаного списку.

50
00:03:02,730 --> 00:03:08,070
Це означає, що якщо остаточний список містить номери п, де п тут 8,

51
00:03:08,070 --> 00:03:12,610
Потім нам потрібно не більше п порівнянь, щоб отримати всі ці цифри в правильному місці.

52
00:03:13,230 --> 00:03:16,230
Такий алгоритм називається працювати в лінійному часу,

53
00:03:16,230 --> 00:03:18,090
але не турбуйтеся про це тут.

54
00:03:18,570 --> 00:03:22,810
>> Використовуючи наш алгоритм злиття, ми можемо зробити швидкий алгоритм сортування злиттям.

55
00:03:22,810 --> 00:03:25,170
Отже, давайте скинути наші списки.

56
00:03:35,210 --> 00:03:37,750
Є 2 великі кроки в процесі сортування злиттям.

57
00:03:37,750 --> 00:03:41,500
По-перше, безперервно розділити список чашки навпіл

58
00:03:41,500 --> 00:03:44,860
до тих пір поки у нас є купа списків тільки з 1 чашкою в них.

59
00:03:44,860 --> 00:03:47,350
Не хвилюйтеся, якщо список містить непарне число

60
00:03:47,350 --> 00:03:49,880
і ви не можете зробити ідеально чистий зріз між ними.

61
00:03:49,880 --> 00:03:53,750
Просто довільно вибрати, який список, включивши додаткову чашку дюйма

62
00:03:53,750 --> 00:03:56,240
Отже, давайте розділити ці списки.

63
00:03:58,140 --> 00:04:01,310
Тепер у нас є 2 списку.

64
00:04:04,120 --> 00:04:06,570
Тепер у нас є 4 списків.

65
00:04:10,350 --> 00:04:13,870
>> І тепер у нас є 8 списків з однієї чашки в кожному списку.

66
00:04:13,870 --> 00:04:16,630
Так ось воно що на кроці 1.

67
00:04:16,630 --> 00:04:22,230
Для кроці 2, ми неодноразово злиття пари списків з використанням алгоритму злиття ми дізналися раніше.

68
00:04:22,230 --> 00:04:29,160
Злиття 108 і 15, ми в кінцевому підсумку зі списком 15, 108.

69
00:04:30,330 --> 00:04:36,250
Злиття 50 і 4, ми в кінцевому підсумку з 4, 50.

70
00:04:36,960 --> 00:04:41,400
Злиття 8 і 42, ми в кінцевому підсумку з 8, 42.

71
00:04:42,790 --> 00:04:48,130
І злиття 23 і 16, ми в кінцевому підсумку з 16, 23.

72
00:04:49,740 --> 00:04:52,450
Тепер всі наші списки розміру 2.

73
00:04:53,020 --> 00:04:56,180
Зверніть увагу, що кожний з 4 списки сортуються.

74
00:04:56,180 --> 00:04:59,160
>> Таким чином, ми можемо почати злиття пари списки.

75
00:04:59,160 --> 00:05:03,240
Злиття 15 і 108, а 4 і 50 -

76
00:05:03,240 --> 00:05:11,170
спочатку взяти 4, то 15, то 50, то 108.

77
00:05:11,170 --> 00:05:15,120
Злиття 8, 42 і 16, 23,

78
00:05:15,120 --> 00:05:22,440
Візьмемо спочатку 8, потім 16, потім 23, потім 42.

79
00:05:22,440 --> 00:05:27,370
Так що тепер у нас є всього 2 списки розмір 4, кожна з яких сортується.

80
00:05:27,370 --> 00:05:30,980
Отже, тепер ми об'єднати ці 2 списку.

81
00:05:30,980 --> 00:05:33,440
Спочатку ми беремо 4.

82
00:05:33,440 --> 00:05:36,580
Потім ми беремо 8.

83
00:05:36,580 --> 00:05:50,700
Потім ми беремо 15 і 16, то 23, то 42, то 50, то 108.

84
00:05:50,700 --> 00:05:52,220
І ми зробили.

85
00:05:52,220 --> 00:05:54,900
Тепер у нас є відсортований список.

86
00:05:54,900 --> 00:05:57,890
Так, як швидко було це насправді?

87
00:05:57,890 --> 00:06:02,000
З технічної точки зору, злиття сортування O (п § п),

88
00:06:02,000 --> 00:06:07,380
в той час як всі бульбашкового сортування, сортування вставкою, і вибір роду є O (N ²).

89
00:06:07,380 --> 00:06:11,120
У самому справі, як ви дізнаєтеся найближчим часом, ви не зможете придумати свого роду

90
00:06:11,120 --> 00:06:14,820
, Що працює краще, ніж O (п § п) в загальному випадку.

91
00:06:14,820 --> 00:06:19,120
Знову ж таки, не турбуйтеся про це великому позначення O, якщо ви його ще не бачила.

92
00:06:19,120 --> 00:06:23,490
>> Просто знаю, що це означає, якщо ми хочемо, щоб відсортувати дійсно великий список

93
00:06:23,490 --> 00:06:26,820
бульбашкова сортування, сортування вставкою, і вибір роду потенційно можуть приймати

94
00:06:26,820 --> 00:06:29,500
значно довше, ніж сортування злиттям.

95
00:06:29,500 --> 00:06:33,210
Це не означає, що сортування злиттям буде швидше для всіх списків

96
00:06:33,210 --> 00:06:36,220
або навіть для будь-якого єдиний список під певний розмір.

97
00:06:36,220 --> 00:06:41,950
Наприклад, сортування вставкою може бути найшвидший вид для всіх списків менше, ніж 5 елементів.

98
00:06:41,950 --> 00:06:47,360
На практиці, сортування злиттям, як правило, швидше для списків як малі, як 50 елементів.

99
00:06:47,360 --> 00:06:51,120
>> Але ця додаткова швидкість не приходить без ціни.

100
00:06:51,120 --> 00:06:54,770
На відміну від інших сортів, які приймають список і змінити список на місці

101
00:06:54,770 --> 00:06:58,740
поки ми не отримаємо відсортований список, сортування злиттям необхідно додаткове місце

102
00:06:58,740 --> 00:07:00,900
об'єднати 2 списку разом.

103
00:07:00,900 --> 00:07:04,690
Ми не можемо відразу використовувати списки, які зливаються для зберігання об'єднаного списку

104
00:07:04,690 --> 00:07:08,880
так як ми можемо змінити елементи, які ще мають бути об'єднані.

105
00:07:08,880 --> 00:07:13,540
Це простір є трохи ціни, але це звичайно не є необгрунтованим.

106
00:07:13,540 --> 00:07:15,330
І ось саме для сортування злиттям.

107
00:07:15,330 --> 00:07:18,490
>> Мене звуть Боб Боуден, і це CS50.

108
00:07:18,490 --> 00:07:20,500
[CS50.TV]

109
00:07:20,500 --> 00:07:24,000
- І вибір роду.

110
00:07:24,000 --> 00:07:25,880
[Сміється]

111
00:07:25,880 --> 00:07:31,480
Ох, треба прийняти це занадто, тому що я перейшов, як я уявляв його.

112
00:07:31,480 --> 00:07:35,680
Список зліва. Це була помилка.

113
00:07:35,680 --> 00:07:39,290
[Обмовимося] я облажався -

114
00:07:39,290 --> 00:07:41,190
[Сміється]

115
00:07:41,190 --> 00:07:44,190
Я не знаю, що -