[Powered by Google Translate] TOMMY: Давайте поглянемо на вибір роду, алгоритм
для ухвалення списку чисел і сортування їх.
Алгоритм, пам'ятаєте, це просто крок за кроком
Процедура для виконання завдання.
Основна ідея вибору роду полягає в поділі
наш список на дві частини -
відсортовано частини і несортовані частина.
На кожному кроці алгоритму, числа переміщається з
непідібране частини до відсортовані частина поки в кінці кінців
Весь список відсортований.
Отже, ось список з шести цифр -
23, 42, 4, 16, 8 та 15.
Зараз весь список вважається відсортовані.
Хоча число як 16 уже може бути в правильному
місце, наш алгоритм не має можливості дізнатися, що до
Весь список відсортований.
Таким чином, ми будемо розглядати кожен номер, який буде несортоване, поки ми не сортувати
це самі.
Ми знаємо, що ми хочемо, щоб список, який буде в порядку зростання.
Тому ми хочемо створити відсортований частина нашого списку
зліва направо, від меншого до більшого.
Щоб зробити це, нам потрібно знайти мінімальний елемент несортовані
і поклав його в кінці відсортовані частина.
Оскільки цей список не відсортований, єдиний спосіб зробити це, щоб
дивитися на кожен елемент в несортоване частина, згадавши
який елемент є найнижчим і порівнюючи
кожен елемент цього.
Таким чином, ми спочатку дивимося на 23.
Це перший елемент, який ми бачили, тому ми будемо пам'ятати
це як мінімум.
Далі ми розглянемо 42.
42 більше ніж 23, тому 23 як і раніше є мінімальним.
Далі йде 4, який є менше, ніж 23, так що ми пам'ятаємо 4
як новий мінімум.
Далі йде 16, яка більше 4, тому 4
як і раніше є мінімальним.
8, розмір яких перевищує 4, а 15 більше 4, тому 4 повинна бути
найменший елемент несортовані.
Так що, хоча, як і люди, ми можемо відразу побачити, що 4
мінімального елемента, наш алгоритм повинен дивитися на
кожен елемент несортоване, навіть після того, як ми знайшли 4 -
мінімальний елемент.
Так що тепер ми знайшли мінімальний елемент, 4, ми хочемо
щоб перемістити його в відсортованому частину списку.
Так як це перший крок, це означає, що ми хочемо поставити 4 на
На початку списку.
Зараз 23 знаходиться на початку списку, так
Давайте обмінюватися 4 і 23.
Так що тепер наш список виглядає наступним чином.
Ми знаємо, що 4 повинен знаходитися в своєму остаточному місці, тому що це
як найменший елемент і елемент на початку
списку.
Таким чином, це означає, що ми ніколи не повинні перемістити його знову.
Так давайте повторимо цей процес, щоб додати ще один елемент
відсортовано частину списку.
Ми знаємо, що ми не повинні дивитися на 4, тому що це
вже відсортовані.
Таким чином, ми можемо почати в 42, в якій ми будемо пам'ятати, як
мінімальний елемент.
Так що в наступний ми будемо дивитися на 23, що менше, ніж 42, тому ми
пам'ятаю 23 є новим мінімумом.
Далі ми бачимо 16, який менше, ніж 23, тому
16 є новим мінімумом.
Тепер ми дивимося на 8, який менше, ніж 16, так
8 є новим мінімумом.
І, нарешті, 8 менше, ніж 15, так що ми знаємо, що 8 є мінімальним
непідібране елемент.
Значить, ми повинні додати 8 до відсортований
частину списку.
Зараз 4 є єдиним відсортований елемент, тому ми хочемо помістити
8 вперед на 4.
З 42 є першим елементом у несортоване частина
Список, ми хочемо, щоб обміняти 42 і 8.
Так що тепер наш список виглядає наступним чином.
4 і 8 являють собою впорядковані частині списку, а
Інші цифри являють несортовані
частину списку.
Так що давайте продовжувати з іншого ітерації.
Ми починаємо з 23 на цей раз, так як ми не повинні дивитися на
4 і на 8 більше, тому що вони
вже відсортовані.
16 менше 23, тому ми будемо пам'ятати
16 в якості нового мінімуму.
16 менше 42, а 15 менше 16, так 15 має бути
мінімальний несортовані елемент.
Отже, тепер ми хочемо, щоб поміняти 15 і 23 по
дайте нам цей список.
Відсортовано частину списку складається з 4, 8 і 15, і
ці елементи як і раніше відсортовані.
Але так вже сталося, що наступний елемент несортоване, 16,
вже відсортовані.
Однак, немає ніякого способу для нашого алгоритму, щоб дізнатися, що 16
вже в правильному місці, тому ми все ще повинні
Повторюю точно такий же процес.
Отже, ми бачимо, що 16 менше, ніж 42, і 16 менше 23, тому
16 повинен бути мінімальним елементом.
Неможливо обміняти цей елемент сам з собою, тому ми можемо
Просто залиште його в цьому місці.
Так що нам потрібно ще один прохід нашого алгоритму.
42 більше 23, тому 23 має бути
мінімальна несортовані елемент.
Після того як ми переставляємо 23 і 42, ми в кінцевому підсумку з нашої останньої
відсортований список -
4, 8, 15, 16, 23, 42.
Ми знаємо, що 42 повинні бути в правильному місці, так як це
Єдиний елемент залишили, і це вибір роду.
Давайте тепер оформити наш алгоритм з деякими
псевдокод.
На першій лінії, ми бачимо, що нам потрібно інтегрувати по
кожен елемент списку.
За винятком останнього елемента, так як 1 елемент
список вже відсортований.
На другій лінії, ми розглянемо перший елемент несортовані
Частина списку, щоб бути мінімальним, як ми зробили з нашим
Наприклад, у нас є щось для порівняння.
Третій рядок починається другий цикл, в якому ми перебору
кожен несортовані елемент.
Ми знаємо, що після того як я ітерацій, відсортовані частини
з нашого списку повинні мати елементи я в ньому з кожним кроком
види одного елемента.
Таким чином, перший несортовані елемент повинен знаходитися в положенні я плюс 1.
На четвертому рядку, ми порівнюємо поточний елемент до мінімуму
елемент, який ми бачили дотепер.
Якщо поточний елемент менше, ніж мінімальна
елемент, то ми пам'ятаємо, поточний елемент в якості нової
Мінімум на лінії п'ять.
Нарешті, на лінії шість і сім, ми переставляємо мінімальної
елемент з першим елементом несортоване, таким чином,
додати його в відсортованому частину списку.
Як тільки ми отримаємо алгоритм, важливе питання
себе в якості програмістів як довго це займе?
Ми спочатку поставити запитання, скільки часу буде потрібно для цього
Алгоритм для роботи в гіршому випадку?
Нагадаємо, ми представляємо цей хід
Час з великої позначення O.
Для того, щоб визначити мінімальну несортовані елемент,
по суті було порівняти кожен елемент в списку
будь-який інший елемент у списку.
Інтуїтивно, це звучить як O п квадрат операції.
Дивлячись на нашому псевдокоді, ми також маємо цикл вкладений в
інший цикл, який дійсно звучить як O
п квадрат операції.
Однак пам'ятайте, що ми не повинні дивитися на
Весь список при визначенні мінімального несортовані елемент?
Як тільки ми знали, що 4 був відсортований, наприклад, ми не
потрібно дивитися на це знову.
Чи означає це, нижня час роботи?
Для нашого списку довжина 6, нам потрібно було зробити п'ять
порівнянь для першого елемента, чотири порівнянь для
Другий елемент, і так далі.
Це означає, що загальна кількість кроків є сумою
числами від 1 до довжини списку мінус 1.
Ми можемо уявити це за допомогою підсумовування.
Ми не будемо вдаватися в сумах тут.
Але виявляється, що це підсумовування дорівнює п раз
N мінус 1 по 2.
Або, що еквівалентно, п квадрат більше 2 мінуса п над 2.
Коли мова йде про асимптотичної виконання, це п квадрат термін
буде домінувати в цій п термін.
Таким чином, вибір сортування O п квадрат.
Нагадаємо, що в нашому прикладі, вибір роду все ще потребують
перевірте номер, який був уже відсортований
Необхідно переміщати.
Таким чином, це означає, що якщо ми побігли вибір роду на вже
відсортований список, це зажадає стільки ж кроків, як це
б при роботі над цілком несортоване список.
Таким чином, вибір роду має найкращому разі виконання п квадратів,
які ми представляємо з омега N в квадраті.
І ось саме для вибору роду.
Це лише один з багатьох алгоритмів можна
використовувати для сортування списку.
Мене звати Томмі, і це CS50.