Metodos de ordenamiento

Vista previa del material en texto

Métodos de ordenamiento 
Son operaciones para organizar y ordenar 
un conjunto de datos (por ej.: 
vectores, archivos), con un determinado 
criterio u orden. 
A continuación veremos diferentes 
métodos, que se diferencian 
principalmente en su complejidad y 
eficiencia. 
 
Método de la burbuja 
(Bubble sort) 
Este método es el mas sencillo de 
implementar. 
 Se basa en comparaciones (if), con la 
utilización de una variable auxiliar, que 
permite intercambiar el contenido de 2 
posiciones (para no perder el contenido de 
estos), en un vector. 
A su vez, es el método que mas 
comparaciones hace, por lo que resulta el 
menos eficiente. 
Método de la burbuja 
(Bubble sort) 
 Se basa en el siguiente razonamiento: 
Ej.: cargo 2 números en un vector: 10, 5, quiero 
ordenarlos de menor a mayor. 
Lo resuelvo con una comparación: 
 
si vector(1) > vector(2) entonces 
 auxiliar = vector(1) 
 vector(1) = vector(2) 
 vector(2) = auxiliar 
fin si 
Método de la burbuja 
(Bubble sort) 
Si tenemos mas elementos (n), llegamos al algoritmo 
genérico, agregando 2 ciclos para (for): 
 
para i = 1 hasta n 
 para j = 1 hasta n-1 
 si vector(j) > vector(j+1) entonces 
 auxiliar = vector(j) 
 vector(j) = vector(j+1) 
 vector(j+1) = auxiliar 
 fin si 
 fin para j 
fin para i 
Método de la burbuja 
(Bubble sort) 
El segundo ciclo para, se ejecuta n-1 veces, 
dado que es la cantidad de comparaciones 
necesarias para que los elementos queden 
ordenados. 
La eficiencia de este algoritmo, es 
independiente de que tan ordenados estén 
los números (porque compara uno por 
uno). 
Método de inserción 
(Insertion sort) 
También conocido como método de la baraja, por 
la forma en la que se intercambian los 
elementos. 
 Consiste en insertar uno de los elementos entre 
uno menor y otro mayor, de modo que se 
desplazaran los elementos para ubicarlo. 
Se utilizan ciclos, comparaciones, y banderas 
(flags). 
Una bandera es una variable binaria, que tiene un 
funcionamiento similar al de un interruptor 
(prendido/apagado). 
 
Método de inserción 
(Insertion sort) 
Tenemos un vector, ej.: 2 7 3 5 4 
Tomamos el 4, es mayor que 3 y menor que 5, 
lo insertamos en ese lugar. 
obtenemos: 2 7 3 4 5 
A este proceso se le agrega un ciclo para, un 
ciclo mientras, y una bandera, para llegar al 
siguiente código: 
Método de inserción 
(Insertion sort) 
para i = 2 hasta n 
 auxiliar = vector(i) 
 k = i - 1 
 bandera = 0 „(simula el estado apagada o false) 
 mientras (bandera = 0) y (k >= 1) 
 si auxiliar < vector(k) entonces 
 vector(k+1)=vector(k) 
 k = k - 1 
 sino 
 bandera = 1 „(simula el estado prendida o true) 
 fin si 
 fin mientras 
 vector(k+1) = auxiliar 
fin para i 
 
 
Método de inserción 
(Insertion sort) 
Este método tendrá su cantidad de 
comparaciones e inserciones, dependientes 
de que tan ordenado estén los elementos, 
siendo el mínimo=n-1 (para el mejor caso). 
Tiene complejidad media-baja en su 
implementación, y resulta muy útil para 
conjuntos con pocos elementos. 
 
Método de selección 
(Selection sort) 
 Este método es bastante sencillo, si se conoce 
como obtener el mayor o menor 
elemento de un vector. 
Si se desea ordenar de menor a mayor; se 
buscara el menor y en caso contrario se 
buscara el mayor. 
Cuando se obtiene el menor (caso: menor a 
mayor), se lo ubica en la primera posición del 
vector; luego se busca el segundo menor en la 
segunda posición, y así sucesivamente. 
Método de selección 
(Selection sort) 
Como primer paso, buscamos el menor elemento (y lo 
trasladamos a la primera posición), utilizando una 
lógica de búsqueda: 
 
minimo = vector(1) 
para j = 2 hasta n 
 si vector(j) < vector(1) entonces 
 minimo = vector(j) 
 fin si 
