Tip:
Highlight text to annotate it
X
>> [Грає музика]
ДАГ Lloyd: Сортувати Вибір є алгоритм, який, як ви могли б очікувати,
сортує набір елементів.
І алгоритм відгук це крок за кроком набір
інструкцій для виконання завдання.
>> При виборі сортувати Основна ідея це,
знайти найменше несортоване елемент і додати його в кінці відсортованого списку.
Ефективно, що це робить збірки відсортований список, один елемент за один раз.
Порушення його до псевдокоді ми могли б стверджувати, цей алгоритм
як слід, не повторювати це, поки немає несортовані елементи залишаються.
Пошук через несортоване дані, щоб знайти найменше значення,
Потім поміняти найменше значення з Перший елемент невідсортоване частини.
>> Це може допомогти візуалізувати це, так що давайте поглянемо на це.
Так що це Я стверджую, що це несортоване масив а у мене
вказано його про те, що всі з елементів червоного кольору,
вони ще не сортуються.
Це повне несортоване частина масиву.
>> Отже, давайте по кроках Вибір роду сортувати цей масив.
Отже, ще раз, ми збираємося повторити ДН не несортовані елементи залишаються.
Ми збираємося Пошук по дані, щоб знайти найменше значення,
а потім обміняти цю величину з Перший елемент невідсортоване частини.
>> Зараз, знову ж таки, вся Масив є несортоване частину.
Всі червоних елементів несортоване.
Таким чином, ми шукати через і ми знаходимо найменше значення.
Ми почнемо з самого початку, ми йдемо до кінця,
ми знаходимо найменше значення, один.
Так от перша частина.
І тоді друга частина, поміняти це значення з перший елемент невідсортоване частини,
або перший елемент червоний.
>> У цьому випадку, було б п'ять, так що ми поміняти одного до п'яти.
Коли ми робимо це, ми можемо наочно побачити, що ми
переїхав з найменшим значенням елемента масиву, на самому початку.
Ефективно сортування цей елемент.
>> І таким чином ми можемо підтвердити, чи дійсно і держава, що один, сортується.
І тому ми будемо вказувати відсортований частина з нашого масиву, за забарвленням він блакитний.
>> Тепер ми просто повторити процес знову.
Ми шукаємо через несортованої частини масив, щоб знайти найменший елемент.
У цьому випадку, це два.
>> Ми поміняти, що з першого елемент невідсортоване частини.
У цьому випадку два також буває перший елемент невідсортоване частини.
Таким чином, ми поміняти два з себе, які насправді просто залишає дві
де він знаходиться, і це сортується.
Продовжуючи, ми шукаємо через знайти найменший елемент.
Це три.
Ми поміняти його з першим елемент, який є п'ять.
А тепер три сортується.
>> Ми знову шукати через, і ми знайти найменший елемент чотири.
Ми поміняти його з першим елементом несортоване частина, і в даний час чотири сортується.
>> Ми вважаємо, що це п'ять найменший елемент.
Ми поміняти його з першим елемент невідсортоване частини.
А тепер п`ять сортується.
>> І тоді, нарешті, наш несортоване частина складається
тільки з одного елемента, тому ми шукати через
і ми знаходимо, що шість це маленький, а насправді, єдиним елементом.
І тоді ми можемо стверджувати, що це сортується.
А тепер ми перейшли нашу масив від повного несортоване
в червоний, повністю упорядковано в синьому, за допомогою вибору роду.
>> Так що в гіршому випадку тут?
Ну в найгірше так, ми повинні дивитися за
всі елементи масиву в знайти найменше несортоване елемент,
і ми повинні повторити цей процес п раз.
Після того, як для кожного елемента масиву бо ми тільки в цьому алгоритмі,
Сортувати один елемент за раз.
>> Який найкращий сценарій?
Ну, це точно так само, вірно?
Ми насправді потрібно ще пройти через кожен елемент масиву
для того, щоб підтвердити, що він є, Справді, найменший елемент.
>> Таким чином, в гіршому разі виконання, ми доведеться повторити процес п раз,
один раз для кожного з п елементів.
І в кращому випадку, ми повинні зробити те ж саме.
>> Так згадуючи наш обчислювальна складність інструментів,
те, що ви думаєте, це найгірше Справа виконання для вибору роду?
Що ви вважаєте найкращим Справа виконання для вибору роду?
>> Ви здогадалися Big O н квадрат, і Великий Омега п квадраті?
Ви були б праві.
Ті, справді, в гіршому випадку і кращий випадок виконання
раз, для вибору роду.
>> Я Дуг Ллойд.
Це CS50.