Cargando...
 
Imprimir

Ordenación por inserción directa (InsertionSort)

Image
El algoritmo de ordenación por el método de inserción directa es un algoritmo relativamente sencillo y se comporta razonablemente bien en gran cantidad de situaciones.

Completa la tripleta de los algoritmos de ordenación más básicos y de orden de complejidad cuadrático, junto con SelectionSort y BubbleSort.

Se basa en intentar construir una lista ordenada en el interior del array a ordenar.

De estos tres algoritmos es el que mejor resultado da a efectos prácticos. Realiza una cantidad de comparaciones bastante equilibrada con respecto a los intercambios, y tiene un par de características que lo hacen aventajar a los otros dos en la mayor parte de las situaciones.

Este algoritmo se basa en hacer comparaciones, así que para que realice su trabajo de ordenación son imprescindibles dos cosas: un array o estructura similar de elementos comparables y un criterio claro de comparación, tal que dados dos elementos nos diga si están en orden o no. (ver Algoritmos de ordenación).

Es un algoritmo estable de ordenación interna y su complejidad temporal en el peor caso es de O(n2) y en el mejor caso -que el array ya esté totalmente ordenado- puede llegar a Ω(n) siendo n el tamaño del array a ordenar.

El algoritmo consiste en realizar varias pasadas sobre el array. En cada pasada se analiza un elemento, y se intenta encontrar su orden relativo entre los analizados en pasadas anteriores. Con esto se logra ir manteniendo una lista ordenada constantemente. Cada elemento a analizar se desplaza por esa lista hasta encontrar su lugar. Cuando todos los elementos del array han sido analizados, la lista está completamente ordenada. Esa es una diferencia importante con BubbleSort y SelectionSort. En ellos, en cada pasada se colocaba una carta en su sitio definitivo. En InsertionSort, el array no está totalmente ordenado hasta que el algoritmo termina.

Por otro lado, en cada pasada no se recorre todo el array, sino solo los elementos analizados y ordenados en pasadas anteriores. Eso convierte a InsertionSort en un Algoritmo en línea (online), es decir, un algoritmo que no necesita disponer de todos los elementos a ordenar desde el principio, sino que puede aceptarlos de uno en uno y procesarlos a medida que los recibe.

Vamos a intentar ver informalmente el funcionamiento del algoritmo. Supondremos que el array tiene n elementos.

  • Realizaremos n-1 pasadas. En cada una de ellas analizaremos un elemento, colocándolo en orden relativo con respecto a los analizados en pasadas anteriors. El motivo de realizar n-1 pasadas y no n es que empezamos por el segundo elemento. Si analizásemos el primer elemento deberíamos colocarlo en orden con respecto a los anteriores, pero al no haber realizado pasadas anteriores, el primer elemento forma él solito una lista ordenada. Así pues, empezamos con el segundo directamente.
  • En cada pasada escogemos un elemento sucesivamente (en la primera pasada el segundo elemento, en la segunda el tercero.... en la n-1 el n) y recorreremos el array hacia atrás (hacia la izquieda, si quieres) buscando el orden relativo del elemento en cuestión entre los anteriores (los de su izquierda). Cada vez que encontremos un elemento que sea mayor que él realizaremos un intercambio.

Un ejemplo

Vemos un ejemplo sencillo. Supongamos que queremos ordenar estos valores con el algoritmo de selección directa: 45, 52, 21, 37, 49, 72, 14. Así pues, n=7

Empezamos a analizar el segundo elemento. El primero está en orden con respecto a sí mismo. Forma él solo una lista ordenada. Intentaremos mantener una lista ordenada al principio del array. Vamos a marcar el elemento a analizar en rojo y la lista ordenada en azul.

1ª pasada: El primer elemento forma la lista ordenada, y vamos a ver qué hacemos con el segundo.

45, 52, 21, 37, 49, 72, 14 → Comparamos 52 con el anterior. Como está en orden, paramos.
45, 52, 21, 37, 49, 72, 14 → 45 y 52 forman la lista ordenada ahora. (Sí, sí... están en orden entre ellos 45<52)

2ª pasada: Hay dos elementos en orden relativo entre ellos y vamos a ver qué hacemos con el tercero.

