[Powered by Google Translate] [Ordenar Inserción]
[Tommy MacWilliam] [Harvard University]
[Esta es CS50.TV]
Vamos a echar un vistazo a la ordenación por inserción, un algoritmo para la toma de una lista de números y ordenarlos.
Un algoritmo, recuerde, es simplemente un procedimiento paso a paso para realizar una tarea.
La idea básica detrás de la ordenación por inserción, es dividir la lista en dos partes,
una porción ordenados y una porción sin clasificar.
>> En cada paso del algoritmo, un número se mueve
desde la parte no seleccionada a la porción ordenados
hasta que finalmente toda la lista está ordenada.
Esta es la lista de seis números no clasificados - 23, 42, 4, 16, 8, y 15.
Dado que estos números no son todo en orden ascendente, están sin ordenar.
Puesto que no hemos empezado clasificación, sin embargo, vamos a considerar los seis elementos de nuestra parte sin clasificar.
>> Una vez que comenzamos la clasificación, vamos a poner estos números ordenados a la izquierda de las mismas.
Por lo tanto, vamos a empezar con 23, el primer elemento de la lista.
No tenemos ningún elemento de nuestra parte ordenados, sin embargo,
así que vamos a considerar sólo 23 al ser el inicio y el final de nuestra parte ordenada.
Ahora, nuestra porción ordenada tiene un número, 23,
y de nuestra parte no seleccionada tiene estos cinco números.
Ahora vamos a insertar el siguiente número de nuestra parte sin clasificar, de 42 años, en la parte ordenada.
>> Para ello, tendremos que comparar la 42 a la 23 - el único elemento en nuestra porción ordenados hasta ahora.
Cuarenta y dos es mayor que 23, por lo que simplemente puede añadir 42 hasta el final
de la parte ordenada de la lista. Great!
Ahora nuestra parte según consta de dos elementos, y nuestra parte no seleccionada tiene cuatro elementos.
Por lo tanto, vamos a pasar ahora a la 4, el siguiente elemento de la parte sin clasificar.
Así, donde debe ser colocado en esta porción de la ordenados?
>> Recuerde, queremos poner este número en forma ordenada
por lo que nuestra porción ordenados permanece correctamente ordenados en todo momento.
Si colocamos la 4 a la derecha de los 42, entonces nuestra lista estará fuera de orden.
Por lo tanto, vamos a continuar moviéndose de derecha a izquierda en nuestra porción de clasificación.
A medida que avanzamos, vamos a pasar por cada número un lugar para hacer espacio para el nuevo número.
Vale, 4 también es inferior a 23, por lo que no se puede colocar aquí tampoco.
Vamos a pasar el 23 a la derecha un solo lugar.
>> Eso significa que nos gustaría poner el 4 en la primera ranura en la parte ordenada.
Observe cómo este espacio en la lista ya estaba vacía,
porque hemos estado moviendo elementos ordenados a medida que los hemos encontrado.
Está bien. Por lo tanto, estamos a mitad de camino.
Vamos a continuar nuestro algoritmo mediante la inserción de la 16 a la parte ordenada.
Dieciséis es menos de 42, así que vamos a pasar el 42 a la derecha.
Dieciséis es también menos de 23, así que vamos a cambiar también ese elemento.
>> Ahora, 16 es mayor que 4. Por lo tanto, parece que nos gustaría insertar la 16 entre el 4 y 23 de la.
Mientras se mueve a través de la porción de la lista ordenada de derecha a izquierda,
4 es el primer número hemos visto que es menor que el número
estamos tratando de insertar.
Por lo tanto, ahora podemos insertar los 16 en esta ranura vacía,
que, recordemos, hemos creado por elementos en movimiento en la parte de tipo más
como los hemos encontrado.
>> Está bien. Ahora, tenemos cuatro elementos ordenados y dos elementos no ordenados.
Por lo tanto, vamos a pasar el 8 en la parte ordenada.
Ocho es inferior a 42.
Ocho es menos de 23.
Y 8 es menor que 16.
Pero 8 es mayor que 4.
Por lo tanto, nos gustaría introducir el 8 entre el 4 y el 16.
Y ahora sólo tenemos un elemento más a la izquierda para ordenar - el 15.
Quince es inferior a 42,
Quince es menos de 23.
Y 15 es menor que 16.
Pero 15 es mayor que 8.
>> Así pues, aquí es donde queremos que nuestra inserción final.
Y hemos terminado.
No tenemos más elementos en la porción sin clasificar,
y nuestra porción ordenados en el orden correcto.
Los números están ordenados de menor a mayor.
Por lo tanto, echemos un vistazo a algunos pseudocódigo que describe los pasos que acabamos de realizar.
>> En la línea 1, podemos ver que vamos a necesitar para iterar sobre cada elemento de la lista
excepto el primero, ya que el primer elemento en la parte no seleccionada se hará simplemente
el primer elemento en la parte ordenados.
En las líneas 2 y 3, estamos manteniendo un seguimiento de nuestra posición actual en la parte sin clasificar.
Elemento representa el número que se está moviendo en la parte de clasificados,
y j representa nuestro índice en la parte sin clasificar.
>> En la línea 4, estamos iterando a través de la porción ordenados de derecha a izquierda.
Queremos dejar de iterar una vez que el elemento a la izquierda de su posición actual
es menor que el elemento que estamos tratando de insertar.
En la línea 5, estamos cambiando cada elemento que encontramos un espacio a la derecha.
De esta manera, vamos a tener un espacio libre para insertar en cuando nos encontramos con el primer elemento
menor que el elemento que se está moviendo.
En la línea 6, estamos actualizando nuestro contador a continuar moviéndose a la izquierda por la parte ordenada.
Por último, en la línea 7, estamos insertar el elemento dentro de la parte de la lista ordenada.
>> Sabemos que está bien para insertar en la posición j,
porque ya hemos movido el elemento que solía estar allí un espacio a la derecha.
Recuerde, nos estamos moviendo a través de la porción ordenados de derecha a izquierda,
pero nos estamos moviendo a través de la parte no seleccionada de izquierda a derecha.
Está bien. Echemos un vistazo a cómo de larga data que se algoritmo.
En primer lugar, voy a hacer la pregunta ¿cuánto tiempo se necesita para que este algoritmo se ejecute en el peor de los casos.
Recordemos que representamos esta vez corriendo con la notación grande O.
Para ordenar la lista, tuvimos que iterar sobre los elementos de la parte sin clasificar,
y para cada uno de esos elementos, potencialmente a través de todos los elementos en la porción ordenados.
Intuitivamente, esto suena como una operación O (n ^ 2).
>> En cuanto a nuestro pseudocódigo, tenemos un bucle anidado dentro de otro bucle,
que, de hecho, suena como una operación O (n ^ 2).
Sin embargo, la parte ordenada de lista no contenía toda la lista hasta el final.
Aún así, podría insertar un nuevo elemento en el comienzo mismo de la porción ordenados
en cada iteración del algoritmo,
lo que significa que tendríamos que mirar cada elemento actualmente en la parte ordenada.
Por lo tanto, esto significa que potencialmente podría hacer una comparación para el segundo elemento,
dos comparaciones para el tercer elemento, y así sucesivamente.
Así, el número total de pasos es la suma de los enteros de 1 a la longitud de la lista menos 1.
Podemos representar esto con una suma.
>> No vamos a entrar en sumas aquí, pero resulta que esta suma es igual a
n (n - 1) sobre 2, que es equivalente n ^ 2/2 - n / 2.
Cuando se habla de tiempo de ejecución asintótico,
este n ^ 2 plazo va a dominar este término n.
Por lo tanto, la ordenación por inserción es Big O (n ^ 2).
¿Qué pasa si nos quedamos ordenación por inserción en una lista ya ordenada.
En ese caso, simplemente se había acumulación de la porción ordenados de izquierda a derecha.
Así que lo único que necesita del orden de n pasos.
>> Esto significa que la ordenación por inserción tiene un rendimiento mejor de los casos de n,
que representamos con Ω (n).
Y eso es todo por tipo de inserción,
sólo uno de los muchos algoritmos que se pueden utilizar para ordenar una lista.
Mi nombre es Tommy, y esto es CS50.
[CS50.TV]
Oh, no puedes dejar que una vez que se inicie.
Oh, lo hicimos - Boom! >>