ДАГ Lloyd: Так в CS50 ми дізналися про різноманітність сортування і пошуку алгоритми. І іноді це може бути трохи складніше тримати трек, який алгоритм робить. Ми дійсно тільки знежирене поверхня теж Є багато інших пошук і алгоритми сортування. Таким чином, в цьому відео давайте просто взяти кілька хвилин щоб спробувати відігнати кожен алгоритм до його основних елементів так що ви можете пам'ятати, найбільш важлива інформація про них і бути в змозі сформулювати відмінності, якщо це необхідно. 

Перший вибір роду. Основна ідея вибору роду це знайти найменший елемент несортоване в масиві і поміняти його з в першу чергу несортоване елемент цього масиву. Ми сказали, що в гіршому випадку запустити час, що був н квадраті. І якщо ви хочете, щоб згадати, чому, взяти Подивіться на вибір роду відео. Час роботи кращому випадку також п квадраті. 

Пузир роду, ідея, що один, щоб поміняти сусідні пари. Так що це ключ, який допомагає вам запам'ятати різницю тут. Вибір роду є, досі, знайти smallest-- міхур Сортувати поза поміняти сусідні пари. Ми поміняти сусідні пари елементів, якщо вони вийшли з ладу, який ефективно бульбашки великі елементи права, і в той же час вона також починає для переміщення дрібних елементів вліво. Час виконання випадок найгіршого випадку міхура сортування п квадраті. Час роботи кращому випадку міхура сортування п. Тому що в цій ситуації ми не actually-- ми, можливо, не потрібно робити які-небудь свопи на всіх. У нас є тільки зробити один пройти через всі п елементів. 

У вставки роду, то Основна ідея тут змінюється. Це ключове слово для вставки роду. Ми збираємося вийти один раз через масив зліва направо. І, як ми робимо, ми збирається перенести елементи ми вже бачили, щоб звільнити місце для дрібні, що потрібно, щоб відповідати десь тому в цій відсортовано частини. Так ми будуємо відсортований масив одним елемент, у той час, зліва направо, і ми переходимо речі, щоб зробити кімнату. Найгірший час пробіг вставка сортування п квадраті. Час кращий варіант запуску є н. 

Злиття sort-- ключового слова тут розділення і злиття. Ми розділили повний спектр Чи це шість елементів, восьми елементів, 10000 elements-- ми розділили його скоротилася вдвічі, удвічі, удвічі, поки у нас під масив н однієї масивів елементів. Набір N Один масивів елементів. Отже, ми почали з одного Масив +1000 елемент, і ми дістатися до точки, де ми є 1000 масивів одноелементні. Тоді ми починаємо об'єднати ці суб масиви разом в правильному порядку. Таким чином, ми прийняти два масиви одноелементні і створити масив з двох елементів. Візьмемо два масиви двох елементів і створити масив з чотирьох елементів і так далі, і так далі, поки ми не знову відновлений один масив п елементів. 

Найгірший час пробіг сортування злиттям п раз увійти н. У нас є п елементів, але цей процес рекомбінуючих приймає увійти п кроків, щоб отримати повернутися до повної масиву. У кращому випадку час виконання також п журналу п тому що цей процес не має великого піклуватися, чи був масив сортування або не починати. Процес той же, є немає спосіб коротких речей вимикачів. Так п п увійти в гіршому випадку, п п увійти в кращому випадку. 

Ми говорили про двох алгоритми пошуку. Так лінійний пошук про ітерації. Перейдемо через масив один раз, зліва направо, намагаючись знайти номер що ми шукаємо. Час найгірший запустити великий виведення п. Це може зайняти нам ітерації по кожній елемента щоб знайти елемент ми шукаємо для, або в останній позиції, або не на всіх. Але ми не можемо підтвердити, що до тих пір, ми дивилися на все. м кращому випадку, ми відразу знайти. Кращий випадку час пробіг лінійний пошук омега 1. 

Нарешті, було бінарний пошук, який вимагає асорті масив. Пам'ятайте, що це дуже важливим фактором при роботі з бінарного пошуку. Це є необхідною умовою для допомоги it-- масив, що ви шукаєте через повинні бути відсортовані. В іншому випадку, ключове слово це розділяй і володарюй. Спліт масив навпіл і усунення половина елементів кожен раз, як ви пройти через. Через це розділяй і володарюй і поділ речей у половині підходу, в гіршому випадку час виконання бінарних пошук увійти н, який, по суті краще, ніж лінійний пошук у п. Час кращому випадку працювати як і раніше один. 

Ми могли б відразу ж знайти Перший раз ми робимо поділ, але, знову, пам'ятайте, що хоча двійковий пошук значно краще, ніж лінійний пошук в силу того, журнал N в порівнянні з п, Ви, можливо, доведеться пройти через роботу сортування свій масив першою, може зробити його менш ефективним в залежності на розмір ітерації відсортовані. 

Я Дуг Ллойд, це CS50.