fin para j 
vector(1) = minimo 
Método de selección 
(Selection sort) 
De forma genérica, agregamos un ciclo para hasta n-1 (dado que el 
ultimo quedara ordenado) 
 
para i = 1 hasta n-1 
 minimo = vector(i) 
 posicion = i 
 para j = i + 1 hasta n 
 si vector(j) < minimo entonces 
 minimo = vector(j) 
 posicion = j 
 fin si 
 fin para j 
 vector(posicion) = vector(i) 
 vector(i) = minimo 
fin para i 
Método de selección 
(Selection sort) 
Este método, realizara menos comparaciones 
que el método de la burbuja y también es 
independiente de que tan ordenados están 
los elementos. 
Su complejidad es baja, casi al nivel del 
método de la burbuja. 
Método de Shell 
(Shell sort) 
Es una mejora del método de inserción 
(creado por Donald Shell), basado en la 
cantidad de comparaciones; esto hace 
que sea una mejor opción para una mayor 
cantidad de elementos. 
Las comparaciones se reducen mediante 
pasos mas grandes, que permiten llegar mas 
rápido al intercambio (inserción). 
 
Método de Shell 
(Shell sort) 
 Se toma como paso n/2 (siendo “n” la 
cantidad de elementos), se divide 
sucesivamente hasta que sea igual a 1 
(aplicando redondeo en las divisiones), y a 
eso le llamaremos “salto”. 
La lógica es mas compleja, pero como 
beneficio tenemos mayor eficiencia en el 
algoritmo: 
Método de Shell 
(Shell sort) 
salto = int(n/2) 
mientras salto >= 1 
 para i = salto + 1 hasta n 
 j = i - salto 
 mientras j>0 
 k = j + salto 
 si vector(j) <= vector(k) entonces 
 j=0 
 sino 
 auxiliar = vector(j) 
 vector(j) = vector(k) 
 vector(j) = auxiliar 
 fin si 
 j = j - salto 
 fin mientras 
 fin para i 
 salto = int(salto/2) 
fin mientras 
Método de Shell 
(Shell sort) 
Como se puede ver en el código, es un algoritmo 
refinado del método de inserción, sin mas que 
la variable “salto”, cuya finalidad es disminuir la 
cantidad de comparaciones. 
Los saltos son dependientes de la cantidad de 
números y de que tan ordenados están estos; 
esto hace que sea muy difícil determinar 
cuantas comparaciones necesitamos para 
ordenar un conjunto de elementos. 
Método de ordenación rápida 
(Quicksort) 
Este método es el mas rápido de los 5 en 
estudio, basado en la técnica “divide y 
vencerás”. 
Esta técnica nos dice que resolver un 
problema entero, naturalmente es mas difícil 
que resolverlo en partes. 
 
Método de ordenación rápida 
(Quicksort) 
Se divide la lista de elementos en 2 listas, y un 
“pivote” (elemento especifico). El pivote es un 
elemento de la lista, deberá utilizarse un criterio 
para la elección del mismo. 
Una de las listas debe contener todos sus valores 
menores que el pivote, y la otra todos sus valores 
mayores a este. 
Cada lista se ordenara con la misma técnica 
(intercambiar mayores y menores), por lo que se 
utilizara la recursividad. 
A continuación, un DFD que representa esta lógica. 
Método de ordenación rápida 
(Quicksort) 
Método de ordenación rápida 
(Quicksort) 
Llamar a quicksort 1 , n 
procedimiento quicksort inicio , fin 
 i = inicio 
 j = fin 
 pivote = vector(i) 
 mientras i <= j 
 mientras vector(i) < x 
 i = i + 1 
 fin mientras 
 mientras vector(j) > x 
 j = j – 1 
 fin mientras 
 si i <= j entonces 
 auxiliar = vector(i) 
 vector(i) = vector(j) 
 vector(j) = auxiliar 
 i = i + 1 
 j = j – 1 
 fin si 
 fin mientras 
 si j > inicio entonces 
 llamar a quicksort inicio , j 
 fin si 
 si i < fin entonces 
 llamar a quicksort i , fin 
 fin si 
fin procedimientoMétodo de ordenación rápida 
(Quicksort) 
Como vemos, es el mas complejo y el mas 
eficiente a la vez; por lo que es el mas 
utilizado (porque mayormente se busca 
eficiencia en los algoritmos). 
Pero esta es una implementación que utiliza el 
criterio del primer elemento como pivote; 
existen mas criterios, y estos también 
determinan la eficiencia del algoritmo.