[Powered by Google Translate] [Ordenar Inserção]
[Tommy MacWilliam] [Harvard University]
[Esta é CS50.TV]
Vamos dar uma olhada no tipo de inserção, um algoritmo para a tomada de uma lista de números e classificando-os.
Um algoritmo, lembre-se, é simplesmente um procedimento passo-a-passo para a realização de uma tarefa.
A idéia básica por trás do tipo de inserçã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 porção não triados para a porção classificada
até que finalmente toda a lista é ordenada.
Aqui está a lista de seis números indiferenciados - 23, 42, 4, 16, 8 e 15.
Uma vez que estes números não são tudo em ordem ascendente, eles estão sem classificação.
Desde que não começou ainda a classificação, vamos considerar todos os seis elementos a nossa parte indiferenciados.
>> Assim que iniciar a classificação, vamos colocar esses números classificados para a esquerda destes.
Então, vamos começar com 23, o primeiro elemento em nossa lista.
Nós não temos todos os elementos de nossa parte classificada ainda,
então vamos simplesmente considerar 23 seja o início eo fim de nossa parte classificados.
Agora, a nossa parte ordenada possui um número, 23,
e nossa porção indiferenciados tem esses cinco números.
Vamos agora inserir o próximo número na nossa porção indiferenciados, 42, na porção classificados.
>> Para isso, vamos precisar de comparar a 42 para o 23 - o único elemento em nossa parcela classificada até agora.
Quarenta e dois é maior do que 23, então podemos simplesmente acrescentar 42 até o fim
da porção da lista ordenada. Ótimo!
Agora a nossa parte ordenada possui dois elementos, e nossa porção indiferenciados tem quatro elementos.
Então, vamos agora passar para a 4, o elemento seguinte na parte indiferenciados.
Assim, onde deve esta ser colocada na parte classificada?
>> Lembre-se, nós queremos colocar esse número na ordem de classificação
por isso a nossa parte permanece classificada corretamente classificados em todos os momentos.
Se colocarmos a 4 para a direita dos 42, então a nossa lista vai ser fora de ordem.
Então, vamos continuar a mover da direita para a esquerda na nossa porção tipo.
À medida que avançamos, vamos mudar cada número abaixo de um lugar para dar espaço para o novo número.
Ok, 4 também é menor que 23, portanto, não podemos colocá-lo aqui também.
Vamos passar a 23 um lugar certo.
>> Isso significa que nós gostaríamos de colocar o 4 no primeiro buraco na parte de classificados.
Observe como esse espaço na lista já estava vazio,
porque estamos movendo elementos classificados para baixo como nós encontramos eles.
Tudo bem. Então, nós estamos no meio do caminho.
Vamos continuar o nosso algoritmo, inserindo a 16 na porção classificados.
Dezesseis é menor do que 42, então vamos mudar o 42 para a direita.
Dezesseis também é menor do que 23, então vamos também mudar esse elemento.
>> Agora, 16 é maior do que 4. Então, parece que gostaria de inserir a 16 entre o 4 eo 23.
Enquanto se move através da parte classificada da lista da direita para a esquerda,
4 é o primeiro número que vimos que é menor do que o número
estamos tentando inserir.
Então, agora nós podemos inserir o 16 neste slot vazio,
que, lembre-se, nós criamos por elementos móveis na parte de tipo mais
como nós encontramos eles.
>> Tudo bem. Agora, temos quatro elementos classificados e dois elementos não ordenados.
Então, vamos passar a 8 na porção classificados.
Oito é inferior a 42.
Oito é inferior a 23.
E 8 é menor do que 16.
Mas 8 é maior do que 4.
Então, nós gostaríamos de inserir a 8 entre o 4 eo 16.
E agora só temos mais um elemento para a esquerda para classificar - o 15.
Quinze é inferior a 42,
Quinze é inferior a 23.
E 15 é menor do que 16.
Mas 15 é maior do que 8.
>> Então, aqui é onde nós queremos fazer a nossa inserção final.
E estamos a fazer.
Nós não temos mais elementos na parte indiferenciados,
e nossa parte é classificada na ordem correta.
Os números são ordenados do menor para o maior.
Então, vamos dar uma olhada em alguns pseudocódigo que descreve os passos que acabou de realizar.
>> Na linha 1, podemos ver que nós vamos precisar iterar sobre cada elemento da lista
exceptuando o primeiro, uma vez que o primeiro elemento na porção não triados será simplesmente
o primeiro elemento na porção classificada.
Nas linhas 2 e 3, estamos mantendo o controle de nosso lugar atual na parte indiferenciados.
Elemento representa o número que estamos actualmente a passar para a parte de classificados,
e j representa o nosso índice para a parte indiferenciados.
>> Na linha 4, estamos interagindo através da parte ordenada da direita para a esquerda.
Queremos parar a iteração uma vez que o elemento para a esquerda de nossa posição atual
é menor do que o elemento que estamos tentando inserir.
Na linha 5, nós estamos mudando cada elemento que encontramos um espaço para a direita.
Dessa forma, nós vamos ter um espaço livre para inserir em quando encontramos o primeiro elemento
menos do que o elemento que estamos nos movendo.
Na linha 6, estamos atualizando nosso contador para continuar a mover para a esquerda através da parte classificados.
Finalmente, na linha 7, que está inserindo o elemento dentro da porção da lista ordenada.
>> Sabemos que não há problema em inserir em posição j,
porque já mudou o elemento que costumava ser há um espaço para a direita.
Lembre-se, estamos nos movendo através da parte ordenada da direita para a esquerda,
mas estamos nos movendo através da parte indiferenciados da esquerda para a direita.
Tudo bem. Vamos agora dar uma olhada em como o algoritmo de longa duração que tomou.
Vamos primeiro fazer a pergunta quanto tempo leva para este algoritmo para executar no pior caso.
Lembre-se que nós representamos desta vez correndo com notação Big.
A fim de resolver a nossa lista, nós tivemos que iterar sobre os elementos na parte indiferenciados,
e para cada um desses elementos, potencialmente mais de todos os elementos na porção classificada.
Intuitivamente, isso soa como uma operação de O (n ^ 2).
>> Olhando para o nosso pseudocódigo, temos um loop aninhado dentro de outro loop,
que, na verdade, soa como uma operação de O (n ^ 2).
No entanto, a parte ordenada de lista não continha toda a lista até o fim.
Ainda assim, poderíamos potencialmente inserir um novo elemento no início da porção classificada
a cada iteração do algoritmo,
o que significa que teríamos de olhar para cada elemento atualmente na parte de classificados.
Então, isso significa que poderia, potencialmente, fazer uma comparação para o segundo elemento,
duas comparações para o terceiro elemento, e assim por diante.
Assim, o número total de passos é a soma dos números inteiros de 1 até o comprimento da lista menos 1.
Podemos representar isso com um somatório.
>> Nós não vamos entrar em somatórios aqui, mas acontece que esta soma é igual a
n (n - 1) ao longo de 2, o que é equivalente n ^ 2/2 - n / 2.
Quando se fala em tempo de execução assintótico,
isso n ^ 2 termo vai dominar este termo n.
Então, tipo de inserção é Big O (n ^ 2).
E se corremos tipo de inserção em uma lista já classificada.
Nesse caso, nós simplesmente construir a porção ordenadas da esquerda para a direita.
Então, a gente só precisa da ordem de n passos.
>> Isso significa que esse tipo de inserção tem um desempenho melhor caso de n,
que representamos com Ω (n).
E é isso por tipo de inserção,
apenas um dos muitos algoritmos que podem ser usados ​​para classificar uma lista.
Meu nome é Tommy, e este é o CS50.
[CS50.TV]
Oh, você não pode impedir que uma vez iniciado.
Oh, nós fizemos isso - Boom! >>