[Música tocando] 

Doug LLOYD: Entón ordenación por inserción é outro algoritmo que podemos utilizar para clasificar unha matriz. A idea detrás deste algoritmo é construír a súa matriz clasificada no lugar, desprazando elementos de a forma como vai, para facer o cuarto. Esta é lixeiramente diferente tipo de selección ou burbulla tipo, por exemplo, onde estamos axustando os locais, onde estamos facendo swaps. 

Neste caso, o que somos, en realidade, facendo é elementos de deslizamento máis, para fóra do camiño. Como é que este algoritmo traballar en pseudocódigo? Ben, imos só dicir que o arbitrariamente primeiro elemento da matriz é clasificada. Estamos construíndo-lo no lugar. 

Nós imos ir un elemento de cada vez e constrúe-lo, e por iso o primeiro que vemos é unha matriz de un elemento. E, por definición, un elemento da matriz está clasificada. 

Entón nós imos repetir este proceso until-- imos repetir o proceso a seguir ata que todos os elementos son clasificados. Olle para o seguinte elemento sen clasificar e inserir-lo na porción clasificada, desprazándose o número necesario de elementos fóra do camiño. Esperemos que esta visualización vai axudar a ver o que está pasando con ordenación por inserción. 

Entón, de novo, aquí está a nosa toda matriz non clasificado, todos os elementos indicados en vermello. E imos seguir o pasos do noso pseudocódigo. O primeiro que facemos, é o que chamamos primeiro elemento da matriz, clasificados. Entón, nós estamos só vou dicir cinco, está agora clasificada. 

Entón, miramos para a próxima indiferenciados elemento da matriz e queremos que inserir na porción clasificados, desprazando elementos máis. Entón, dous é a seguinte indiferenciados elemento da matriz. Claramente, antes da pertenza cinco, entón o que nós imos facer é unha especie de realizar dúas de lado por un segundo, cambiar ao longo de cinco, e logo insira dous antes das cinco, onde debe ir. E agora podemos dicir que dous está clasificada. 

Entón, como podes ver, temos só ata agora mirou dous elementos do array. Non mirou para o descansar en todo, pero nós temos teño eses dous elementos clasificados por camiño do mecanismo de cambio. 

Por iso, repita o proceso de novo. Olhe a próxima sen clasificar elemento, que é un. Imos manter isto de lado por un segundo, cambiar todo máis, e poñer unha onde debe ir. 

De novo, aínda, temos sempre só mirou para un, dous, e cinco. Non sabemos o que máis está por vir, pero temos ordenados eses tres elementos. 

Preto elemento é sen clasificar tres, así que imos define-lo de lado. Nós imos cambiar co que nós precisa para que, desta vez non é todo como no precedente dous casos, é só a cinco. E entón nós imos estar tres, entre os dous e os cinco. 

Seis é o seguinte sen clasificar elemento para a matriz. E, de feito, seis é superior a cinco, así nós nin sequera que facer calquera cambio. Podemos só alinhavar seis da dereita para o extremo da porción clasificados. 

Para rematar, é a catro último elemento indiferenciado. Entón, imos define-lo de lado, cambiar ao longo os elementos que precisa cambiar máis, e logo poñer catro onde pertence. E agora mira, temos sorte de todos os elementos. Observe con inserción tipo, nós non temos para ir e volver do outro lado da matriz. Nós só fomos fronte á matriz Unha vez máis, e cambiamos as cousas que xa atopara, a fin para dar espazo para os novos elementos. 

Entón, cal é o peor caso escenario con ordenación por inserción? No peor dos casos, o matriz é na orde inversa. Ten que cambiar cada un dos elementos n ata n posicións, cada vez que facer unha inserción. Iso é unha chea de cambio. 

No mellor dos casos, o matriz é perfectamente ordenadas. E máis ou menos como o que pasou con cinco e seis no exemplo, onde se pode só alinhavar-lo no sen ter que facer ningún cambio, teremos esencialmente facelo. 

Se imaxinar que a nosa matriz era dun a seis, nós comezar por declarando un é clasificado. Dous vén despois dun para que poidamos só dicir, OK, así un e dous son clasificadas. Tres vén despois de dous, así, OK, un e dous e tres son clasificadas. 

Non estamos facendo ningún swaps, estamos só movendo esta liña arbitraria entre clasificadas e sen clasificar como imos nós. De forma tan eficaz como fixemos no exemplo, transformando elementos azul, a medida que proseguimos. Entón, cal é o peor caso de tempo de execución, entón? Teña en conta que, se temos que cambiar cada un dos os n elementos posiblemente n posicións, espero que lle dá unha idea que o peor caso O tempo de execución é grande de n ao cadrado. 

Se a matriz é perfectamente clasificadas, todos temos que facer é mirar para cada elemento Unha vez máis, e, a continuación, estamos a facer. Así, no mellor dos casos, é omega de n. 

Eu son Doug Lloyd. Este é CS50.