Nombre:Alexandra Maguana
Métodos de Ordenamiento
En este artículo vamos a mostrar los
algoritmos, ventajas y desventajas de los 3 métodos de ordenamiento más comunes
y básicos. Estos son: burbuja, selección, inserción.
Los métodos de ordenamiento son necesarios para que luego de ordenar, se puedan
buscar datos de una manera mucho mas rápida y eficiente aplicando distintas
técnicas.
Ordenamientos Internos y Externos
Internos: los valores a
ordenar están en memoria principal, por lo que se asume que el tiempo que se
requiere para acceder cualquier elemento sea el mismo (a[1], a[500], etc).
Externos: Los valores a
ordenar están en memoria secundaria (disco, cinta, cilindro magnético, etc),
por lo que se asume que el tiempo que se requiere para acceder a cualquier
elemento depende de la última posición accesada (posición 1, posición 500…)
Existen tres casos al ordenar
información
1) El peor caso
para el algoritmo es cuando la información que se tiene está ordenada al revés.
2) El Mejor es
cuando la información está ordenada.
3) El caso Promedio es
cuando la información está ordenada al azar.
Algoritmos de Ordenamiento Lineal
Por ordenar se entiende el proceso de reorganizar
un conjunto de objetos en una cierta secuencia de acuerdo a un criterio
especificado. En general, el objetivo de este proceso es facilitar la posterior
búsqueda de elementos en el conjunto ordenado.
Existen múltiples ejemplos reales de conjuntos que
requieren ser ordenados: la guía telefónica, índices de libros, ficheros de
bibliotecas, diccionarios, ficheros de diverso tipo en oficinas, actas de
exámenes, etc.
A continuación se describen algunos de los
algoritmos de ordenación lineal más conocidos.
BubleSort
La idea de este método es ir tomando los elementos
de a dos e ir comparándolos e intercambiándolos de ser necesario, hasta que
todos los elementos sean comparados.
El bucle externo establece un desplazamiento
secuencial dentrodel vector desde el primer elemento hasta el penúltimo , el
bucle interno realiza un recorrido del vector desde el elemento i+1 hasta el
último elemento del vector y va reduciendo en cada iteración del bucle externo
el número de elementos a comparar, ya que los elementos anteriores ya debieron
ordenarse en las iteraciones anteriores. Ahora bien, lo que se quiere es
ordenar todos los valores, para lo cual se compara el elemento i con los subsiguientes
elementos del vector e intercambiándolo cuando sea mayor que alguno de los
elementos ubicado en alguna posición inferior del vector, en este intrecambio
es que se genera la burbuja, donde los elementos más pequeños van subiendo y
los más grandes se van ubicando en las posiciones inferiores del vector.
Ejemplo 3.1. Supongamos que un vector de 10
elementos tiene estos valores:
9 7 6 5 4 3 11 8 10 2
A continuación se describe paso por paso la evolución del método. Representando
cada estado del vector de la siguiente manera:
i,j->V[0]V[1]V[2]V[3]V[4]V[5]V[6]V[7]V[8]V[9]
0,1->7 9 6 5 4 3 11 8 10 2
0,2->6 9 7 5 4 3 11 8 10 2
0,3->5 9 7 6 4 3 11 8 10 2
0,4->4 9 7 6 5 3 11 8 10 2
0,5->3 9 7 6 5 4 11 8 10 2
0,6->3 9 7 6 5 4 11 8 10 2
0,7->3 9 7 6 5 4 11 8 10 2
0,8->3 9 7 6 5 4 11 8 10 2
0,9->2 9 7 6 5 4 11 8 10 3
1,2->2 7 9 6 5 4 11 8 10 3
1,3->2 6 9 7 5 4 11 8 10 3
1,4->2 5 9 7 6 4 11 8 10 3
1,5->2 4 9 7 6 5 11 8 10 3
1,6->2 4 9 7 6 5 11 8 10 3
1,7->2 4 9 7 6 5 11 8 10 3
1,8->2 4 9 7 6 5 11 8 10 3
1,9->2 3 9 7 6 5 11 8 10 4
2,3->2 3 7 9 6 5 11 8 10 4
2,4->2 3 6 9 7 5 11 8 10 4
2,5->2 3 5 9 7 6 11 8 10 4
2,6->2 3 5 9 7 6 11 8 10 4
2,7->2 3 5 9 7 6 11 8 10 4
2,8->2 3 5 9 7 6 11 8 10 4
2,9->2 3 4 9 7 6 11 8 10 5
3,4->2 3 4 7 9 6 11 8 10 5
3,5->2 3 4 6 9 7 11 8 10 5
3,6->2 3 4 6 9 7 11 8 10 5
3,7->2 3 4 6 9 7 11 8 10 5
3,8->2 3 4 6 9 7 11 8 10 5
3,9->2 3 4 5 9 7 11 8 10 6
4,5->2 3 4 5 7 9 11 8 10 6
4,6->2 3 4 5 7 9 11 8 10 6
4,7->2 3 4 5 7 9 11 8 10 6
4,8->2 3 4 5 7 9 11 8 10 6
4,9->2 3 4 5 6 9 11 8 10 7
5,6->2 3 4 5 6 9 11 8 10 7
5,7->2 3 4 5 6 8 11 9 10 7
5,8->2 3 4 5 6 8 11 9 10 7
5,9->2 3 4 5 6 7 11 9 10 8
6,7->2 3 4 5 6 7 9 11 10 8
6,8->2 3 4 5 6 7 9 11 10 8
6,9->2 3 4 5 6 7 8 11 10 9
7,8->2 3 4 5 6 7 8 10 11 9
7,9->2 3 4 5 6 7 8 9 11 10
8,9->2 3 4 5 6 7 8 9 10 11
La evolución del método muestra que cada elemento
del vector desde el primer elemento hasta el penúltimo se van comparando con
los subsiguientes (no con los anteriores), ya que los elementos se han comparado
en las iteraciones anteriores
La falencia de este método es que como sí o sí va a
hacer n - 1 pasadas, muchas veces puede hacer pasadas inclusive con el vector
ya ordenado. Por lo tanto, una mejora para este método consiste en establecer
un mecanismo para que verifique cuando el vector este ya ordenado.
Si queremos ordenar el vector descendente cambiamos
el signo en la condición del SI por V[i]< V[j].
Análisis del algoritmo.
Estabilidad: Este algoritmo nunca intercambia registros con claves iguales.
Por lo tanto es estable.
Requerimientos de Memoria: Este algoritmo sólo requiere de una variable
adicional para realizar los intercambios sin importar qué tan grande sea
el vector. Requerimiento constante.
Tiempo de Ejecución: El ciclo interno se ejecuta (n-1)*n/2 veces para una
lista de n elementos. El ciclo externo se ejecuta n veces. Es decir, la
complejidad es n * n = O(n2). El comportamiento del caso promedio depende
del orden de entrada de los datos, pero es sólo un poco mejor que el del
peor caso, y sigue siendo O(n2).
Ventajas
|
Desventajas
|
A) Fácil implementación
|
A) Muy lento
|
B) No requiere memoria adicional.
|
B) Realiza numerosas comparaciones
|
C) Realiza numerosos intercambios.
|
|
Este algoritmo es uno de los más pobres en
rendimiento. No es recomendable usarlo. Tan sólo está aquí para que sea
conocido, y porque su sencillez lo hace bueno para empezar.
SelectionSort
Entre los métodos elementales de ordenación de
vectores se encuentra el algoritmo de selección:
Es decir, el método se basa en buscar en cada
iteracción el mínimo elemento del “subvector” situado entre el índice i y el
final del vector e intercambiarlo con el de índice i. Tomando la dimensión del
vector n como tamaño del problema es inmediato que el bucle se repite n veces y
por tanto la función que da el número de repeticiones es de tipo lineal (O(n)).
La operación interior al bucle se puede desarrollar a su vez como:
Se trata de una secuencia de tres operaciones, la
segunda de las cuales es, a su vez, una iteración. La primera (asignación) y la
tercera(intercambio) pueden considerarse de coste constante. La segunda es un
bucle que internamente incluye una operación condicional que en el peor caso
supone una operación de coste constante (O(1)) (en el peor caso y en el mejor, puesto
que la comparación se ha de realizar siempre ) y el número de repeticiones de
esa operación es de tipo lineal, ya que se realiza n-(i+1) veces, y por tanto,
al crecer n, el número de veces crece proporcionalmente a n. Luego será de
costeO(n) O(1) = O(n). Éste será entonces el coste de la secuencia completa
(sucesión de dos operaciones de coste constante y una de coste lineal)
El algoritmo total será entonces de ordenO(n).O(n)
=O(n^2)
Es interesante observar que en este algoritmo el
contenido de los datos de entrada, no influye en el coste del algoritmo. En
efecto se puede comprobar (aplicar el algoritmo sobre varios vectores ejemplo),
que se ejecutan de forma completa ambos bucles tanto para vector desordenado
como para vector ordenado.
Ejemplo Supongamos que un vector de 10 elementos
tiene estos valores:
9 7 6 5 4 3 11 8 10 2
A continuación se describe paso por paso la
evolución del método. Representando cada estado del vector de la siguiente
manera:
V[i]<->V[imin]
=>V[0]V[1]V[2]V[3]V[4]V[5]V[6]V[7]V[8]V[9], igualmente se muestran cada uno
de los cambios de la variable imin.
imin -> 1
imin -> 2
imin -> 3
imin -> 4
imin -> 5
imin -> 9
V[0]<->V[9]=>2 7 6 5 4 3 11 8 10 9
imin -> 2
imin -> 3
imin -> 4
imin -> 5
V[1]<->V[5]=>2 3 6 5 4 7 11 8 10 9
imin -> 3
imin -> 4
V[2]<->V[4]=>2 3 4 5 6 7 11 8 10 9
V[3]<->V[3]=>2 3 4 5 6 7 11 8 10 9
V[4]<->V[4]=>2 3 4 5 6 7 11 8 10 9
V[5]<->V[5]=>2 3 4 5 6 7 11 8 10 9
imin -> 7
V[6]<->V[7]=>2 3 4 5 6 7 8 11 10 9
imin -> 8
imin -> 9
V[7]<->V[9]=>2 3 4 5 6 7 8 9 10 11
V[8]<->V[8]=>2 3 4 5 6 7 8 9 10 11
V[9]<->V[9]=>2 3 4 5 6 7 8 9 10 11
Análisis del algoritmo.
- Estabilidad:
No es estable. Intercambia registros con claves iguales.
- Requerimientos
de Memoria: Este algoritmo sólo requiere de una variable adicional para
realizar los intercambios sin importar qué tan grande sea el vector.
Requerimiento constante.
- Tiempo
de Ejecución: El ciclo externo se ejecuta n veces para una lista de n
elementos. Cada búsqueda requiere comparar todos los elementos no
clasificados. Luego la complejidad es O(n2). Este algoritmo presenta un
comportamiento constante independiente del orden de los datos. Luego la
complejidad promedio es también O(n2).
Ventajas
|
Desventajas
|
A) Fácil implementación
|
A) Lento
|
B) No requiere memoria adicional.
|
B) Realiza numerosas comparaciones.
|
C) Realiza pocos intercambios.
|
C) Este es un algoritmo lento
|
D) Rendimiento constante: poca diferencia entre
el peor y el mejor caso
|
|
No obstante, ya que sólo realiza un intercambio en
cada ejecución del ciclo externo, puede ser una buena opción para listas con
registros grandes y claves pequeñas.
InsertionSort
En este procedimiento se recurre a una búsqueda
binaria en lugar de una búsqueda secuencial para insertar un elemento en la
parte de arriba del arreglo, que ya se encuentra ordenado. El proceso, al igual
que en el método de inserción directa, se repite desde el segundo hasta el n-elemento.
Ejemplo Supongamos que un vector de 10 elementos
tiene estos valores:
9 7 6 5 4 3 11 8 10 2
A continuación se describe paso por paso la
evolución del método. Representando cada estado del vector de la siguiente
manera:
i->V[0]V[1]V[2]V[3]V[4]V[5]V[6]V[7]V[8]V[9]
1->7 9 6 5 4 3 11 8 10 2
2->6 7 9 5 4 3 11 8 10 2
3->5 6 7 9 4 3 11 8 10 2
4->4 5 6 7 9 3 11 8 10 2
5->3 4 5 6 7 9 11 8 10 2
6->3 4 5 6 7 9 11 8 10 2
7->3 4 5 6 7 8 9 11 10 2
8->3 4 5 6 7 8 9 10 11 2
9->2 3 4 5 6 7 8 9 10 11
Análisis del algoritmo.
- Estabilidad:
Este algoritmo nunca intercambia registros con claves iguales. Por lo
tanto es estable.
- Requerimientos
de Memoria: Este algoritmo sólo requiere de una variable adicional para
realizar los intercambios sin importar qué tan grande sea el vector.
Requerimiento constante.
- Tiempo
de Ejecución: Al analizar el método de ordenación por inserción binaria se
advierte la presencia de un caso antinatural. El método efectúa el menor
número de comparaciones cuando el arreglo está totalmente desordenado y el
máximo cuando está ordenado.
Es posible suponer que mientras en una búsqueda
secuencial se necesitan k comparaciones para insertar un elemento, en una
búsqueda binaria se necesitará la mitad de las k comparaciones. Por lo tanto,
el número de comparaciones promedio en el método de ordenación por Inserción
Binaria puede calcularse como :
C= (1/2) + (2/2) + (3/2) + . . . + ((n-1)/2) =
((n(n-1))/4) = ((n2 – n) / 4)
Éste es un algoritmo de comportamiento antinatural
y por lo tanto es necesario ser muy cuidadoso cuando se hace un análisis de él.
Las mejoras producen un efecto negativo cuando el arreglo está ordenado y
produce resultados apenas satisfactorios cuando las claves (temp y V[Medio])
están desordenadas. De todas maneras debe recordarse que no se reduce el número
de movimientos que es una operación más complicada y costosa que la operación
de comparación. Por lo tanto, el tiempo de ejecución del algoritmo sigue siendo
proporcional a n2.
Ventajas
|
Desventajas
|
A) Fácil implementación
|
A) Lento.
|
B) No requiere memoria adicional.
|
B) En promedio hace numerosas comparaciones.
|
ShellSort
Denominado así por su desarrollador Donald Shell
(1959), ordena una estructura de una manera similar a la del Bubble Sort, sin
embargo no ordena elementos adyacentes sino que utiliza una segmentación entre
los datos. Esta segmentación puede ser de cualquier tamaño de acuerdo a una
secuencia de valores que empiezan con un valor grande (pero menor al tamaño
total de la estructura) y van disminuyendo hasta llegar al '1'.
Este método funciona de la siguiente manera:
- Ordena
subgrupos de elementos separados K unidades (respecto de su posición en el
arreglo) del arreglo original. El valor K es llamado incremento.
- Después
de que los primeros K subgrupos han sido ordenados, se escoge un nuevo
valor de K más pequeño, y el arreglo es de nuevo partido entre el nuevo
conjunto de subgrupos. Cada uno de los subgrupos mayores es ordenado y el
proceso se repite de nuevo con un valor más pequeño de K.
- Eventualmente
el valor de K llega a ser 1, de tal manera que el subgrupo consiste de
todo el arreglo ya casi ordenado.
- Al
principio del proceso se escoge la secuencia de decrecimiento de
incrementos; el último valor debe ser 1.
- "Es
como hacer un ordenamiento de burbuja pero comparando e intercambiando
elementos."
- Cuando
el incremento toma un valor de 1, todos los elementos pasan a formar parte
del subgrupo y se aplica inserción directa.
- El
método se basa en tomar como salto N/2 (siendo N el número de elementos) y
luego se va reduciendo a la mitad en cada repetición hasta que el salto o
distancia vale 1.
Algoritmo:
Ejemplo Para el arreglo a = [6, 1, 5, 2, 3, 4, 0]
tenemos el siguiente recorrido:
Recorrido
|
Salto
|
Lista
|
Intercambios
|
1
|
3
|
2,1,4,0,3,5,6
|
(6,2), (5,4), (6,0)
|
2
|
3
|
0,1,4,2,3,5,6
|
(2,0)
|
3
|
3
|
0,1,4,2,3,5,6
|
Ninguno (cuando no hay intercambios se procede a
cambiar el valor de K o Salto)
|
4
|
1
|
0,1,2,3,4,5,6
|
(4,2), (4,3)
|
5
|
1
|
0,1,2,3,4,5,6
|
Ninguno
|
Análisis del algoritmo.
- Estabilidad:
Este algoritmo se considera estable.
- Requerimientos
de Memoria: Una variable adicional para realizar los intercambios. Y una
variable para el salto. Requerimiento constante.
- Tiempo
de Ejecución: Los estudios realizados indican que su complejidad es de
O(n^1.2) en el mejor caso y de O(n^1.25) en el caso promedio.
Algoritmos
de ordenamiento Recursivo
Dentro de los algoritmos de ordenamiento recursivo
se encuentran los métodos de MergeSort (Ordenación por mezclas sucesivas) y
QuickSort (Ordenamiento Rápido).
MergeSort
El algoritmo Merge divide el arreglo original en
dos arreglos y los coloca en arreglos separados. Cada arreglo es recursivamente
ordenado y finalmente se unen los arreglos en un arreglo ordenado. Como
cualquiera de los algoritmos de ordenamiento recursivo el algoritmo Merge tiene
complejidad de O(n log n). Fue desarrollado por John Von Neumann.
Este método aplica la técnica divide-y-vencerás, dividiendo
la secuencia de datos en dos subsecuencias hasta que las subsecuencias tengan
un único elemento, luego se ordenan mezclando dos subsecuencias ordenadas en
una secuencia ordenada, en forma sucesiva hasta obtener una secuencia única ya
ordenada. Si n = 1 solo hay un elemento por ordenar, sino se hace una
ordenación de mezcla de la primera mitad del arreglo con la segunda mitad. Las
dos mitades se ordenan de igual forma. Ejemplo: Se tiene un arreglo de 8
elementos, se ordenan los 4 elementos de cada arreglo y luego se mezclan. El
arreglo de 4 elementos, se ordenan los 2 elementos de cada arreglo y luego se
mezclan. El arreglo de 2 elementos, como cada arreglo sólo tiene n = 1
elemento, solo se mezclan.
Ejemplo Esquema procedimiento Algoritmo MergeSort
Análisis del algoritmo.
- Estabilidad:
Sí es estable.
- Requerimientos
de Memoria: Se necesita memoria auxiliar del mismo tamaño de los conjuntos
a mezclar.
- Tiempo
de Ejecución: O(n log n).
Ventajas
|
Desventajas
|
A) Rápido
|
A) Implementación compleja.
|
B) Especial para datos atómicos o registros con
pocos componentes
|
B) Grandes Requerimientos de Memoria
|
La ordenacion rapida, inventada y nombrada por
C.A.R. Hoare en 1960, esta considerada como el mejor algoritmo de ordenacion
disponible actualmente. Esta basada en la ordenacion por el metodo de
intercambio.
La ordenacion rápida se basa en la idea de las
particiones. El procedimiento general es seleccionar un valor llamado
COMPARANDO y entonces dividir el array en dos partes. En un lado todos los
elementos mayores o iguales al valor de particion y en otro todos los elementos
menores que el valor. Este proceso se repite en cada parte restante hasta que
el array esté ordenado.
Como se puede ver, este proceso es esencialmente
recursivo por naturaleza y, de hecho, las implementaciones mas claras de la
ordenacion rapida es por algoritmos recursivos.
La seleccion del valor comparado se puede obtener
de dos formas. Se puede seleccionar aleatoriamente o haciendo la media de un
pequeno conjunto de valores tomados del array. Para una ordenacion optima es
mejor seleccionar un valor que este precisamente en medio del rango de valores.
Sin embargo, esto no es facil de hacer en la mayoria de los conjuntos de datos.
En el caso peor, el valor escogido esta en un extremo. Incluso en este, la
ordenacion rapida todavia funciona bien. La version de la ordenacion rapida que
sigue selecciona el elemento mitad del array. Aunque no siempre sera una buena
eleccion, la ordenacion sigue funcionando correctamente.
Método de ordenamiento Burbuja
for ( i=1; i
for( j=0;j
if (a[j] > a[j+1])
temp = a[j];
a[j]= a[j+1];
a[j+1]= temp;
}
Ventajas:
- Fácil implementación.
- No requiere memoria adicional.
Desventajas:
- Muy lento.
- Realiza numerosas comparaciones.
- Realiza numerosos intercambios.
Método de ordenamiento por selección
for (i=0; i
pos_men = Menor(lista, TAM, i)
temp = lista[i];
lista[i] = lista [pos_men];
lista [pos_men] = temp; }
Menor(lista,TAM,i) es una función que
busca el elemento menor del arreglo llamado lista que se encuentra entre las
posiciones i y la posición TAM, y devuelve la el identificador. A continuación
se encuentra el código de la función:
int menor (tipo arreglo, int largo, int j) {
tipo menor=arreglo[j];
int pos_menor=j;
for (j++;j
if (arreglo[j]
menor=arreglo[j];
pos_menor=j;
}
return pos_menor;
} //Fin del for
Ventajas:
- Fácil implementación.
- No requiere memoria adicional.
- Realiza pocos intercambios.
- Rendimiento constante: poca diferencia entre el peor y el mejor caso.
Desventajas:
- Lento.
- Realiza numerosas comparaciones.
Ordenamiento por inserción
for (i=1; i
temp = lista[ i ];
j = i - 1 ;
while ( (lista[ j ] > temp) && (j >= 0) ) {
lista[ j+1] = lista[ j ] ;
j-- ;
} //Fin while
lista [ j+1] = temp;
}//Fin for
Ventajas:
- Fácil implementación.
- Requerimientos mínimos de memoria.
Desventajas:
- Lento.
- Realiza numerosas comparaciones
Quicksort
El algoritmo quicksort es quizá el
más eficiente de los algoritmos de ordenamiento, debido a que su complejidad es
mínima y por lo tanto su tiempo de ejecución también es mínimo. Se divide la
lista en dos sublistas y ordenarlas en forma independiente cada una. El proceso
de partición es repetido hasta llegar a listas de tamaño 1 (que están
ordenadas).
Lo central en este método es
encontrar un método eficiente para particionar la lista en dos partes, tal que:
Todos los elementos de una sub-lista
deben ser menores que un elemento llamado pivote.
Todos los elementos en la otra sub-lista deben ser mayores que el pivote.
Si asumimos que los elementos de la
lista están almacenados en un arreglo, el método para particionar el arreglo en
dos es como sigue:
1. Escoja un
elemento en el arreglo como pivote. Por conveniencia, usaremos el primer
elemento del arreglo.
2. Ponga un
índice al segundo elemento del arreglo (i1) y otro al último elemento (i2).
3. Decremente i2 hasta
que encuentre un elemento con valor menor que el pivote o i2 llegue
a i1. Incremente i1 hasta que encuentre un
elemento mayor que el pivote o hasta que i1 llegue a i2.
Llamaremos a este proceso “búsqueda”.
4. Si los dos
índices son distintos, los dos elementos del arreglo (los apuntados por i2 e i1)
están fuera de lugar, por lo que se intercambian. Repita el paso anterior de
búsqueda, resumiendo la operación donde se había quedado.
5. Si los dos
índices son iguales y el valor que ambos índices apuntan es menor que el pivote,
intercámbielos. El arreglo está ahora particionado por el elemento referenciado
por i2 (o i1). La localización del pivote separa
el arreglo en una porción donde todos sus valores son menores que el pivote, y
otra porción donde todos sus valores son mayores que el pivote.
BIBLIOGRAFIA
http://elbrilloestaensertumismo.blogspot.com/2008/10/metodos-de-manejo-de-archivos-clases.html
http://artemisa.unicauca.edu.co/~nediaz/EDDI/cap03.htm
