>> [REPRODUCCIÓN DE MÚSICA]
>> DOUG LLOYD: Así ordenación por inserción es otro algoritmo que puede utilizar para ordenar una matriz.
La idea detrás de este algoritmo es la construcción de su matriz ordenada
en su lugar, los elementos de desplazamiento de el camino a medida que avanza, para hacer espacio.
Esto es ligeramente diferente desde la selección del tipo o de la burbuja
Ordena, por ejemplo, donde estamos ajustando los lugares,
donde estamos haciendo swaps.
>> En este caso lo que somos en realidad haciendo es elementos deslizantes
otra vez, fuera del camino.
¿Cómo funciona este algoritmo trabajar en pseudocódigo?
Bueno vamos a decir simplemente que la forma arbitraria primer elemento de la matriz se ordena.
Estamos construyendo en su lugar.
>> Vamos a ir un elemento a la vez y construirlo, por lo que la primera cosa que vemos
es una matriz de un elemento.
Y, por definición, una elemento de la matriz se ordena.
>> Entonces vamos a repetir este proceso until-- vamos a repetir el siguiente proceso
hasta que todos los elementos son ordenados.
Mira el siguiente elemento no seleccionados y insertarlo en la parte ordenada,
desplazando el número requerido de elementos fuera del camino.
Esperemos que esta visualización le ayudará a ver exactamente lo que está
pasando con la ordenación por inserción.
>> Así que de nuevo, aquí está nuestra toda variedad sin clasificar,
todos los elementos indicados en rojo.
Y vamos a seguir la pasos de nuestra pseudocódigo.
La primera cosa que hacemos, se nos llama a la primer elemento de la matriz, ordenados.
Así que sólo vamos a decir cinco, ahora eres ordenados.
>> Entonces nos fijamos en la siguiente elemento sin clasificar de la matriz
y queremos insertar ese en la porción ordenados,
por elementos de desplazamiento sobre.
Así que dos es la siguiente sin clasificar elemento de la matriz.
Es evidente que pertenece antes de la cinco, así que lo que vamos a hacer
es una especie de sostener de dos de lado por un segundo, cambiar de cinco más, y después inserte de dos
antes de las cinco, dónde debe ir.
Y ahora podemos decir que dos se ordena.
>> Así como usted puede ver, sólo hemos hasta ahora mirado dos elementos de la matriz.
No hemos mirado el descansamos en absoluto, sino que hemos
consiguieron esos dos elementos ordenados por camino del mecanismo de cambio.
>> Así que repetimos el proceso de nuevo.
Mira la siguiente sin clasificar elemento, que es uno.
Vamos a celebrar eso a un lado por un segundo, cambiar todo lo más, y poner uno
donde debe ir.
>> Una vez más, aún así, sólo he miró a uno, dos y cinco.
No sabemos qué más está por venir, pero hemos solucionaron esos tres elementos.
>> Elemento sin clasificar siguiente es tres, por lo que vamos a establecer a un lado.
Nos desplazamos sobre lo que necesitará que, esta vez
no lo es todo como en el anterior dos casos, es sólo el cinco.
Y entonces nos mantendremos tres en, entre los dos y los cinco.
>> Seis es el siguiente sin clasificar elemento a la matriz.
Y de hecho seis es superior a cinco, por lo que ni siquiera necesitamos hacer ningún intercambio.
Sólo podemos virar y seis a la derecha en el extremo de la porción ordenados.
>> Por último, cuatro es el último elemento sin clasificar.
Así que vamos a establecer un lado, cambiamos más los elementos que tienen que cambiar a lo largo,
y luego poner las cuatro que le corresponde.
Y ahora mira, tenemos una especie de todos los elementos.
Aviso de la inserción especie, no teníamos
para ir y venir a través de la matriz.
Nosotros sólo fuimos a través de la matriz una sola vez, y nos cambió las cosas
que ya habíamos encontrado, con el fin para dar cabida a los nuevos elementos.
>> ¿Cuál es el peor de los casos escenario con la ordenación por inserción?
En el peor de los casos, la array es en orden inverso.
Usted tiene que cambiar cada uno de los n elementos hasta n posiciones, todos tenemos una sola vez
hacer una inserción.
Eso es un montón de cambiar.
>> En el mejor de los casos, la matriz está perfectamente ordenadas.
Y algo así como lo que pasó con cinco y seis en el ejemplo,
en el que sólo podíamos virar en sin tener que hacer ningún cambio,
que esencialmente haríamos eso.
>> Si usted se imagina que nuestro matriz fue del uno al seis,
nos gustaría empezar por declarando un solo está ordenada.
Dos viene después de que uno por lo que puede simplemente dicen, OK, bueno uno y dos son ordenados.
Tres viene después de dos, así, está bien, uno y dos y tres están ordenados.
>> No estamos haciendo ningún swaps, estamos sólo mover esta línea arbitraria
entre clasificados y no clasificados a medida que avanzamos.
Como efectivamente como lo hicimos en el ejemplo, convertir elementos azul, a medida que avancemos.
Entonces, ¿qué es lo peor de ejecución caso, entonces?
Recuerde, si tenemos que cambiar cada uno de los n elementos posiblemente n posiciones,
espero que te da una idea de que el peor de los casos
tiempo de ejecución es O grande de n al cuadrado.
>> Si la matriz es perfectamente ordenado, todo lo que tenemos que hacer
es mirar a cada elemento una vez, y luego hemos terminado.
Así que en el mejor de los casos, es el omega de n.
>> Soy Doug Lloyd.
Esto es CS50.