[Mūzikas atskaņošanai] Doug LLOYD: Selection kārtošanas ir algoritms, kas, kā jūs varētu gaidīt, sakārto elementu kopumu. Un algoritms atsaukšana ir soli pa solim komplekts par norādījumiem, kā pabeigt uzdevumu. 

Izvēlē kārtot Pamatideja ir tas, atrast mazāko nešķirotas elementu un pievienojiet to beigām šķiroto sarakstā. Efektīvi Kas tas ir būvēt sakārtoti sarakstu, viens elements laikā. Breaking to uz leju līdz pseudocode mēs varētu norādīt šo algoritmu šādi, atkārtojiet šo darbību, līdz Nav nešķirotas elementi paliek. Pārlūkot nešķiroti datus, lai atrastu mazāko vērtību, Pēc tam mijmaiņas mazāko vērtību ar no nešķirotu daļas pirmais elements. 

Tas var palīdzēt vizualizēt to, tāpēc pieņemsim to apskatīt šo. Tātad tas, es apgalvo, ir nešķiroti masīvs un es esmu norādīja to, norādot, ka visi no elementiem, ir sarkanā krāsā, tie vēl nav sakārtots. Tas ir viss nešķiroti daļa no masīva. 

So iesim cauri soļiem atlase Kārtot, lai sakārtotu šo masīvu. Tātad vēlreiz, mēs esam gonna atkārtot kamēr nav nešķirotas elementi paliek. Mēs esam gonna pārlūkot datus, lai atrastu mazāko vērtību, un pēc tam mijmaiņas šo vērtību ar no nešķirotu daļas pirmais elements. 

Tieši tagad, atkal, viss masīvs ir nešķirotas daļa. Visi sarkanās elementiem nav šķirotas. Tātad mēs pārlūkot un mēs atrodam mazāko vērtību. Sākam sākumā, mēs iet uz beigām, mēs atrodam mazāko vērtību ir viens. Tā ka ir viena daļa. Un tad otrā daļa, mijmaiņas šo vērtību ar No nešķirotu daļas pirmais elements, vai pirmais sarkanais elements. 

Šajā gadījumā, kas būtu pieci, tāpēc mēs mijmaiņas viena līdz pieciem. Kad mēs to darām, mēs varam vizuāli redzēt, ka mēs esam pārcēlās vismazāko vērtē elements masīva, lai paša sākuma. Efektīvi šķirošanas šo elementu. 

Un tā mēs varam patiesi apstiprināt un norāda, ka viens, ir sakārtots. Un tā mēs norāda sakārtoti daļu Mūsu masīva, iekrāsojot to zilā krāsā. 

Tagad mēs vienkārši atkārtot procesu no jauna. Mēs meklējam caur nešķirotu daļu masīvs atrast mazāko elementu. Šajā gadījumā tas ir divi. 

Mēs mijmaiņas ka ar pirmo no nešķirotiem daļas elements. Šajā gadījumā divi arī notiek, No nešķirotu daļas pirmais elements. Tātad mēs mijmaiņas divas ar sevi, kas patiešām ir tikai atstāj divus kur tas ir, un tas ir sakārtoti. Turpinot tālāk, mēs pārlūkot atrast mazāko elementu. Tas ir trīs. Mēs apmainīt to ar pirmo elements, kas ir pieci. Un tagad trīs ir sakārtots. 

Mēs pārlūkot atkal, un mēs atrast mazākais elements ir četri. Mēs apmainīt to ar pirmā elementa nešķiroti daļa, un tagad četri ir sakārtots. 

Mēs uzskatām, ka ir pieci mazākais elements. Mēs apmainīt to ar pirmo no nešķirotiem daļas elements. Un tagad pieci ir sakārtots. 

Un tad visbeidzot, mūsu nešķiroti daļu veido par tikai vienu elementu, tāpēc mēs pārlūkot un mēs redzam, ka seši ir mazākais, un faktiski vienīgais elements. Un tad mēs varam apgalvot, ka tas ir sakārtots. Un tagad mēs esam pārgājuši mūsu masīvs tiek pilnīgi Nesašķirotas sarkanā krāsā, lai pilnībā sakārtots zilā krāsā, izmantojot atlases veida. 

Tātad, kas ir sliktākais scenārijs šeit? Nu absolūti sliktākais gadījumā, mums ir jāskatās pāri visu elementu masīva līdz atrast mazāko nešķirotas elementu, un mums ir jāatkārto šis process n reizes. Pēc tam, kad katram masīva elementa jo mēs tikai, šajā algoritmu, kārtot viens elements laikā. 

Kāds ir labākais scenārijs? Nu tas ir tieši tas pats, vai ne? Mums tiešām ir vēl soli pa katru elementu masīva lai apstiprinātu to, ka tas ir, patiesībā, mazākais elements. 

Tātad sliktākajā gadījumā runtime, mēs atkārtot procesu n reizes, vienreiz par katru no n elementiem. Un labākajā gadījumā, mums ir jādara tas pats. 

Tātad domāšana atpakaļ uz mūsu skaitļošanas sarežģītība toolbox, Ko jūs domājat, ir vissliktākais Lieta runtime uz atlases veida? Kas, Jūsuprāt, ir labākais Lieta runtime uz atlases veida? 

Vai jūs uzminēt Big O no n brusas, un Big Omega n kvadrātā? Tu būsi taisnība. Tie ir, faktiski, sliktākajā gadījumā un labākajā gadījumā palaist reizes, lai atlases veida. 

Es esmu Doug Lloyd. Tas ir CS50.