[Powered by Google Translate] [Вставка Сортування] [Tommy MacWilliam] [Гарвардський університет] [Це CS50.TV] Давайте поглянемо на сортування вставками, алгоритм прийняття список чисел і сортування їх. Алгоритм, пам'ятаєте, це просто крок за кроком процедури для виконання завдання. Основна ідея сортування вставкою, полягає в поділі нашого списку на дві частини, відсортовано частини і несортовані частина. 

На кожному кроці алгоритму, числа переміщається від несортовані частини до відсортовані частина поки в кінці кінців весь список буде відсортований. Ось список з шести несортовані номери - 23, 42, 4, 16, 8 та 15. Оскільки ці цифри не все в порядку, вони відсортовані. Так як ми ще не почали сортування тим не менше, ми будемо розглядати всі шість елементів наших несортовані частина. 

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

Щоб зробити це, нам потрібно порівняти з 42 до 23 - єдиний елемент у наших сортуються частина досі. Сорок два більше, ніж 23, тому ми можемо просто додати 42 до кінця з відсортованих частину списку. Відмінно! Тепер наші відсортовані частина складається з двох елементів, і наші несортовані частина складається з чотирьох елементів. Отже, давайте перейдемо до 4, то наступний елемент у несортоване частина. Так, де це повинно бути поміщене в відсортовані частина? 

Пам'ятаєте, ми хочемо помістити це число в певному порядку таким чином, наші відсортовані частина залишається правильно відсортований у всі часи. Якщо ми помістимо 4 вправо з 42, то наш список буде в порядку. Отже, давайте продовжувати рухатися праворуч-ліворуч в наш рід частина. Оскільки ми рухаємося, давайте перекласти кожен номер вниз місце, щоб звільнити місце для нового номера. Гаразд, 4 також менше, ніж 23, тому ми не можемо помістити його і тут. Давайте перейдемо на 23 праву одному місці. 

Це означає, що ми хотіли б розмістити 4 в перший слот в відсортованої частини. Зверніть увагу, як це місце в списку було вже порожньо, тому що ми рухалися відсортовані елементи вниз, як ми зіткнулися з ними. Добре. Таким чином, ми вже на півдорозі. Давайте продовжимо наш алгоритм, вставивши 16 в відсортовані частина. Шістнадцять менше, ніж 42, так що давайте перекласти 42 до правої. Шістнадцять також менше, ніж 23, так що давайте також зсув цього елемента. 

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

Добре. Тепер у нас є чотири відсортовані елементів і двох елементів несортовані. Отже, давайте перейдемо 8 у відсортовані частина. Вісім менше, ніж 42. Вісім менше, ніж 23. А 8 менше, ніж 16. Але 8 більше 4. Таким чином, ми хотіли б, щоб вставити 8 між 4 і 16. А зараз ми просто ще один елемент залишили для сортування - 15. П'ятнадцять менше, ніж 42, П'ятнадцять менше, ніж 23. А 15 менше, ніж 16. Але 15 більше, ніж 8. 

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

У рядку 1, ми бачимо, що нам потрібно для перебору кожного елемента в списку крім першої, так як перший елемент у несортоване частина просто стануть Перший елемент в відсортованої частини. У рядках 2 і 3, ми відстежують наше нинішнє місце в несортоване частина. Елемент являє собою число ми в даний час рухається в відсортовані частина, і J представляє наш індекс в несортоване частина. 

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

Ми знаємо, що це нормально для вставки в позицію J, тому що ми вже переїхали елемент, що використовується, щоб бути там одне місце вправо. Пам'ятайте, що ми рухаємося через відсортовані частина справа наліво, але ми рухаємося через несортовані частину зліва направо. Добре. Давайте тепер поглянемо на те, як довго працює, що алгоритм взяв. Ми спочатку поставити запитання, скільки часу буде потрібно для цього алгоритму для роботи в гіршому випадку. Нагадаємо, що ми представляємо цей час роботи з великою позначення O. Для того, щоб розібратися наш список, ми були для перебору елементів в несортоване частина, і для кожного з цих елементів, потенційно над всіма елементами в відсортованої частини. Інтуїтивно, це звучить як O (N ^ 2) операцій. 

Дивлячись на нашому псевдокоді, у нас є цикл вкладений в інший цикл, який, дійсно, звучить як O (N ^ 2) операцій. Тим не менш, відсортовані частину списку не містять весь список до самого кінця. Тим не менш, ми потенційно могли б вставити новий елемент на самому початку відсортованого частина на кожній ітерації алгоритму, Це означає, що ми повинні дивитися на кожен елемент в даний час в відсортованої частини. Таким чином, це означає, що ми потенційно могли б зробити одне порівняння для другого елементу, два порівняння для третього елемента, і так далі. Таким чином, загальна кількість кроків є сума чисел від 1 до довжини списку мінус 1. Ми можемо уявити це за допомогою підсумовування. 

Ми не будемо вдаватися в сумах тут, але виявляється, що це підсумовування одно (П - 1) більше 2, що еквівалентно п ^ 2/2 - п / 2. Коли мова йде про асимптотичної виконання, це п ^ 2 терміну буде домінувати в цій п термін. Таким чином, включення сортування Big O (N ^ 2). Що, якщо ми побігли сортування вставкою в уже відсортований список. У цьому випадку, ми б просто створити відсортований частину зліва направо. Таким чином, ми будемо тільки потрібно близько п кроків. 

Це означає, що сортування вставкою має найкращому разі виконання п, які ми представляємо з Ω (N). І ось саме для сортування вставкою, лише одна з багатьох алгоритмів можна використовувати для сортування списку. Мене звати Томмі, і це CS50. [CS50.TV] О, ви просто не можете зупинитися, що як тільки він починається. Так, ми зробили це - >> Boom!