>> [Música tocando]
>> DOUG LLOYD: Então ordenação por inserção é outro algoritmo que podemos usar para classificar uma matriz.
A idéia por trás deste algoritmo é construir a sua matriz classificada
no lugar, deslocando elementos de a maneira como você vai, para fazer o quarto.
Esta é ligeiramente diferente tipo de seleção ou bolha
tipo, por exemplo, onde nós estamos ajustando os locais,
onde nós estamos fazendo swaps.
>> Neste caso, o que nós somos, na verdade, fazendo é elementos de deslizamento
mais, para fora do caminho.
Como é que este algoritmo trabalhar em pseudocódigo?
Bem, vamos apenas dizer que o arbitrariamente primeiro elemento da matriz é classificada.
Estamos construindo-lo no lugar.
>> Nós vamos ir um elemento de cada vez e construí-lo, e por isso a primeira coisa que vemos
é uma matriz de um elemento.
E, por definição, um elemento da matriz está classificada.
>> Então nós vamos repetir esse processo until-- vamos repetir o processo a seguir
até que todos os elementos são classificados.
Olhe para o próximo elemento não triados e inseri-lo na porção classificada,
deslocando-se o número necessário de elementos fora do caminho.
Esperemos que esta visualização vai ajudá-lo a ver exatamente o que está
acontecendo com ordenação por inserção.
>> Então, novamente, aqui está a nossa toda matriz não classificado,
todos os elementos indicados em vermelho.
E vamos seguir o passos do nosso pseudocódigo.
A primeira coisa que fazemos, é o que chamamos primeiro elemento da matriz, classificados.
Então, nós estamos só vou dizer cinco, você está agora classificada.
>> Então, olhamos para a próxima indiferenciados elemento da matriz
e nós queremos que inserir na porção classificados,
deslocando elementos mais.
Então, dois é a próxima indiferenciados elemento da matriz.
Claramente, antes da pertence cinco, então o que nós vamos fazer
é uma espécie de realizar duas de lado por um segundo, mudar ao longo de cinco, e em seguida, insira dois
antes das cinco, para onde deve ir.
E agora podemos dizer que dois está classificada.
>> Então, como você pode ver, nós temos somente até agora olhou para dois elementos do array.
Nós não olhou para o descansar em tudo, mas nós temos
tenho esses dois elementos classificados por caminho do mecanismo de mudança.
>> Por isso, repita o processo novamente.
Olhe para a próxima não triados elemento, que é um.
Vamos manter isso de lado por um segundo, mudar tudo mais, e colocar uma
onde ele deve ir.
>> Novamente, ainda, temos sempre apenas olhou para um, dois, e cinco.
Nós não sabemos o que mais está por vir, mas temos ordenados esses três elementos.
>> Próximo elemento é não triados três, por isso vamos defini-lo de lado.
Nós vamos mudar com o que nós precisa para que, desta vez
não é tudo como no precedente dois casos, é apenas a cinco.
E então nós vamos ficar três, entre os dois e os cinco.
>> Seis é o próximo não triados elemento para a matriz.
E, de facto, seis é superior a cinco, assim nós nem sequer precisa fazer qualquer troca.
Podemos apenas alinhavar seis à direita para a extremidade da porção classificados.
>> Por último, é a quatro último elemento indiferenciado.
Então, vamos defini-lo de lado, mudar ao longo os elementos que precisa mudar mais,
e em seguida, colocar quatro onde ele pertence.
E agora olha, nós temos sorte de todos os elementos.
Observe com inserção tipo, nós não temos
para ir e voltar do outro lado da matriz.
Nós só fomos em frente à matriz uma vez, e mudamos as coisas
que já tinha encontrado, a fim para dar espaço para os novos elementos.
>> Então, qual é o pior caso cenário com ordenação por inserção?
No pior dos casos, o matriz é na ordem inversa.
Você tem que mudar cada um dos elementos n até n posições, cada vez que
fazer uma inserção.
Isso é um monte de mudança.
>> No melhor dos casos, o matriz é perfeitamente ordenadas.
E mais ou menos como o que aconteceu com cinco e seis no exemplo,
onde se pode apenas alinhavar-lo no sem ter que fazer qualquer mudança,
teremos essencialmente fazer isso.
>> Se você imaginar que a nossa matriz era de um a seis,
nós começar por declarando um é classificado.
Dois vem após um para que possamos apenas dizer, OK, bem um e dois são classificadas.
Três vem depois de dois, assim, OK, um e dois e três são classificadas.
>> Nós não estamos fazendo nenhum swaps, estamos apenas movendo essa linha arbitrária
entre classificadas e não triados como vamos nós.
De forma tão eficaz como fizemos no exemplo, transformando elementos azul, à medida que prosseguimos.
Então, qual é o pior caso de tempo de execução, então?
Lembre-se, se tivermos que mudar cada um dos os n elementos possivelmente n posições,
espero que lhe dá uma idéia que o pior caso
O tempo de execução é grande de n ao quadrado.
>> Se a matriz é perfeitamente classificadas, todos nós temos que fazer
é olhar para cada elemento uma vez, e, em seguida, estamos a fazer.
Assim, na melhor das hipóteses, é omega de n.
>> Eu sou Doug Lloyd.
Este é CS50.