>> [Грає музика]
>> ДАГ Lloyd: Так вставки сортування інший Алгоритм можна використовувати для сортування масиву.
Ідея цього алгоритму це, щоб побудувати свій відсортований масив
в місці, переминаючись елементи з спосіб, як ви йдете, щоб звільнити місце.
Це трохи відрізняється від вибору роду або міхура
роду, наприклад, де ми регулювання місцеположення,
де ми робимо свопи.
>> У цьому випадку те, що ми насправді робите розсувні елементи
більше, з шляху.
Як це алгоритм працювати в псевдокоді?
Ну давайте просто довільно сказати, що Перший елемент масиву сортується.
Ми будуємо її на місці.
>> Ми збираємося йти один елемент, у той час, і будувати і тому перше, що ми бачимо,
це масив один елемент.
І за визначенням, один елемент масиву сортується.
>> Тоді ми будемо повторювати цей процес until-- ми будемо повторювати наступну процедуру
поки всі елементи не сортуються.
Подивіться на наступний несортованої елемента і вставте його в відсортованому частини,
шляхом зрушення необхідну кількість елементів з шляху.
Сподіваюся, ця візуалізація допоможе вам побачити саме те, що
відбувається з вставки роду.
>> Отже, ще раз, ось наш Весь масив несортовані,
всі елементи відображаються в червоному кольорі.
І давайте слідувати кроки нашої псевдокоді.
Перше, що ми робимо, є ми називаємо Перший елемент масиву, відсортувати.
Так що ми просто збираюся говорити п'ять, ви тепер сортуються.
>> Потім ми розглянемо на наступному несортоване елемент масиву
і ми хочемо, щоб вставити, що в частині відсортовано,
зрушуючи елементи старше.
Так два це наступний несортоване елемент масиву.
Очевидно, він належить до п'ять, так що ми збираємося зробити
є свого роду проведе два в сторону на секунду, перекласти п`ять над, а потім вставте дві
до п'яти, де повинні йти.
І тепер ми можемо сказати, що два сортується.
>> Отже, як ви бачите, ми тільки поки подивився на двох елементів масиву.
Ми не дивилися на відпочинок на всіх, але ми
отримав ці два елементи упорядковано Спосіб механізму перемикання.
>> Таким чином, ми повторюємо процес знову.
Подивіться на наступний несортоване елемент, що одна.
Давайте вважати, що в сторону на секунду, перекласти все закінчилося, і покласти один
де вона повинна йти.
>> Знову ж, досі, ми тільки коли-небудь подивився на один, два і п'ять.
Ми не знаємо, що ще йде, але ми упорядковано ці три елементи.
>> Наступна несортоване елемент зо три, так що ми будемо встановлювати його в сторону.
Ми поступово зміщувати те, що ми потрібно, який, на цей раз
це ще не все, як і в попередньому два випадки, це просто п'ять.
І тоді ми будемо дотримуватися три в, між двома і п'ятьма.
>> Шість є наступним несортоване елемент до масиву.
І справді шести більше п'яти, так ми навіть не потрібно робити які-небудь заміни.
Ми можемо просто лавірувати шостій право на кінець відсортованого частини.
>> Нарешті, чотири є Останнє несортоване елемент.
Таким чином, ми будемо встановлювати його в сторону, перейти по елементи, які ми повинні перенести протягом,
а потім покласти чотирьох, де вона належить.
А тепер подивіться, ми начебто з усіх елементів.
Зверніть увагу, з введенням сортувати, у нас не було
щоб йти вперед і назад через масив.
Ми тільки пішли через масив один час, і ми перейшли речі
що ми вже стикалися в порядок щоб звільнити місце для нових елементів.
>> Так що в гіршому випадку Сценарій з вставки роду?
У гіршому разі, масив у зворотному порядку.
Ви повинні перейти кожного з п елементів до н позицій, кожен раз, коли ми
зробити вставку.
Це багато змінюється.
>> У кращому випадку, Масив прекрасно відсортовані.
І ніби як те, що відбулося з п'ятьма і шістьма у прикладі,
де ми могли б просто лавірувати її на без того, щоб зробити будь-який зрушення,
ми, по суті, що робити.
>> Якщо уявити, що наші Масив був один через шість,
ми б почати з заявивши, один сортується.
Два приходить після одного, щоб ми могли просто кажуть, добре, добре один і два сортуються.
Три приходить після двох, так, добре, один і два, і три сортуються.
>> Ми не робимо ніяких свопи, ми просто переміщення цю довільну лінію
між сортуються і несортовані, як ми йдемо.
Як ефективно, як ми це робили в прикладі, повертаючи елементи синій, як ми далі.
Так що в гіршому випадку виконання, то?
Пам'ятайте, що якщо у нас є перекласти кожен з російські елементи, можливо, N позицій,
ми сподіваємося, що дає вам ідея, що в гіршому випадку
виконання є Великий О п квадраті.
>> Якщо масив прекрасно сортувати, все, що ми повинні зробити,
це подивитися на кожного елемента один раз, а потім ми зробили.
Таким чином, в кращому випадку, це омега п.
>> Я Дуг Ллойд.
Це CS50.