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