[Powered by Google Translate] TOMMY: Vamos dar uma olhada tipo de seleção, um algoritmo para a tomada de uma lista de números e classificando-os. Um algoritmo, lembre-se, é simplesmente um passo-a-passo procedimento para realizar uma tarefa. A idéia básica por trás do tipo de seleção é dividir nossa lista em duas partes - uma parte ordenada e uma porção indiferenciados. Em cada etapa do algoritmo, um número é movido a partir da parte indiferenciados para a porção classificados até, eventualmente, o lista completa está classificada. Então aqui está uma lista de seis números - 23, 42, 4, 16, 8, e 15. Agora toda a lista é considerada sem classificação. Mesmo que um número como 16 já pode estar em sua correcta localização, nosso algoritmo tem nenhuma maneira de saber que até o lista completa está classificada. Então, vamos considerar cada número a ser triados até classificar nós mesmos. Nós sabemos que queremos a lista para estar em ordem crescente. Então, nós vamos querer construir a parte ordenada da nossa lista da esquerda para a direita, a menor para o maior. Para isso, vamos precisar de encontrar o elemento mínimo indiferenciados e colocá-lo no fim da porção classificada. Como esta lista não está ordenada, a única maneira de fazer isso é olhar para cada elemento na porção não separados, lembrando qual elemento é a mais baixa e comparando cada elemento a que. Então, vamos olhar primeiro para o 23. Este é o primeiro elemento que temos visto, por isso vamos lembrar como o mínimo. Em seguida, vamos olhar para 42. 42 é maior do que 23, então 23 é ainda o mínimo. O próximo é o 4, que é inferior a 23, por isso vamos lembrar 4 como o novo mínimo. Em seguida é 16, que é maior do que 4, então 4 ainda é o mínimo. 8 é maior do que 4, e 15 é maior do que 4, então 4 deve ser o menor elemento indiferenciado. Assim, mesmo que, como seres humanos, podemos ver imediatamente que 4 é o elemento mínimo, o algoritmo precisa de olhar para cada elemento indiferenciado, mesmo depois de ter encontrado a 4 - o elemento mínimo. Portanto, agora que nós encontramos o elemento mínimo, 4, vamos querer para movê-la para dentro da porção da lista ordenada. Uma vez que este é o primeiro passo, isso significa que queremos colocar em 4 o início da lista. Nesse momento 23 é, no início da lista, de modo Vamos trocar o 4 eo 23. Então, agora a nossa lista parecida com esta. Sabemos que 4 tem de ser na sua posição final, uma vez que é tanto o elemento mais pequeno eo elemento no início da lista. Então isso significa que não precise mover novamente. Então, vamos repetir esse processo para adicionar mais um elemento para a parcela classificada da lista. Nós sabemos que não precisamos de olhar para o 4, porque é já estão classificados. Assim, podemos começar no 42, que vai se lembrar de como a elemento mínimo. Então, da próxima vamos olhar para o 23, que é menor do que 42, então nós lembrar 23 é o novo mínimo. Em seguida, vemos a 16 que é inferior a 23, de modo 16 é o novo mínimo. Agora vamos examinar o 8 que é menos do que 16, então 8 é o novo mínimo. E finalmente 8 é inferior a 15, de modo que sabemos que 8 é um mínimo elemento indiferenciado. Então isso significa que devemos acrescentar 8 ao ordenadas porção da lista. Agora 4 é o único elemento classificados, por isso queremos colocar o próximo dia 8 para o 4. Uma vez que 42 é o primeiro elemento na porção não separados do lista, vamos querer trocar o 42 eo 8. Então, agora a nossa lista parecida com esta. 4 e 8 representam a parcela classificada da lista, eo números restantes representam a indiferenciados porção da lista. Então, vamos continuar com outro iteração. Começamos com 23 desta vez, já que não precisa de olhar para o 4 eo 8 mais, porque eles têm já foram classificados. 16 é menor que 23, portanto, nós nos lembraremos 16, tal como o novo mínimo. 16 é menor do que 42, mas 15 é menor do que 16, então deve ser 15 o elemento mínimo indiferenciados. Então, agora queremos trocar os 15 e os 23 a nos dar esta lista. A porção da lista ordenada é constituída por 4, 8 e 15, e esses elementos estão ainda sem classificação. Mas acontece que o próximo elemento indiferenciado, 16, já está classificado. No entanto, não há nenhuma maneira para o nosso algoritmo para saber que 16 já está em seu local correto, então ainda precisamos repetir exatamente o mesmo processo. Portanto, vemos que 16 é menos de 42, e 16 é menor que 23, então 16 deve ser o elemento mínimo. É impossível trocar esse elemento com ele mesmo, para que possamos simplesmente deixá-lo no local. Então precisamos de uma passagem mais do nosso algoritmo. 42 é maior que 23, então 23 deve ser o indiferenciados elemento mínimo. Uma vez que trocar os 23 e os 42, vamos acabar com nossa final lista de classificados - 4, 8, 15, 16, 23, 42. Sabemos 42 deve estar no lugar correto, já que é o único elemento à esquerda, e que é uma espécie de seleção. Vamos agora formalizar o nosso algoritmo com algum pseudocódigo. Em uma linha, podemos ver que precisamos integrar mais cada elemento da lista. Excepto o último elemento, uma vez que o elemento 1 lista já está classificado. Na linha dois, consideramos que o primeiro elemento da unsorted parte da lista para ser o mínimo, como fizemos com a nossa exemplo, de modo que temos algo para comparar. Linha de três começa uma segunda volta em que iterar cada elemento indiferenciado. Sabemos que, depois de iterações, a parte classificada da nossa lista deve ter i elementos nele desde cada passo tipo um elemento. Assim, o primeiro elemento unsorted deve estar na posição i + 1. Na linha de quatro, comparamos o elemento atual para o mínimo elemento que temos visto até agora. Se o elemento de corrente é menor do que o mínimo elemento, então lembre-se o elemento atual como o novo mínima na linha cinco. Finalmente, em linhas seis e sete, trocamos o mínimo elemento com o primeiro elemento não separados, assim adicionando-a a porção da lista ordenada. Uma vez que temos um algoritmo, uma importante causa de pedir nós como programadores é quanto tempo isso leva? Vamos primeiro fazer a pergunta quanto tempo leva para essa algoritmo para executar no pior caso? Lembro que representam esta corrida tempo com notação O grande. A fim de determinar o elemento mínimo indiferenciados, nós tinha essencialmente para comparar cada elemento da lista de todos os outros elementos da lista. Intuitivamente, isso soa como um O de n operação quadrado. Olhando para o nosso pseudocódigo, também temos um loop aninhado outro ciclo, que na verdade soa como um O operação de n ao quadrado. No entanto, lembre-se que nós não precisamos de olhar sobre o lista completa para determinar o elemento mínimo indiferenciados? Uma vez que sabia que o 4 foi classificada, por exemplo, nós não precisa olhar para ele de novo. Então isso menor o tempo de execução? Para a nossa lista de comprimento 6, é necessário fazer cinco comparações para o primeiro elemento, quatro comparações para o segundo elemento, e assim por diante. Isso significa que o número total de passos é igual à soma de os números inteiros de 1 até o comprimento da lista de menos 1. Podemos representar isso com um somatório. Nós não vamos entrar em somatórios aqui. Mas acontece que essa soma é igual a n vezes n menos 1 sobre 2. Ou equivalentemente, n ao quadrado mais 2 menos n mais de 2. Quando se fala em tempo de execução assintótico, este termo n ao quadrado vai dominar este termo n. Então tipo de seleção é O de n ao quadrado. Lembre-se que no nosso exemplo, tipo de seleção ainda precisava verificar se um número que já foi classificada necessária para ser movido. Então isso significa que, se correu tipo de seleção sobre uma já lista classificada, seria necessário o mesmo número de passos, uma vez que faria ao atropelar uma lista completamente indiferenciado. Então tipo de seleção tem um desempenho melhor caso de n ao quadrado, que representamos com ômega n ao quadrado. E é isso por tipo de seleção. Apenas um dos muitos algoritmos que podemos usar para classificar uma lista. Meu nome é Tommy, e este é o CS50.