45, 52, 21, 37, 49, 72, 14 → Comparamos el 21 con el anterior (52). No están en orden, así que los intercambiamos.
45, 21, 52, 37, 49, 72, 14 → Comparamos el 21 con el anterior (45). No están en orden, así que los intercambiamos.
21, 45, 52, 37, 49, 72, 14 → Ya no hay más para comparar. El 21 está en su sitio con respecto a los otros de la lista.
21, 45, 52, 37, 49, 72, 14 → Ahora 21, 45 y 52 forman la lista ordenada.

3ª pasada: Hay tres elementos en orden relativo entre ellos y vamos a ver qué hacemos con el cuarto.

21, 45, 52, 37, 49, 72, 14 → Comparamos el 37 con el anterior (52). No están en orden, así que los intercambiamos.
21, 45, 37, 52, 49, 72, 14 → Comparamos el 37 con el anterior (45). No están en orden, así que los intercambiamos.
21, 37, 45, 52, 49, 72, 14 → Comparamos el 37 con el anterior (21). Sí están en orden, así que paramos.
21, 37, 45, 52, 49, 72, 14 → Ahora 21, 37, 45 y 52 forman la lista ordenada.

4ª pasada: Hay cuatro elementos en orden relativo entre ellos y vamos a ver qué hacemos con el quinto.

21, 37, 45, 52, 49, 72, 14 → Comparamos el 49 con el anterior (52). No están en orden, así que los intercambiamos.
21, 37, 45, 49, 52, 72, 14 → Comparamos el 49 con el anterior (45). sí están en orden, así que paramos.
21, 37, 45, 49, 52, 72, 14 → Ahora 21, 37, 45, 49 y 52 forman la lista ordenada.

5ª pasada: Hay cinco elementos en orden relativo entre ellos y vamos a ver qué hacemos con el sexto.

21, 37, 45, 49, 52, 72, 14 → Comparamos el 72 con el anterior (52). Sí están en orden, así que paramos.
21, 37, 45, 49, 52, 72, 14 → Ahora 21, 37, 45, 49, 52 y 72 forman la lista ordenada.

6ª y última pasada: Hay seis elementos en orden relativo entre ellos y vamos a ver qué hacemos con el séptimo.

21, 37, 45, 49, 52, 72, 14 → Comparamos el 14 con el anterior (72). No están en orden, así que los intercambiamos.
21, 37, 45, 49, 52, 14, 72 → Comparamos el 14 con el anterior (52). No están en orden, así que los intercambiamos.
21, 37, 45, 49, 14, 52, 72 → Comparamos el 14 con el anterior (49). No están en orden, así que los intercambiamos.
21, 37, 45, 14, 49, 52, 72 → Comparamos el 14 con el anterior (45). No están en orden, así que los intercambiamos.
21, 37, 14, 45, 49, 52, 72 → Comparamos el 14 con el anterior (37). No están en orden, así que los intercambiamos.
21, 14, 37, 45, 49, 52, 72 → Comparamos el 14 con el anterior (21). No están en orden, así que los intercambiamos.
14, 21, 37, 45, 49, 52, 72 → Comparamos el 14 con el anterior (21). No están en orden, así que los intercambiamos.
14, 21, 37, 45, 49, 52, 72 → Ya no hay más para comparar, así que el 14 está en su sitio.

Ya no quedan elementos a anailizar al final del array, así que hemos terminado y el array está ordenado.



El algoritmo

Expresado en pseudocódigo, podría ser algo como esto (ojo: este algoritmo aún no es el bueno de inserción directa):

pseudocódigo
algoritmo insercion( A : array de n elementos indizados de 1 a n)
  variables: enteros i,j, temporal
  //estas son las pasadas, desde 2 hasta n
  //en cada una intentaremos encontrar la posición
  //relativa del elemento i entre los anteriores
  para i desde 2 hasta n
      j=i-1
      //vamos "descendiendo" el elemento
      //haciendo intercambios
      mientras (j>=1) Y (A[j]>A[j+1]) hacer
         //intercambio de la posicion j y la siguiente
         temporal=A[j+1]
         A[j+1]=A[j]
         A[j]=temporal
         j=j-1
      fin mientras
  fin para
fin algoritmo


La idea es sencilla. El índice i nos va llevando desde el elemento 2 hasta el último. En cada vuelta del bucle "para" cogemos el elemento que está inicialmente en la posición "i" y lo vamos intercambiando en el bucle "mientras" con los anteriores (que están en orden relativo entre ellos) hasta que ocupe su lugar.

