Método de Ordenamiento BURBUJADEFINA Y EXPLIQUE DE FORMA CLARA Y SENCILLA EL MÉTODO DE ORDENACIÓN POR BURBUJA. CITE SUS VENTAJAS Y DESVENTAJAS. El ordenamiento es uno de los procesos más comunes y útiles en el procesamiento de datos, es la clasificación u ordenación de los mismos. La colocación en orden de una lista de valores se le llama ordenación. Por ejemplo, se podría disponer de una lista de valores numéricos en orden ascendente o descendente, o bien una lista de nombres en orden alfabético.
El método de ordenación por burbuja es el mas conocido y popular entre estudiantes y aprendices de programación.
Este método se basa en la ordenación por cambios de elementos, ya que se van comparando de dos en dos los elementos de la tabla (vector). Si nosotros deseamos ordenar dicha tabla de menor a mayor (ascendente) al realizar la comparación entre dos elementos se produce el intercambio en el momento en que el primer elemento es mayor que el segundo. De esta forma los elementos más grandes pasan a estar en el último lugar de la tabla. El elemento sube por la tabla al igual que una burbuja en un recipiente, de ahí proviene su nombre.
La técnica consiste en hacer varias pasadas a través de la tabla, en cada pasada se comparan parejas sucesivas de elementos. Si una pareja esta en orden creciente (o los valores son idénticos), se dejan los valores como están. Si una pareja esta en orden decreciente, sus valores se intercambian en la tabla.
Supongamos que tenemos una tabla de un total de 50 elementos y que desde un principio esta ordenada, pero eso nosotros no lo sabemos, por lo que sometemos la tabla a una ordenación. Como te puedes imaginar el programa esta empleando un tiempo que nos puede ser útil, para realizar cualquier otro calculo dentro de la aplicación. Piensa que con una tabla de 50 elementos el programa pasara por el bucle principal 49 veces. Podemos ver que es un método un poco rudimentario y un poco largo según el caso.
Este método dentro de lo sencillo, es que nos permite una mejora. Esta mejora consiste en terminar el bucle principal en el momento en el que detectemos que en una pasada, por todo lo largo de la tabla no ha habido ningún cambio, esto quiere decir que la tabla esta completamente ordenada.
Ventajas:
Este método es fácil de comprender, programar y es el más extendido.
Es bastante sencillo
En un código reducido se realiza el ordenamiento
Eficaz
Trabaja in situ.
Emplea operacionales en promedio para ordenar elementos.
Su bucle interno extremadamente corto.
Desventajas:
Ø Su desventaja principal, es uno de los menos eficientes y por ello, normalmente, se aprende su técnica pero no se utiliza.
Ø Consume bastante tiempo de computadora
Ø Requiere muchas lecturas/escrituras en memoria
Ø Es recursivo y su implementación no recursiva es complicada.
Ø El desempeño es en su peor caso.
La ordenación o clasificación es el proceso de organizar datos en algún orden o secuencia específica tal como creciente o decreciente para datos numéricos o alfabéticamente para datos de caracteres.
El Método de la Burbuja o Intercambio se basa en el principio de comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que estén todos ordenados.
Supongamos que se desea clasificar en orden ascendente el vector o lista:
50 15 56 14 35 1 12 9
A (1) A (2) A (3) A (4) A (5) A (6) A (7) A (8)
Los pasos a dar son:
1.- Comparar A (1) y A (2); si están en orden, se mantienen como están; en caso contrario se intercambian entre sí.
2.- A continuación se comparan los elementos 2 y 3; de nuevo se intercambian si es necesario.
3.- El proceso continúa hasta que cada elemento del vector ha sido comparado con sus elementos adyacentes y se han realizado los intercambios necesarios.
El método expresado e pseudos código en el primer diseño es:
Desde I=I hasta 7 hacer
Si elemento (I)> elemento (I+I)
Entonces intercambiar elementos (I, I+I)
Fin_si
Fin_desde
La acción intercambiar entre sí los valores de los elementos A (I), A (I+I), es una acción compuesta que contiene las siguientes acciones, considerando una variable auxiliar AUX.
AUX ← A (I)
A (I) ← A (I+I)
A (I+I) ←AUX
ORDENACIÓN POR EL MÉTODO DE LA BURBUJA
Este método consiste en acomodar el vector moviendo el mayor hasta la última casilla comenzando desde la casilla cero del vector hasta haber acomodado el número más grande el la última posición, una vez acomodado el más grande, prosigue a encontrar y acomodar el siguiente más grande comparando de nuevo los números desde el inicio del vector, y así sigue hasta ordenar todo los elementos el arreglo. Este algoritmo es muy deficiente ya que al ir comparando las casillas para buscar el siguiente más grande, éste vuelve a comparar las ya ordenadas. A pesar de ser el algoritmo de ordenamiento más deficiente que hay, éste es el más usado en todos los lenguajes de programación.
Entonces:
Dado un vector a1, a2, a3, ... an
1) Comparar a1 con a2 e intercambiarlos si a1>a2 (o a1<A2) 2) Seguir hasta que todo se haya comparado an-1 con an 3) Repetir el proceso anterior n-1 veces Algoritmo: Complejidad
for(i=0; i < n-1; i++){ T(n2)
for(j=0; j < n-1; j++){ T(n)
if(vec[j] > vec[j+1]){ T(1)
aux=vec[j]; T(1)
vec[j]=vec[j+1]; T(1)
vec[j+1]=aux;} T(1)
}
}
El procedimiento de la burbuja es el siguiente:
Ir comparando desde la casilla 0 numero tras número hasta encontrar uno mayor, si este es realmente el mayor de todo el vector se llevará hasta la última casilla, si no es así, será reemplazado por uno mayor que él.
Este procedimiento seguirá así hasta que haya ordenado todas las casillas del vector.
Una de las deficiencias del algoritmo es que ya cuando a ordenado parte del vector vuelve a compararlo cuando esto ya no es necesario.
PRIMERA MEJORA DEL METODO DE LA BURBUJA:
La primera pasada a lo largo del vector deja el número mayor en el extremo derecho. La segunda pasada deja los dos números mayores ordenados en el extremo derecho, y así hasta quedar el vector ordenado ascendentemente.
A comparación con el método de la burbuja que compara parte del vector cuando ya esta ordenado, este no lo hace ya que ahora tiene el límite para no llegar a comparar a donde ya ordeno.
Algoritmo (Orientado a C)
Complejidad for (i=0; i < n-1; j++){ T(n2)
for (j=0; j < (n-1)-i; j++){ T(n)
if (a(j) > a(j+1) ){ T(1)
aux = a(j); T(1)
a(j) = a(j+1); T(1)
a(j+1) = aux; T(1)
}
}
}
Métodos de Ordenación Elementales:
Los métodos de ordenación elementales proporcionan:
Una terminología básica
Un mecanismo básico que puede extenderse a otros métodos más generales, sofisticados y con mejor desempeño.
Típicamente, los métodos de ordenación elementales tienen peor desempeño que los sofisticados, pero existen muchas aplicaciones en las que es mejor utilizar un método de ordenación elemental. Por ejemplo, cuando el algoritmo se utiliza pocas veces y/o se ordenan pocos elementos.
Como regla general se tiene que los métodos elementales necesitan cerca de pasos para ordenar elementos organizados al azar.
En general, no se recomienda su uso para ordenar:
Archivos grandes
Archivos clasificados aleatoriamente.
Por su parte, métodos mas avanzados pueden lograr desempeños de orden NlogN, , . Mas aún, se puede demostrar que ningún método de
Ordenación puede utilizar menos de NlogN comparaciones entre claves cuando éstas están organizadas al azar.
Terminología General: En el contexto de los métodos de ordenación, cada elemento de dato tiene su clave, y los métodos de ordenación trabajan ordenando los elementos de dato según sus claves. Por lo regular, los métodos comparan las claves e intercambian los elementos de dato. En lugar de desplazar físicamente los elementos de datos, con frecuencia, sólo se intercambian índices, punteros o referencias. Esto se denomina ordenación indirecta.
Un método de ordenación que trabaja sobre un conjunto de datos que se encuentra en memoria e.g., un arreglo, una lista se dice que es un método de ordenación interna. Por el contrario, si el conjunto de datos almacenados en archivos no pueden ser cargados en memoria por ejemplo, por razones de tamaño y el método de ordenación opera sobre los archivos, se dice que es de ordenación externa. Evidentemente, en la ordenación interna se accede a los elementos de dato más fácilmente, mientras que en la ordenación externa se accede a los elementos de dato de forma secuencial o al menos en grades bloques.
Los métodos de ordenación se pueden clasificar de acuerdo a sus requerimientos de memoria. Los métodos in situ son aquellos que requieren ninguna o muy poca memoria extra. En el otro extremo, existen métodos que requieren mucha memoria extra.
Una característica que puede ser importante es la estabilidad del método de ordenación. Un algoritmo de ordenación es estable si elementos de dato con la misma clave conservan su orden relativo luego de su aplicación. Típicamente, los métodos elementales son estables mientras que la mayoría de los algoritmos sofisticados no lo son.
Entre los métodos de ordenación elementales están Selección e Inserción, los cuales son descritos a continuación.
Método de Ordenación por Seleccion: Supongamos que tenemos un arreglo con los datos, entonces el procedimiento es como sigue:
Ø se sitúa en el primer elemento (i=0).
Ø se busca el elemento más pequeño de arreglo (desde i hasta el final).
Ø se intercambia el elemento más pequeño con el que está en la posición i.
Ø se incrementa i (i++).
Nótese que se gasta la mayor parte del tiempo en intentar en encontrar el elemento mínimo.
A continuación se presenta una implementación en Java del método de ordenación por selección:
/**
* Clase que implementa métodos de ordenación elementales.
*/ public class Sorting
{
static public void selectionSort(Comparable array[])
{ // No se incluye validación de parámetro de entrada.
int min; for (int i = 0; i < array.length; i++)
{
min = i;
for (int j = i + 1; j < array.length; j++)
{
if (array[j].compareTo(array[min]) < 0)
{
min = j;
}
}
Sort.swap(array, min, i);
}
}
private static void swap(Comparable[] array, int i, int j)
{
Comparable tmp = array[i];
array[i] = array[j];
array[j] = tmp; }
}
El método de ordenación por selección:
Ø está basado en el enfoque de fuerza bruta
Ø funciona bien con archivos pequeños
Ø cada elemento se mueve sólo una vez
Método de Ordenación por Inserción:
Considere que los elementos están uno tras otro, el método consiste en insertar cada elemento en el lugar apropiado entre los elementos que ya han sido considerado manteniéndolos ordenados. Es similar a la forma en que se ordena un juego de cartas.
Por ejemplo:
E J E M P L O A O R D E N A R
E J
E J E
E E J M
E E J M P
E E J M P L
E E J L M P...
A continuación se muestra una implementación en Java del método de ordenación por inserción.
Static public void insertion Sort (Comparable array[])
{ // No se incluye validación de parámetro de entrada.
int min; for (int i = 1; i < array.length; i++)
{
Comparable tmp = array[i];
int j;
for (j = i; j > 0 && tmp.compareTo(array[j-1]) < 0; j--)
{
array[j] = array[j-1];
}
array[j] = tmp;
} }
Características de Rendimiento de los Metodos de Ordenacion Elementales: La simple inspección de las implementaciones anteriores sirve de evidencia de que los métodos elementales son cuadráticos tanto en el peor caso como en el caso medio y no necesitan memoria extra in situ. La ordenación por selección utiliza aproximadamente comparaciones y intercambios. El número de comparaciones está dado por: .
Si entonces el número de comparaciones es igual a . Por otra parte, puede haber máximo intercambios. Estos resultados son independientes del conjuntos de datos de entrada, entonces se dice que el método de selección es insensible a los datos de entrada. La ordenación por inserción utiliza aproximadamente comparaciones y intercambios en el caso medio y dos veces más en el peor caso ( comparaciones y intercambios). Nótese que cuando el archivo está ordenado la ordenación por inserción es lineal ( ).
Muchas veces se abusa de los métodos de ordenación de propósito general, en especial en estos casos donde el método de inserción supera a los métodos sofisticados. Por ejemplo, supongamos que se desea añadir algunos elementos a una lista ordenada para obtener una lista ordenada más grande.
Para ello:
Ø Añada los nuevos elementos al final del archivo
Ø Llame al método de ordenación por inserción
Ø Se puede demostrar que cualquier algoritmo de ordenación que intercambie elementos adyacentes tiene un tiempo de ejecución promedio (cota inferior).
Metodo de Ordenación de Shell (Shell Sort): Fue uno de los primeros métodos en romper la barrera del tiempo cuadrático. Ya sabemos que cualquier algoritmo de ordenación que intercambie elementos adyacentes tendrá un tiempo promedio de ejecución de orden cuadrático.
Qué podemos para tratar de mejorar eso Simplemente hacer comparaciones e intercambios entre elementos no adyacentes es decir, más apartados. En consecuencia, Shell Sort compara elementos que están distantes, y esta distancia disminuye en la medida que el algoritmo progresa hasta la última fase en la cual se comparan elementos adyacentes.
Shell Sort utiliza secuencias de incrementos del tipo: donde y . Después de una fase y habiendo usando un incremento , para cada elemento i se cumple que , es decir que todos los elementos espaciados están ordenados. En este caso se dice que tenemos una archivo -ordenado. En cada fase se realizan ordenaciones por inserción en arreglos independientes.
A continuación se presenta un ejemplo de la ejecución de Shell Sort con la secuencia {5, 3, 1}:
Propiedad 1: un archivo -ordenado que es luego -ordenado, mantiene su condición de -ordenado. Nótese que el desempeño del algoritmo depende de la secuencia seleccionada y que unas secuencias son mejores que otras. Algunas de las secuencias más utilizadas son las siguientes:
y : es una secuencia que ofrece pobre desempeño (peor caso: ).
Incremento de Hibbard: (peor caso: , caso promedio: ).
Incremento de Sedgewick: (nunca hace más de comparaciones).
Una de las mejores secuencias es y está dada por: ó .
Se ha comprobado que la cota aplica a muchas secuencias.
A continuación se presenta una implementación en Java del método de ordenación de Shell que utiliza la secuencia de Sedgewick.
static public void shellSort(Comparable array[])
// No se incluye validación de parámetro de entrada.
Comparable tmp; int h = 0;
// generate the sequence
for (h = 0; h < array.length; h=3*h+1);
for (; h>0; h/=3)
{
for (int i = h; i < array.length; i++)
{
tmp =array[i];
int j = i;
while (j>=h && tmp.compareTo(array[j-h]) < 0)
{
array[j] = array[j-h];
j-=h;
}
array[j] = tmp;
} }
}
Ordenacion por Fusión (MergeSort):
Es un algoritmo recursivo (de tipo divide y vencerás) cuyo tiempo de ejecución es de en el peor caso, y el número de comparaciones usadas es cercana al óptimo.
La operación fundamental sobre la cual se basa este algoritmo es: funcionar 2 arreglos (listas) ordenados en un arreglo (lista) mayor también ordenado. Esta operación se puede realizar en un sólo paso por la entrada, si la salida es puesta en su tercer arreglo. Supóngase que tenemos como entrada dos arreglos de elementos ya ordenados (A[N] y B[M]) y como salida el arreglo C[N+M]; adicionalmente tenemos las variables enteras contadores a, b y c inicializadas en 0 que servirán para manejar los índices de los arreglos. Dado esto la operación se realiza de la siguiente manera:
El menor de A[a] y B[b] es colocado en C[c] y se incrementan los contadores apropiados.
Cuando se llega al final de alguno de los arreglos de entrada el resto del otro arreglo es copiado a C.
Ejemplifica la operación básica de fusionar dos arreglos ordenados.
Mezclar dos arreglos (listas) ordenados(as) en otro(a) ordenado(a) es un proceso lineal: cuando más se realizan comparaciones, donde es el número total de elementos.
Descripción
Los pasos son lo siguientes:
Si N=1 sólo existe un elemento a ordenar y ya se tiene la solución.
En caso contrario, aplique recursivamente la operación mergeSort(...) sobre la primera y segunda mitad del arreglo
Finalmente, esto resulta en dos mitades ordenadas que pueden funcionarse utilizando la operación fundamental descrita anteriormente.
Detalle de implementación: cuando el arreglo a ordenar es pequeño (e.g., 20 elementos o menos) dentro de una llamada recursiva, en lugar de continuar recursivamente se utiliza el método de ordenación por inserción.
Desempeño Para realizar el análisis del algoritmo empleamos la siguiente secuencia: y , donde es el número de elementos a ordenar. En la parte derecha de la igualdad de la segunda ecuación, el primer término de corresponde a las dos llamadas recursivas del algoritmo, mientras el segundo corresponde a la mezcla que es lineal.
Características
El algoritmo de ordenación por fusión:
Necesita alrededor de comparaciones para ordenar un archivo de elementos.
Utiliza un espacio extra proporcional a (no es in situ).
Es estable.
Es insensible al orden inicial de la entrada.
QuickSort: Es probablemente el más utilizado de los algoritmos de ordenación. Fue inventado por C.A.R. Hoare2 en 1960 y desde entonces se han propuesto mejoras.
Es muy popular porque es relativamente fácil de implementar, ofrece buenos resultados generales, en muchos casos consume menos recursos otros método de ordenación, y está bien estudiado (ha sido expuesto a un minucioso análisis matemático que ha sido corroborado con amplia experiencia práctica).
Descripción
Es un algoritmo recursivo (de tipo divide y vencerás). Es decir, divide el arreglo en dos partes y las ordena independientemente. A continuación se presenta el algoritmo QuickSort en pseudocódigo.
Void quicksort(int a[], int izq, int der)
{
int i;
if (der>izq)
{
i= divide(a, izq, der);
quicksort(a, izq, i-1);
quicksort(a, i+1, der): }
}
Nótese que la llamada quicksort(a, 0, N-1) ordena el arreglo de N elementos en su totalidad.
Un montículo es un árbol binario completo completamente lleno excepto el último nivel que satisface las siguientes condiciones Condiciones de Montículo Binario:
Cada nodo debe tener mayor o igual prioridad a la de su hijos (si tiene alguno).
El nodo de mayor prioridad es la raíz.
Cualquier subárbol es un montículo binario.
Un árbol binario completo es sumamente regular3. Además, presenta la ventaja de que puede ser implementado mediante un arreglo sin necesidad de enlaces. Esto es: para cualquier elemento , el hijo izquierdo está en la posición , el hijo derecho en la posición y el padre en la posición . (Figura 5)
Esto favorece la implementación de operaciones simples y rápidas, aunque requiere la estimación de la capacidad máxima del arreglo, y su redimensionamiento dinámico (e.g., uso de la clase ArrayList).
Los algoritmos básicos que operan sobre montículos tienen las siguientes características:
Operan a lo largo de algún camino desde la raíz hasta el fondo del montículo excepto la unir dos montículos.
Comienzan haciendo una simple modificación estructural que potencialmente viola las condiciones del montículo, luego lo recorren y modifican para asegurar que dichas condiciones son restablecidas.
Por ejemplo, la operación de insertar un nuevo elemento involucra:
Agregar el elemento al final del arreglo, lo cual potencialmente viola la condición de montículo.
Hacer que el elemento recién agregado suba el montículo de forma tal que ocupe la posición que le corresponde y en consecuencia, restaurar la condición de montículo.
Por otra parte, la operación de extraer el elemento de mayor prioridad consiste en:
Asignar el primer elemento del arreglo a una variable temporal (item = a[1]).
Asignar el último elemento del arreglo a la primera posición y decrementar el tamaño del arreglo (a[1]=a[N-]), lo cual potencialmente viola la condición de montículo.
Hacer que el elemento recién colocado en la primera posición del arreglo baje el montículo de forma tal que ocupe la posición que le corresponde y en consecuencia, restaurar la condición de montículo.
Retornar el elemento asignado a la variable temporal item. |
|
