[За възпроизвеждане на музика] Дъг LLOYD: Избор на сортиране е алгоритъм, който, както може да се очаква, сортира набор от елементи. И алгоритъм изземване е набор стъпка по стъпка на инструкции за попълването на дадена задача. 

В подбора сортирате основната идея е тази, намерят най-малкия елемент и е сортиран да го добавите в края на сортиран списък. Ефективно какво прави това е натрупването а сортирани списък, един елемент в даден момент. Тя Премахване на Псевдокод бихме могли да се посочи този алгоритъм както следва, повтарям това, докато не несортиран елементи остават. Търсене чрез несортирани данни, за да намерят най-малката стойност, След това сменяте най-малката стойност с Първият елемент от сортиран част. 

Тя може да помогне да се визуализира това, така че нека да погледнем на това. Така че това, Аз твърдя, е сортиран масив и съм той посочи, като посочи, че всички на елементите са оцветени в червено, те все още не са подредени. Това е цялото несортиран част на масива. 

Така че нека да мине през етапите на Избор на вид, за да сортирате този масив. Така че отново, ние ще се повтаря докато не останат несортиран елементи. Ние ще търсим в по данни, за да намерят най-малката стойност, и след това да сменяте тази стойност с Първият елемент от сортиран част. 

Точно сега, отново, цялата масив е сортиран част. Всички червени елементи са неразделени. Така че ние търсим в и ние намираме най-малката стойност. Започваме в началото, отидем до края, ние намираме най-малката стойност е един. Така че това е първа част. И тогава част втора, сменяте тази стойност с първият елемент на несортиран част, или първата червен елемент. 

В този случай това би било пет, така че можем да сменяте една и пет. Когато правим това, което можем визуално се види, че ние сме премества най-малката ценен елемент на масива, за самото начало. Ефективно сортиране този елемент. 

И така, ние наистина може да се потвърди и посочва, че една, се сортира. И така, ние ще посочи сортирани част на нашия масив, чрез оцветяване го синьо. 

Сега ние просто повторете процеса отново. Търсим през несортирани част на масива, за да намерите най-малкия елемент. В този случай, това е две. 

Ние суап, че с първия елемент от сортиран част. В този случай две също се случва да бъде първият елемент на несортиран част. Така че ние суап две сам със себе си, които наистина просто оставя двама където и да е, и това е сортирани. Продължавайки нататък, ние търсим в да се намери най-малкия елемент. Това е три. Ние го сменяте с първия елемент, който е пет. И сега три се сортира. 

Ние търсим в отново, и ние намерят най-малкият елемент е четири. Ние го сменяте с първия елемент от несортиран част, а сега четири се сортира. 

Ние намираме, че пет е най-малкия елемент. Ние го сменяте с първия елемент от сортиран част. И сега пет се сортира. 

И след това накрая, нашата несортиран част се състои на само един елемент, така че ние търсим в и ние откриваме, че шест е малката, а в действителност, само елемент. И тогава можем да заявим, че това се сортира. И сега ние сме включен нашия масив да бъде напълно несортирани в червено, за да напълно сортирани в синьо, като се използва за избор на сортиране. 

Така че това, което е най-лошият сценарий тук? Ами в абсолютния-лошото случай, ние трябва да погледнем над Всички елементи на масива намерят най-малката е сортиран елемент, и ние трябва да се повтаря този процес п пъти. След като за всеки елемент на масива защото само в този алгоритъм, подреди един елемент в момента. 

Какво е най-добрия случай? Ами това е точно същото, нали? Ние всъщност трябва да продължава да преминете през всеки един елемент от масива за да се потвърди, че това е, В действителност, най-малкия елемент. 

Така че най-лошия случай на работа, ние трябва да се повтаря един процес п пъти, веднъж за всеки от п елементи. И в най-добрия случай, ние трябва да направим същото. 

Така че мисля обратно към нашия изчислителна сложност инструментариум, какво според вас е най-лошото При изпълнение за избор подреди? Какво мислиш, че е най-добрият При изпълнение за избор подреди? 

Знаете ли, предполагам, Big O на п квадрат, и Big Omega на п квадрат? Вие искате да бъде прав. Това са, в действителност, най-лошия случай и най-добрият случай продължава пъти, за избор на сортиране. 

Аз съм Дъг Лойд. Това е CS50.