>> [Музички]
Даг LLOYD: Избор вид е алгоритам кој, како што би очекувале,
сортира е збир на елементи.
И алгоритам се потсетиме е збир чекор-по-чекор
упатства за завршување на задачата.
>> Во селекцијата сортирате Основната идеја е ова,
најде најмалиот несортиран елемент и да го додадете на крајот на Подредена листа.
Ефикасно Што тоа не е да се изгради на сортирана листа, еден елемент во исто време.
Тоа се урива за да се pseudocode ние би можеле да се наведе овој алгоритам
како што следува, повторете го овој до Нема несортиран елементи остануваат.
Пребарување низ несортиран податоци за да ја најмалата вредност,
тогаш трампа најмалата вредност со Првиот елемент на несортиран дел.
>> Тоа може да помогне да се визуелизира ова, па ајде да ги разгледаме во тоа.
Па ова, јас се соочат, е несортиран низа и јас сум
што е наведено од страна покажува дека сето на елементите се обоени црвено,
тие се уште не се подредени.
Ова е целиот несортиран дел од низата.
>> Па ајде да одиме низ чекорите на селекција вид да се најде решение за оваа низа.
Значи, повторно, ние ќе отидеме повторување додека не остане без несортиран елементи.
Ние ќе пребарување преку податоци за да ја најмалата вредност,
а потоа се разменуваат таа вредност со Првиот елемент на несортиран дел.
>> Токму сега, повторно, целиот Низа е несортиран дел.
Сите црвени елементи се несортиран.
За да можеме да пребарувате преку и наоѓаме најмалата вредност.
Се вклучуваме во почетокот, ние одиме до крај,
наоѓаме најмалата вредност е еден.
Значи, тоа е еден дел.
А потоа и втор дел, кои се разменуваат со вредност првиот елемент на несортиран дел,
или првиот црвено елемент.
>> Во овој случај тоа би било пет, па ние се разменуваат една и пет.
Кога ќе го направите ова, ние може визуелно да се види дека ние сме
преселил најмалата вредност елемент на низата, на самиот почеток.
Ефективно подредување тој елемент.
>> И така ние навистина може да се потврди и велат дека еден, се подредени.
И така ќе укаже на подредени дел на нашата низа, со боење тоа сино.
>> Сега ние само го повтори овој процес одново.
Бараме преку несортиран дел низата да се најде најмалиот елемент.
Во овој случај, тоа е два.
>> Ние трампа дека со првиот елемент на несортиран дел.
Во овој случај, исто така, две се случува да биде првиот елемент на несортиран дел.
Значи ние се разменуваат две со себе, кои, навистина, само остава две
каде што е, и тоа е се подредени.
Кои и понатаму продолжуваат, бараме преку да се најде најмалиот елемент.
Тоа е три.
Ние го трампа со првиот елемент, кој е пет.
А сега три се подредени.
>> Бараме преку повторно, и ние најде најмалиот елемент е четири.
Ние го трампа со првиот елемент на несортиран дел, а сега четири се подредени.
>> Сметаме дека е пет најмалиот елемент.
Ние го трампа со првиот елемент на несортиран дел.
А сега пет се подредени.
>> А потоа и на крај, нашата несортиран дел се состои
на само еден елемент, па ние се бара преку
и гледаме дека шест е најмалиот, и всушност, единствениот елемент.
И потоа можеме да наведе дека се подредени.
И сега ние сме вклучен нашата низа од тоа да биде целосно вон едиции
во црвена, целосно да се решат со сина боја, со користење на селекција кој вид.
>> Значи, што е најлошото сценарио во оваа ситуација?
И во апсолутна најлош случај, ние треба да се погледне во текот на
сите елементи на низата да најде најмалиот несортиран елемент,
и ние треба да се повторува овој процес n пати.
Еднаш за секој елемент од низата затоа што само во овој алгоритам,
вид еден елемент на времето.
>> Што е најдоброто сценарио?
Па тоа е токму истото, нели?
Ние всушност треба да се уште да влезете низ секој елемент од низата
со цел да се потврди дека тоа е, всушност, најмалиот елемент.
>> Па најлош случај траење, ние треба да се повторува процесот n пати,
еднаш за секој од n елементи.
И во најдобар случај, ние треба да го стори истото.
>> Толку размислување назад кон нашите компјутерската комплексност алатникот,
она што мислите дека е најлошото случај траење за избор на вид?
Што мислите дека е најдобар случај траење за избор на вид?
>> Ми го погоди Биг О од n квадрат, Големи и Омега на n квадрат?
Ќе бидете во право.
Тоа се, всушност, најлош случај и најдобар случај бегство
Понекогаш, за избор на вид.
>> Јас сум Даг Лојд.
Ова е CS50.