Esta ordenación es, junto con la de burbuja, una de las más conocidas, pero a diferencia de la primera, es de las más eficientes en O(n2). Su funcionamiento es el siguiente: Si sólo tenemos un dato, entonces el arreglo ya está ordenado. Agregando un segundo dato, podemos ordenar el arreglo acomodando este dato antes o después del primero, según corresponda. Para el tercero, vemos si queda antes del primero, del segundo o en su posición actual. En general, si ya tenemos un arreglo ordenado y queremos agregar un nuevo dato, basta con acomodarlo antes de los datos que son mayores a él.
Problema ejemplo
Ordenamiento por Transposición
Un tema importante en las Ciencias de la Computación es el ordenamiento. Casi cualquier problema puede ser resuelto de forma más eficiente si sus datos se encuentran ordenados previamente. Existen varios excelentes métodos de ordenación que han llegado a la cota mínima nlgn. En este problema discutiremos una nueva forma de ordenar. En este nuevo enfoque, sólo contamos con una operación (transponer) que consiste en intercambiar dos términos adyacentes. Si lo piensas un poco, te darás cuenta que es posible ordenar cualquier conjunto de números de esta forma.
Problema
Se da un conjunto de enteros. Utilizando el método previo, queremos ordenar los números en orden ascendente. Debes encontrar el número mínimo de vueltas requeridas para lograrlo. Por ejemplo, para ordenar “1 2 3” no necesitamos operación alguna, mientras que para “2 3 1” se necesitan 2 operaciones por lo menos.Entrada
La entrada comenzará con un entero positivo n (n ≤ 1000). En la siguiente línea habrá n enteros. Esto se repetirá hasta encontrar el fin de archivo (EOF).Salida
Para cada conjunto de datos encontrados en la entrada, debes imprimir “Minimum exchange operations : m” donde m es la cantidad mínima de transposiciones requeridas para el ordenamiento. Utiliza una línea para cada caso.
Solución: Nos están indicando que la ordenación se va a realizar por medio de transposiciones. Sabemos que la ordenación que se basa en cambios de datos adyacentes es la de por burbuja (como se explico en el ejemplo del capítulo 2), por lo que sería la primera opción que tomaríamos.
Sin embargo, también podemos utilizar inserción. Cuando vayamos a ingresar un nuevo dato al arreglo ya ordenado, sólo necesitamos contar cuantos valores son mayores a él y esta será la cantidad de cambios que son requeridos.
Nota: Existe una manera de contar los cambios sin necesidad de ordenar los datos. Para hacerlo, sólo necesitamos recorrer el arreglo y contar cuantos elementos que ya recorrimos son menores al actual. No lo haremos así para aplicar este método de ordenación. También existen otros algoritmos de ordenación que pueden resolver el problema más rápido, como se ve en la sección 11.7.
Código
En las primeras 3 líneas tenemos la declaración de variables: i una variable para ciclos, n es la cantidad de datos, m es la cantidad mínima de intercambios, y a es el arreglo donde se van a guardar los datos.
De la línea 5 a la 7 es donde se ejecuta el ordenamiento por inserción. Primero definimos las funciones i y j que usaremos en ciclos, y temp que es una variables temporal para el intercambio de datos. El ciclo en la línea 8 lo utilizamos para insertar el i-ésimo dato a la parte del arreglo que ya se encuentra ordenada. Con el siguiente ciclo (línea 9) recorremos la parte que ya está ordenada y movemos el nuevo dato hasta la posición que le corresponde. En la línea 14 contamos cuantos cambios hicimos. Esta línea no es parte del algoritmo y la podemos quitar al utilizarlo en otros programas.
Posibles Cambios
La implementación anterior utiliza cambios para llevar el nuevo dato hasta su posición. Tiene la ventaja de que el código queda corto, y va de acuerdo con lo que pide el problema. Aún así, se están realizando operaciones innecesarias. Podemos cambiar código para que se ejecute más rápido.
Esta es la implementación más común de la ordenación por inserción. Las variables son las mismas y tienen el mismo uso que en la implementación anterior. En la línea 4 buscamos insertar el i-ésimo dato en el arreglo ordenado. Ahora lo que hacemos es copiar el dato a insertar en la variable temporal (línea 7) y recorrer todos los valores que sean de menor tamaño un lugar hacia arriba (ciclo entre las líneas 8 y 13). Al final, acomodamos el valor en su nueva casilla (línea 14). Al igual que con la implementación anterior, el incremento de m (línea 12) no es parte del algoritmo y lo podemos quitar al reutilizar el código.
Caso ejemplo
| Entrada: | 6 1 3 6 2 5 4 |
| Desarrollo: | 1 3 6 2 5 4 1 3 6 2 5 4 1 3 6 2 5 4 1 3 6 2 5 4 ← m = 1 1 3 2 6 5 4 ← m = 2 1 2 3 6 5 4 1 2 3 6 5 4 ← m = 3 1 2 3 5 6 4 1 2 3 5 6 4 ← m = 4 1 2 3 5 4 6 ← m = 5 1 2 3 4 5 6 |
| Salida: | Minimum exchange operations : 5 |
Códigos en C
Tiempo de ejecución
| Lenguaje | Fecha | Tiempos [s] | Memoria [Kb] | |||
|---|---|---|---|---|---|---|
| Ejecución | Mejor | Mediana | Peor | |||
| Pascal | 19-Feb-2006 | 0.238 | 0.021 | 0.537 | 6.314 | 320 |
| C | 19-Feb-2006 | 0.330 | 396 | |||
| Pascal | 19-Feb-2006 | 0.166 | 324 | |||
| C | 19-Feb-2006 | 0.205 | 396 | |||
Introducción