No obstante, hay una optimización muy importante que podemos hacer. Vamos a fijarnos en la última vuelta del ejemplo de antes... en la que movemos el 14 a través del array hasta ocupar su sitio. (si no te acuerdas, echa un vistazo y vuelve). En esa 6ª iteración hemos ido "arrastrando" el 14 por distintos lugares pero ninguno de ellos ha sido definitivo excepto el último. Esto es innecesario: podríamos haber tomado el 14 en una variable temporal, haber hecho comparaciones hasta saber cual es su sitio y luego desplazar de golpe varios valores para hacerle hueco al 14. Finalmente, recuperar el 14 de la variable temporal y colocarlo en su sitio. Mira:

Reproductor Flash no disponible.


Así pues, esto nos lleva a una versión mucho mejor del algoritmo (éste es el bueno):

algoritmo insercion( A : array de n elementos indizados de 1 a n)
  variables: enteros i, j, v
  //estas son las pasadas, desde 2 hasta n
  //en cada una intentaremos encontrar la posición
  //relativa del elemento i entre los anteriores
  para i desde 2 hasta n
      //tomamos el elemento a examinar en una variable
      //temporal v
      v=A[i]
      //empezamos a comparar con los anteriores.
      j=i-1
      //en este bucle intentamos saber cual es su
      //lugar y le vamos haciendo hueco
      mientras (j>=1) Y (A[j]>v) hacer
         //desplazamos el elemento A[j]
         A[j+1]=A[j]
         j=j-1
      fin mientras
      A[j+1]=v
  fin para
fin algoritmo


Por qué comentamos esto?... pues porque cuando introdujimos los algoritmos de ordenacion en el artículo titulado "Algoritmos de ordenación" dijimos que la mayor parte de los algoritmos de ordenación se basaban en dos operaciones: comparación e intercambio. Ésta segunda versión del algoritmo de inserción directa es la que normalmente se utiliza, y los intercambios no se ven. Realmente están ahí, como en la primera versión, pero han sido simplificados.

Ahora que ya sabemos de qué va el algoritmo, podemos hacernos una idea algo más gráfica con ésta animación de baja tecnología:
Reproductor Flash no disponible.


(La música es Bohemia Rag de Joseph Lamb, obtenida de la página de Warren Trachtman(external link). Gracias, Warren)

También hay que tener en cuenta que por supuesto, es necesario adaptarlo a las necesidades concretas. Por ejemplo, en C/C++/C#/Java, etc... los índices de los arrays empiezan en 0 y terminan en n-1. El array a ordenar no tiene por qué ser de enteros, puede ser de cualquier cosa ordenable, pero entonces, análogamente, la operación de comparación (">") debe ser sustituida por la operación que nos compare nuestros elementos por el criterio que nosotros queramos.

Pasándolo a un lenguaje de programación

Como de costumbre, vamos a poner un ejemplo en C# (Ojo con los índices de los arrays: en C# comienzan en 0, y en el pseudocódigo de arriba en 1):
C#
static void InsercionDirecta(int[] A)
{
   //n=la cantidad de elementos en A
   int n = A.Length;
   //empezamos por el segundo (1) y terminamos
   //en el último (n-1)
   for (int i = 1; i < n; i++)
   {
       //guardamos el valor del elemento i
       int v = A[i];
       //empezamos a compararlo con el anterior
       int j = i - 1;
       //y seguimos mientras no hayamos llegado
       //al principio del array y los elementos
       //que encontremos sean mayores que el que
       //analizamos
       while (j >= 0 && A[j] > v)
          {
              //desplazamos el elemento un
              //lugar a la derecha
              A[j + 1] = A[j];
              //y pasamos al anterior
              j--;
          }
       //Al terminar el bucle, j indica el
       //lugar inmediatamente anterior a donde
       //debemos encajar v
       A[j + 1] = v;
   }
}


¿Y con objetos u otro tipo de dato?

Pues ningún problema. Primero, necesitamos tener un criterio claro de ordenación, y que algún método nos permita saber dados dos objetos si están en orden o no. Mira cómo lo hicimos con el algoritmo de la burbuja. Lo mismo se puede aplicar con la inserción directa.

