[Powered by Google Translate] [Сортування злиттям]
[Rob Боуден - Гарвардський університет]
[Це CS50. - CS50.TV]
Давайте поговоримо про сортування злиттям.
До цих пір ви бачили бульбашкового сортування, сортування вставкою, і вибір роду.
Хоча я начебто хвилі моєї рукою на те, що я маю на увазі краще,
сортування злиттям зазвичай працює краще, ніж будь-який з цих 3 видів.
>> Але перш ніж говорити про роду злиття, давайте поговоримо про злиття 2 відсортованих списків.
Ми називаємо процес займає 2 відсортованих списків, як ці,
і одним відсортований список з них - злиття списків.
Як ми можемо це зробити?
Ну, одна ідея, це просто дотримуватися одного списку в кінець іншого списку
а потім відсортувати отриманий список.
>> Хоча це працює, це багато непотрібної роботи.
Ми можемо зробити це швидше, ніж просто сортування.
Зверніть увагу, що один невірний ідея, щоб просто взяти змінний чашки з кожного списку.
Хоча це може здатися, що роботи на першій,
Роблячи це, ми в кінцевому підсумку з 4, 8, 15, 23, 16 - зверніть увагу, що 16 і 23 є недоречними.
Це тому, що 2 елементи, які повинні з'явитися послідовно в об'єднаному списку
знаходяться в тому ж початковий список.
І 15 і 16 знаходяться в списку ліворуч.
Хитрість полягає в тому, щоб скористатися тим, що в обох списках вже відсортовані.
Це означає, що якщо ми просто подивимося на перші елементи обох списків -
Тут, 4 і 8 - один із них повинен бути першим елементом об'єднаного списку.
Ну, навіщо це?
Обидва ці списки вже відсортовані,
і так 4 або 8 повинне бути найменшим елементом, коли ми об'єднаємо 2 списку.
У цьому випадку є найменшим 4,
так що ми можемо взяти з 4 і зробити його першим елементом нашого об'єднаного списку.
Зараз ми продовжуємо злиття залишилися 3 елементи з першого списку
і 4 елементи другого списку.
>> Знову ж таки, ми тільки повинні дивитися на перший елемент обох списках.
Менше з 2 повинні бути другим елементом нашого об'єднаного списку.
На цей раз, між 8 і 15 є найменшим 8, і так ми вставляємо, що
в якості другого елементу нашої відсортований список.
Ми можемо продовжувати порівнювати перші елементи обох списків
і видалення менше з 2.
Порівняння 15 і 23, 15 і менше, так от наш третій елемент.
Порівнюючи тепер 16 і 23, 16 менше.
Так ось четвертий елемент.
>> Зверніть увагу, що 2 елементи прийшли з того ж списку в ряд.
Саме тому об'єднаний список не може просто альтернативний елементів з 2 списку.
Порівняння 50 і 23, 23 буде менше, тому ми вибираємо це.
Між 50 і 42, 42 менше.
Між 50 і 108, 50 менше.
І, нарешті, ми просто повинні 108, тому вона повинна йти в кінці нашого списку.
Зверніть увагу, що у нас є хороші, відсортований список.
Кожен раз, коли ми порівнювали перші 2 елемента з 2 списки
Ми змогли визначити наступний елемент об'єднаного списку.
Це означає, що якщо остаточний список містить номери п, де п тут 8,
Потім нам потрібно не більше п порівнянь, щоб отримати всі ці цифри в правильному місці.
Такий алгоритм називається працювати в лінійному часу,
але не турбуйтеся про це тут.
>> Використовуючи наш алгоритм злиття, ми можемо зробити швидкий алгоритм сортування злиттям.
Отже, давайте скинути наші списки.
Є 2 великі кроки в процесі сортування злиттям.
По-перше, безперервно розділити список чашки навпіл
до тих пір поки у нас є купа списків тільки з 1 чашкою в них.
Не хвилюйтеся, якщо список містить непарне число
і ви не можете зробити ідеально чистий зріз між ними.
Просто довільно вибрати, який список, включивши додаткову чашку дюйма
Отже, давайте розділити ці списки.
Тепер у нас є 2 списку.
Тепер у нас є 4 списків.
>> І тепер у нас є 8 списків з однієї чашки в кожному списку.
Так ось воно що на кроці 1.
Для кроці 2, ми неодноразово злиття пари списків з використанням алгоритму злиття ми дізналися раніше.
Злиття 108 і 15, ми в кінцевому підсумку зі списком 15, 108.
Злиття 50 і 4, ми в кінцевому підсумку з 4, 50.
Злиття 8 і 42, ми в кінцевому підсумку з 8, 42.
І злиття 23 і 16, ми в кінцевому підсумку з 16, 23.
Тепер всі наші списки розміру 2.
Зверніть увагу, що кожний з 4 списки сортуються.
>> Таким чином, ми можемо почати злиття пари списки.
Злиття 15 і 108, а 4 і 50 -
спочатку взяти 4, то 15, то 50, то 108.
Злиття 8, 42 і 16, 23,
Візьмемо спочатку 8, потім 16, потім 23, потім 42.
Так що тепер у нас є всього 2 списки розмір 4, кожна з яких сортується.
Отже, тепер ми об'єднати ці 2 списку.
Спочатку ми беремо 4.
Потім ми беремо 8.
Потім ми беремо 15 і 16, то 23, то 42, то 50, то 108.
І ми зробили.
Тепер у нас є відсортований список.
Так, як швидко було це насправді?
З технічної точки зору, злиття сортування O (п § п),
в той час як всі бульбашкового сортування, сортування вставкою, і вибір роду є O (N ²).
У самому справі, як ви дізнаєтеся найближчим часом, ви не зможете придумати свого роду
, Що працює краще, ніж O (п § п) в загальному випадку.
Знову ж таки, не турбуйтеся про це великому позначення O, якщо ви його ще не бачила.
>> Просто знаю, що це означає, якщо ми хочемо, щоб відсортувати дійсно великий список
бульбашкова сортування, сортування вставкою, і вибір роду потенційно можуть приймати
значно довше, ніж сортування злиттям.
Це не означає, що сортування злиттям буде швидше для всіх списків
або навіть для будь-якого єдиний список під певний розмір.
Наприклад, сортування вставкою може бути найшвидший вид для всіх списків менше, ніж 5 елементів.
На практиці, сортування злиттям, як правило, швидше для списків як малі, як 50 елементів.
>> Але ця додаткова швидкість не приходить без ціни.
На відміну від інших сортів, які приймають список і змінити список на місці
поки ми не отримаємо відсортований список, сортування злиттям необхідно додаткове місце
об'єднати 2 списку разом.
Ми не можемо відразу використовувати списки, які зливаються для зберігання об'єднаного списку
так як ми можемо змінити елементи, які ще мають бути об'єднані.
Це простір є трохи ціни, але це звичайно не є необгрунтованим.
І ось саме для сортування злиттям.
>> Мене звуть Боб Боуден, і це CS50.
[CS50.TV]
- І вибір роду.
[Сміється]
Ох, треба прийняти це занадто, тому що я перейшов, як я уявляв його.
Список зліва. Це була помилка.
[Обмовимося] я облажався -
[Сміється]
Я не знаю, що -