Contenido principal
Curso: Ciencias de la computación > Unidad 1
Lección 5: Ordenamiento por inserciónOrdenamiento por inserción
Google ClassroomExisten muchas maneras distintas de ordenar. Conforme se ejecuta el ordenamiento por selección, el subarreglo al inicio del arreglo queda ordenado mientras que el subarreglo al final aún no lo está. El ordenamiento por selección busca en el subarreglo no ordenado el siguiente elemento que será incluido en el subarreglo ordenado.
Aquí está otra forma de pensar acerca del ordenamiento. Imagina que estás jugando un juego de cartas. Tienes las cartas en tu mano y las cartas están ordenadas. Tomas exactamente una nueva carta del mazo. La tienes que colocar en el sitio correcto de manera que las cartas en tu mano sigan estando ordenadas. En el ordenamiento por selección, cada elemento que agregas al subarreglo ordenado es mayor o igual que los elementos que ya están en el subarreglo ordenado. Pero en nuestro ejemplo de las cartas, la nueva carta podría ser menor que algunas de las cartas que ya tienes en la mano, así que vas una por una, comparando la nueva carta con cada una de las que ya tienes en la mano, hasta encontrar el lugar donde debe ser colocada. Insertas la nueva carta en el sitio correcto y, una vez más, tienes en la mano cartas completamente ordenadas. Entonces tomas otra carta del mazo y repites el mismo procedimiento. Luego otra carta, y otra, y así sucesivamente, hasta terminar con el mazo.
Esta es la idea detrás del ordenamiento por inserción. Itera sobre las posiciones en el arreglo, comenzando con el índice 1. Cada nueva posición es como la nueva carta que tomas del mazo, y necesitas insertarla en el sitio correcto en el subarreglo ordenado a la izquierda de esa posición. Aquí está una visualización que sigue esos pasos:
En términos de arreglos, imagina que el subarreglo con índices del 0 al
Y aquí está cómo se debe ver el subarreglo cuando hayamos terminado:
Para insertar el elemento que está en la posición 6 en el subarreglo a su izquierda, lo comparamos repetidamente con los elementos a su izquierda, moviéndonos de derecha a izquierda. Llamemos al elemento en la posición 6 la llave. Cada vez que veamos que la llave es menor que un elemento a su izquierda, desplazamos ese elemento una posición a la derecha, ya que sabemos que la llave tendrá que quedar a la izquierda de ese elemento. Vamos a necesitar hacer dos cosas para lograr que esta idea funcione: necesitamos tener una operación llamada desplazar que desplaza un elemento una posición hacia la derecha, y necesitamos almacenar el valor de la llave en un sitio separado (de manera que el elemento que queda inmediatamente a su izquierda no la reemplaze). En nuestro ejemplo, vamos a jalar el elemento en el índice 6 a una variable llamada
key (llave):Ahora comparamos
key con el elemento en la posición 5. Encontramos que key (5) es menor que el elemento en la posición 5 (13), así que desplazamos este elemento a la posición 6:Observa que la operación de desplazar simplemente copia el elemento una posición a la derecha. A continuación, comparamos
key con el elemento en la posición 4. Encontramos que key (5) es menor que el elemento en la posición 4 (10), y desplazamos este elemento a la derecha:A continuación, comparamos
key con el elemento en la posición 3 y desplazamos ese elemento a la derecha:Sucede lo mismo con el elemento en la posición 2:
Ahora llegamos al elemento en la posición 1, que tiene el valor 3. Este elemento es menor que
key, así que no lo desplazamos hacia la derecha. En lugar de eso, ponemos key en la posición inmediata a la derecha de este elemento (es decir, en la posición 2), cuyo elemento fue el último en desplazarse a la derecha. El resultado es que el subarreglo con índices del 0 al 6 ha quedado ordenado:El ordenamiento por inserción inserta repetidamente un elemento en el subarreglo ordenado que está a su izquierda. Al inicio, podemos decir que el subarreglo que solo contiene al índice 0 está ordenado, ya que contiene un solo elemento, y ¿cómo un solo elemento podría no estar ordenado con respecto a sí msimo? Debe estar ordenado. Trabajemos un ejemplo. Aquí está nuestro arreglo inicial:
Dado que el subarreglo que solo contiene el índice 0 es nuestro subarreglo ordenado inicial, la primera llave está en el índice 1. (Vamos a mostrar el subarreglo ordenado en rojo, la llave en amarillo y la porción del arreglo con la que aún tenemos que trabajar en azul). Insertamos la llave en el subarreglo ordenado que está a su izquierda:
Ahora el subarreglo ordenado va del índice 0 al 1, y la nueva llave está en el índice 2. La insertamos en el subarreglo ordenado a su izquierda:
Seguimos adelante, considerando a cada elemento del arreglo en turno como la llave, e insertándolo en el subarreglo ordenado a su izquierda:
Una vez que hayamos insertado el elemento hasta la derecha en el arreglo, habremos ordenado todo el arreglo:
Un par de situaciones que se presentaron en nuestro ejemplo merecen más atención: cuando la llave que vamos a insertar es menor que todos los elementos a su izquierda (como cuando insertamos las llaves 2 y 3), y cuando es mayor o igual a todos los elementos a su izquierda (como cuando insertamos la llave 13). En el primer caso, cada elemento en el subarreglo a la izquierda de la llave se desplaza una posición a la derecha, y debemos detenernos una vez que hayamos alcanzado el extremo izquierdo del subarreglo. En el segundo caso, la primera vez que comparamos la llave con un elemento a su izquierda, encontramos que la llave ya está en su posición correcta relativa a todos los elementos a su izquierda; ningún elemento se desplaza y la llave se coloca de regreso en la posición en la que inició.
Insertar un valor en un subarreglo ordenado
El paso principal en el ordenamiento por inserción es hacer espacio en un arreglo para colocar el valor actual, que está almacenado en la variable
key. Como vimos anteriormente, recorremos el subarreglo a la izquierda de la posición inicial de key, de derecha a izquierda, desplazando cada elemento que es mayor que key una posición hacia la derecha. Una vez que encontramos un elemento que es menor que key, o igual a key, dejamos de desplazar y copiamos key en la posición vacante justo a la derecha de este elemento. (Por supuesto, la posición no está realmente vacante, pero su elemento fue desplazado a la derecha). Este diagrama muestra la idea:Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.
¿Quieres unirte a la conversación?
respuesta del siguiente desafío:
var insert = function(array, rightIndex, value) {
for(var j = rightIndex;
j >= 0 && array[j] > value;
j--) {
array[j + 1] = array[j];
}
array[j + 1] = value;
};
var insertionSort = function(array) {
for (var i = 1;i < array.length; i++) {
insert(array, i - 1, array[i]);
}
};
var array = [22, 11, 99, 88, 9, 7, 42];
insertionSort(array);
println("Array after sorting: " + array);
Program.assertEqual(array, [7, 9, 11, 22, 42, 88, 99]);
var array = [15, 40, 1, 52, 8, 7, -42, 99];
insertionSort(array);
println("Array after sorting: " + array);
Program.assertEqual(array, [-42, 1, 7, 8, 15, 40, 52, 99]);
si les fue útil dejen un voto a favor :)(31 votos)
como se ordena por insercion?(2 votos)
es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n²) operaciones para ordenar una lista de n elementos.(4 votos)
para que necesitamos el valor actual de un subarreglo?(1 voto)
como se ordena por la interseccion?(1 voto)
si realizo el programa anterior con menos números ¿ se realizara en menor tiempo?(1 voto)- si realizo el programa anterior con menos números ¿ se realizara en menor tiempo?(1 voto)
- ¿que es ordenamiento por inserción ?(1 voto)
- es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n²) operaciones para ordenar una lista de n elementos(1 voto)
