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