[Música tocando] DOUG LLOYD: Seleção é uma espécie algoritmo que, como você poderia esperar, Classifica um conjunto de elementos. E algoritmo recordação é um conjunto passo-a-passo de instruções para completar uma tarefa. 

Na seleção classificar a idéia básica é esta: encontrar o menor elemento não triados e adicioná-lo para o fim da lista ordenada. Efetivamente o que isso faz é construir uma lista classificada, um elemento de cada vez. Quebrá-lo para baixo para pseudocódigo podemos afirmar este algoritmo como se segue, repita isso até não há elementos não ordenados permanecem. Pesquisa através da indiferenciados dados para encontrar o menor valor, em seguida, trocar o menor valor com o primeiro elemento da parte indiferenciados. 

Ela pode ajudar a visualizar isto, por isso vamos dar uma olhada nisso. Então isso, eu afirmo, é uma matriz não triados e eu tenho indicou que, indicando que todos dos elementos são de cor vermelha, eles ainda não são classificadas. Este é o inteiro indiferenciados parte da matriz. 

Então, vamos percorrer as etapas de seleção classificação para classificar essa matriz. Então, novamente, nós vamos repeat até que não haja elementos não ordenados permanecem. Nós vamos pesquisa através da dados para encontrar o menor valor, e depois trocar esse valor com o primeiro elemento da parte indiferenciados. 

Agora, mais uma vez, a toda matriz é a parte indiferenciados. Todos os elementos vermelhos são indiferenciados. Por isso, pesquisar e encontramos o menor valor. Começamos no início, nós vamos até o fim, encontramos o menor valor é, um. Então essa é uma parte. E, em seguida, a parte dois, trocar esse valor com o primeiro elemento da parte não classificado, ou o primeiro elemento vermelho. 

Neste caso que seria cinco, portanto, trocar um e cinco. Quando fazemos isso, nós podemos visualmente ver que nós temos moveu o elemento mais pequeno valorizado da matriz, para o início. Efectivamente triagem esse elemento. 

E assim podemos efectivamente confirmar e afirmam que um, está classificada. E assim vamos indicar a porção classificada de nossa matriz, colorindo o azul. 

Agora é só repetir o processo novamente. Procuramos através da parte não triados de a matriz para encontrar o elemento mais pequeno. Neste caso, é dois. 

Nós que trocar com a primeira elemento da parte indiferenciados. Neste caso, dois também acontece a ser o primeiro elemento da parte indiferenciados. Então nós trocamos dois com si mesmo, o que realmente deixa apenas dois onde está, e está classificado. Continuando, nós pesquisar para encontrar o elemento mais pequeno. É três. Nós trocá-lo com o primeiro elemento, que é de cinco. E agora três está classificada. 

Nós pesquisa através de novo, e nós encontrar o menor elemento é quatro. Nós trocá-lo com o primeiro elemento da parte não triados, e agora quatro está classificada. 

Nós achamos que é cinco o elemento mais pequeno. Nós trocá-lo com o primeiro elemento da parte indiferenciados. E agora cinco está classificada. 

E então, finalmente, o nosso parte consiste não triados de apenas um único elemento, por isso, pesquisar e nós achamos que seis é o menor, e de fato, único elemento. E então podemos afirmar que ele é classificado. E agora mudamos nossa matriz de ser completamente não separados em vermelho, completamente classificadas em azul, usando a seleção de classificação. 

Então, qual é o pior cenário aqui? Bem no pior absoluta caso, temos que olhar por cima todos os elementos da matriz para encontrar o menor elemento não classificado, e nós temos que repetir este processo n vezes. Uma vez que para cada elemento do array porque nós só, neste algoritmo, tipo um elemento de cada vez. 

Qual é o melhor cenário? Bem, é exatamente o mesmo, certo? Na verdade, temos de continuar a percorrer cada elemento da matriz a fim de confirmar que é, Na verdade, o elemento mais pequeno. 

Então, o pior caso de tempo de execução, que tem que repetir um processo n vezes, uma vez para cada um dos n elementos. E na melhor das hipóteses, nós temos que fazer o mesmo. 

Então, pensando de volta ao nosso toolbox complexidade computacional, o que você acha que é o pior caso de tempo de execução para a seleção tipo? O que você acha que é o melhor caso de tempo de execução para a seleção tipo? 

Será que você adivinha Big O de n ao quadrado, e Big Omega de n ao quadrado? Você estaria certo. Estes são, na verdade, o pior caso e melhor caso de execução vezes, para seleção de tipo. 

Eu sou Doug Lloyd. Este é CS50.