[Грає музика] ДАГ Lloyd: Сортувати Вибір є алгоритм, який, як ви могли б очікувати, сортує набір елементів. І алгоритм відгук це крок за кроком набір інструкцій для виконання завдання. 

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

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

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

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

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

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

Тепер ми просто повторити процес знову. Ми шукаємо через несортованої частини масив, щоб знайти найменший елемент. У цьому випадку, це два. 

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

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

Ми вважаємо, що це п'ять найменший елемент. Ми поміняти його з першим елемент невідсортоване частини. А тепер п`ять сортується. 

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

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

Який найкращий сценарій? Ну, це точно так само, вірно? Ми насправді потрібно ще пройти через кожен елемент масиву для того, щоб підтвердити, що він є, Справді, найменший елемент. 

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

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

Ви здогадалися Big O н квадрат, і Великий Омега п квадраті? Ви були б праві. Ті, справді, в гіршому випадку і кращий випадок виконання раз, для вибору роду. 

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