[Música tocando] Doug LLOYD: Selección é unha especie algoritmo que, como podería esperar, Clasifica un conxunto de elementos. E algoritmo recordo é un conxunto paso a paso de instrucións para completar unha tarefa. 

Na selección clasificar a idea básica é esta: atopar o menor elemento sen clasificar e engadir lo ao final da lista ordenada. Efectivamente o que iso fai é construír unha lista clasificada, un elemento de cada vez. Rompe-lo para abaixo para pseudocódigo podemos afirmar este algoritmo deste xeito, repita iso ata non hai elementos non ordenados permanecen. Busca a través da indiferenciados datos para atopar o menor valor, a continuación, cambiar o menor valor co primeiro elemento da parte indiferenciados. 

Ela pode axudar a ver isto, así que imos dar un ollo niso. Entón iso, eu afirmo, é unha matriz sen clasificar e eu teño indicou que, indicando que todo dos elementos son de cor vermella, eles non son clasificadas. Este é o enteiro indiferenciados parte da matriz. 

Entón, imos percorrer os pasos de selección clasificación para clasificar esta matriz. Entón, de novo, nós imos repeat ata que non haxa elementos non ordenados permanecen. Nós imos busca a través da datos para atopar o menor valor, e despois cambiar ese valor co primeiro elemento da parte indiferenciados. 

Agora, unha vez máis, a toda matriz é a parte indiferenciados. Todos os elementos vermellos son indiferenciados. Por iso, buscar e atopamos o menor valor. Comezamos en principio, nós imos ata o final, atopamos o menor valor, un. Entón esta é unha parte. E, a continuación, a parte dous, intercambiar ese valor con o primeiro elemento da parte non clasificado, ou o primeiro elemento vermello. 

Neste caso que sería cinco, polo tanto, cambiar un e cinco. Cando facemos iso, podemos visualmente ver que temos moveu o elemento máis pequeno valorado da matriz, para o inicio. En efecto selección ese elemento. 

E así podemos efectivamente confirmar e afirman que un, está clasificada. E así imos indicar a porción clasificada da nosa matriz, colorido o azul. 

Agora é só repetir o proceso de novo. Buscamos a través da parte sen clasificar de a matriz para atopar o elemento máis pequeno. Neste caso, é dous. 

Nós que cambiar coa primeira elemento da parte indiferenciados. Neste caso, dous tamén pasa a ser o primeiro elemento da parte indiferenciados. Entón nós trocamos dous con si mesmo, o que realmente deixa só dous onde está, e está clasificado. Continuando, nós buscar para atopar o elemento máis pequeno. É tres. Nós troca-lo o primeiro elemento, que é de cinco. E agora tres está clasificada. 

Nós investigación a través de novo, e nós atopar o menor elemento é catro. Nós troca-lo o primeiro elemento da parte sen clasificar, e agora catro está clasificada. 

Nós cremos que é cinco o elemento máis pequeno. Nós troca-lo o primeiro elemento da parte indiferenciados. E agora cinco está clasificada. 

E entón, finalmente, o noso parte consiste sen clasificar de só un único elemento, por iso, buscar e nós cremos que seis é o menor, e de feito, único elemento. E entón podemos afirmar que é clasificado. E agora cambiamos nosa matriz de ser completamente non separados en vermello, completamente clasificadas en azul, a través da selección de clasificación. 

Entón, cal é o peor escenario aquí? Ben no peor absoluta caso, temos que mirar por riba todos os elementos da matriz para atopar o menor elemento non clasificado, e temos que repetir este proceso n veces. Xa que para cada elemento do array porque só neste algoritmo, tipo un elemento de cada vez. 

Cal é o mellor escenario? Ben, é exactamente o mesmo, non? En realidade, hai que seguir a percorrer cada elemento da matriz a fin de confirmar que é, En realidade, o elemento máis pequeno. 

Entón, o peor caso de tempo de execución, que ten que repetir un proceso n veces, unha vez para cada un dos n elementos. E no mellor dos casos, temos que facer o mesmo. 

Entón, pensando de volta ao noso Toolbox complexidade computacional, o que pensas que é o peor caso de tempo de execución para a selección tipo? ¿Que pensas que é o mellor caso de tempo de execución para a selección tipo? 

Será que adiviña Big O n ao cadrado, e Big Omega n ao cadrado? Estaría ben. Estes son, en realidade, o peor caso e mellor caso de execución veces, para a selección de tipo. 

Eu son Doug Lloyd. Este é CS50.