¿Por qué InsertionSort se comporta, en general mejor que (BubbleSort) o (SelectionSort)?

l hecho de que se comporte mejor viene de dos sitios distintos:

  • Por un lado, la simplificación de los intercambios que hemos hecho descarga bastante el trasiego de memoria que hace el algoritmo, aunque no reduzca su complejidad en el peor caso (el número de operaciones sigue creciendo de manera acotada por arriba por una función cuadrática que depende del número de elementos a ordenar).
  • Por otro lado, el algoritmo se aprovecha del posible orden parcial que pueda existir entre los elementos. Es decir, si un elemento está "cerca" de su posición definitiva, el algoritmo hace menos intercambios. El caso extremo es que el array esté totalmente ordenado... en cuyo caso, el algoritmo nunca entra en el bucle interior y por eso su complejidad en este caso -el mejor- es Ω(n). En esta caso, la cota inferior de la complejidad temporal baja hasta una función lineal.

¿Optimizaciones?

Pues si... todavía se puede mejorar aun más este algoritmo, y sin que deje de ser un algoritmo in-situ. Hay muchas variantes de éste algoritmo, pero vamos a comentar sólo dos.

La primera de ellas es más o menos evidente. Si nos paramos a pensar, el algoritmo realiza con el bucle mientras una búsqueda lineal en una lista enlazada. Lo que está buscando es el lugar exacto en el que debe ir el elemento colocado justo detras de la lista (el que indica el índice i). Cierto es que a medida que va realizando la búsqueda va abriendo hueco desplazando los elementos que encuentra hacia la derecha en el array, porque sabemos que el objeto de la búsqueda es encajar ese elemento. No obstante, hay una forma más eficiente de realizar una búsqueda en un array ordenado: una búsqueda dicotómica. Éste tipo de búsqueda puede encontrar el lugar preciso donde se debe insertar el elemento indizado por i con menos comparaciones -en promedio- que la búsqueda lineal que se utiliza arriba. Sin embargo, cuando se encuentra ese lugar sigue siendo necesario desplazar los elementos hacia la derecha para dejar hueco al elemento. En definitiva... nos ahorramos unas pocas comparaciones y poco más. El efecto se nota un poco si el array a ordenar es muy grande... pero entonces, quizá no merezca la pena utilizar un algoritmo de éste tipo (In-situ y de complejidad cuadrática, como Bubblesort, Selectionsort, InsertionSort y sus variantes), si no pasar a alguno más rápido, aunque consuma una cantidad no constante de memoria (como QuickSort, con una complejidad temporal menor, aunque aumenta la espacial). En fin... una optimización que me convence poco.

La otra sí que me gusta mucho más. En 1959, un ingeniero llamado Donald Shell publicó una variante realmente ingeniosa -casi "mágica"- del algoritmo de inserción directa que hoy conocemos por su nombre: el algoritmo de ordenación de Shell, o ShellSort. La idea básica es aplicar el algoritmo de inserción directa repetidas veces, pero entre elementos separados una determinada distancia k, que al principio es bastante grande. Eso hace que cada elemento se aproxime a su posición definitiva dando saltos muy grandes. Luego se va reduciendo progresivamente esa distancia k hasta hacerla 1. Así pues, al principio del algoritmo cada elemento da grandes saltos hacia su ubicación definitiva, y a medida que va avanzando el algoritmo, cada vez son más pequeños hasta que cada elemento está en su sitio definitivo. Con esta optimización se pierde la característica de ser un algoritmo on line, y tampoco es un algoritmo de ordenación estable, pero en contrapartida, sigue requiriendo un gasto constante de memoria (in-situ) y es en general, mucho más rápido... De hecho, es el más rápido en promedio de los algoritmos de ordenación in-situ. Desde que Shell lo publicó ha sido revisado y perfeccionado por otros. El algoritmo de Shell es lo suficientemente importante como para dedicarle un artículo en otra ocasión.

Ultima edición por vic .
Página última modificacion en Viernes 17 de Agosto, 2012 16:39:50 CEST.


¿Dónde estoy?

Estás en La tecla de ESCAPE, un sitio web personal en el que nos gusta hablar de algoritmos, metodología de la programación, personajes de informática, tecnología, ingeniería del software, internet, y cualquier otra tontería que se nos ocurra.
Leer más / Términos de uso (ToS)