[Грає музика] 

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

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

Ми збираємося йти один елемент, у той час, і будувати і тому перше, що ми бачимо, це масив один елемент. І за визначенням, один елемент масиву сортується. 

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

Отже, ще раз, ось наш Весь масив несортовані, всі елементи відображаються в червоному кольорі. І давайте слідувати кроки нашої псевдокоді. Перше, що ми робимо, є ми називаємо Перший елемент масиву, відсортувати. Так що ми просто збираюся говорити п'ять, ви тепер сортуються. 

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

Отже, як ви бачите, ми тільки поки подивився на двох елементів масиву. Ми не дивилися на відпочинок на всіх, але ми отримав ці два елементи упорядковано Спосіб механізму перемикання. 

Таким чином, ми повторюємо процес знову. Подивіться на наступний несортоване елемент, що одна. Давайте вважати, що в сторону на секунду, перекласти все закінчилося, і покласти один де вона повинна йти. 

Знову ж, досі, ми тільки коли-небудь подивився на один, два і п'ять. Ми не знаємо, що ще йде, але ми упорядковано ці три елементи. 

Наступна несортоване елемент зо три, так що ми будемо встановлювати його в сторону. Ми поступово зміщувати те, що ми потрібно, який, на цей раз це ще не все, як і в попередньому два випадки, це просто п'ять. І тоді ми будемо дотримуватися три в, між двома і п'ятьма. 

Шість є наступним несортоване елемент до масиву. І справді шести більше п'яти, так ми навіть не потрібно робити які-небудь заміни. Ми можемо просто лавірувати шостій право на кінець відсортованого частини. 

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

Так що в гіршому випадку Сценарій з вставки роду? У гіршому разі, масив у зворотному порядку. Ви повинні перейти кожного з п елементів до н позицій, кожен раз, коли ми зробити вставку. Це багато змінюється. 

У кращому випадку, Масив прекрасно відсортовані. І ніби як те, що відбулося з п'ятьма і шістьма у прикладі, де ми могли б просто лавірувати її на без того, щоб зробити будь-який зрушення, ми, по суті, що робити. 

Якщо уявити, що наші Масив був один через шість, ми б почати з заявивши, один сортується. Два приходить після одного, щоб ми могли просто кажуть, добре, добре один і два сортуються. Три приходить після двох, так, добре, один і два, і три сортуються. 

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

Якщо масив прекрасно сортувати, все, що ми повинні зробити, це подивитися на кожного елемента один раз, а потім ми зробили. Таким чином, в кращому випадку, це омега п. 

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