162 Ordenamiento, Búsqueda e Intercalación
luego insertamos 2 delante de 6 y desplazamos 6 y 8.
obteniendo:
-1 2 6 8 | 0 3 -4 3
Como observación: si la componente considerada es ya mayor que la anterior (p.ej: si en
el paso anterior fuera 12 en vez de 2) simplemente se la deja como está, y se pasa a considerar la
componente que sigue (el 0 en este caso).
-1 6 8 12 0 3 -4 3
Volviendo al arreglo original, ya nos damos cuenta, entonces, cómo serán los pasos poste-
riores, insertando las componentes restantes hasta la n
-1 0 2 6 8 | 3 -4 3
-1 0 2 3 6 8 | -4 3
-4 -1 0 2 3 6 8 | 3
-4 -1 0 2 3 3 6 8
Veamos la implementación de un algoritmo para realizar este proceso.
AlgoritmoInserción
entero n, i, j
real V[10000], aux
logico cond
inicio
Leer (n) !suponemos 0<n<=10000
Repetir Para i ← 1, n
leer(V[i])
finpara
! Comienza el ordenamiento
Repetir Para i ← 2, n ! V[i] componente a insertar
x ← V[i] ! almacenarla para no perderla
j ← i – 1 ! posición componente anterior
cond ← verdadero
! se puede comparar para insertar
Repetir Mientras (cond y j>0)
si x<V[j] entonces
V[j+1] ← V[j] ! desplazar un lugar
j ← j–1
sino
cond ← falso
7.1 Ordenamiento 163
finsi
fin mientras
V[j+1] ← x ! almacenar x en el lugar libre
finpara
Repetir Para i ← 1, n
Escribir (V[i])
finpara
fin
7.1.4 Cantidad de comparaciones efectuadas
Hasta aquí hemos propuesto algoritmos que efectivamente resuelven el problema de or-
denamiento, es decir parten de un arreglo desordenado, y tomando cada uno por su camino,
finalizan con el arreglo ordenado. Sin embargo, si la cantidad de datos a ordenar es grande, no
todos los algoritmos trabajan con igual eficiencia. Un análisis de las comparaciones y operaciones
efectuadas, nos detallará estas características.En los tres algoritmos que vimos, hay dos estruc-
turas “repetir para” o “repetir mientras” anidadas, cada una de las cuales recorre una cantidad de
elementos relacionada con n. Esto nos lleva a pensar, en un primer examen, que la cantidad de
operaciones que realiza el algoritmo tiene que estar relacionada con n*n.Analicémoslo con más
precisión en el método de la burbuja (en los otros el razonamiento es similar).
Hay n-1 componentes a ordenar. Para cada una de ellas se deben realizar entre 1 y n-1 compara-
ciones y eventuales intercambios. Tomando el promedio ((n-1)+1)/2 = n/2, la cantidad total de
operaciones se puede estimar como:
(n-1) * n/2 =1/2*n*n - 1/2 * n= 1/2*(n*n – n)
Para n grande (n → ∞), n es despreciable frente a n*n, y basta considerar sólo 1/2*n*n. Es decir,
la cantidad de operaciones que hay que hacer para ordenar un arreglo de n componentes es
proporcional a n*n. En otras palabras, la cantidad de comparaciones crece con el cuadrado de
la cantidad de componentes del arreglo. Entonces, se dice, que el método de la burbuja es un
algoritmo de orden n*n o cuadrático.Pensando que el tiempo de ejecución de un algoritmo es
aproximadamente proporcional a la cantidad de operaciones o comparaciones que efectúa, si p.
ej. para ordenar un arreglo de 10.000 componentes la máquina tarda 1 segundo, para ordenar
uno de 100.000, cuya cantidad de componentes es 10 veces mayor, hay que esperar que demore
un tiempo 10*10=100 veces mayor, o sea 100 segundos, que es 1 minuto con 40 segundos.Esta
observación nos hace entrar en el terreno de la complejidad computacional. Hay algoritmos
cuyo tiempo de ejecución crece mucho más que proporcionalmente a la cantidad de elementos a
procesar. Por ejemplo, una tarea muy frecuente en problemas de cálculo técnico, es la resolución
de sistemas lineales de orden n (sistemas de n ecuaciones con n incógnitas). Los algoritmos
que resuelven estos sistemas por los métodos corrientes de eliminación, son del orden de n3.
Pensemos que puede haber problemas que requieran algoritmos con un orden de exponente
aún mayor, y nos daremos cuenta que tan importante como lograr mejoras en el hardware,
p. ej. mediante computadoras más veloces, es obtener mejoras en el software, empleando o
desarrollando algoritmos que reduzcan la complejidad de las tareas, o que puedan procesarlas en
paralelo, etc.Concretamente, en el caso del ordenamiento de arreglos, no se ha inventado ningún
algoritmo de orden n, pero sí del orden de n log2 n , el Quick sort u Ordenamiento rápido. Para
ordenar un arreglo de 2 elevado a 7 = 128 componentes, el quick sort haría aproximadamente
una cantidad de operaciones proporcional a 128 log2 128 = 128 x 7 = 896. Para ordenar uno de 2