[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.