[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] - І вибір роду. [Сміється] Ох, треба прийняти це занадто, тому що я перейшов, як я уявляв його. Список зліва. Це була помилка. [Обмовимося] я облажався - [Сміється] Я не знаю, що -