ItsxRadio

Nombre del Método

Burbuja Mejorada

Características Teóricas

Es un método iterativo. Es utilizado para resolver problemas que pueden involucrar muchas variables También se clasifica como un método de ordenamiento interno ya que trabajan en memoria principal y sus implementaciones son muy variadas y en función de la memoria disponible. Integra una variable llamada "bandera", la cual detecta los intercambios que se realizaron. La ordenación por burbuja o “bubble sort” se basa en comparar elementos contiguos del arreglo (vector) e intercambiar sus valores si no están en orden. De este modo, los valores de mayor rango se “hunden” hacia la parte inferior del arreglo y los de menor rango “burbujean” hacia la parte superior del arreglo.

La ordenación se basa en comparar los elementos adyacentes del arreglo e intercambiar valores, si es que están desordenados.

Si:

a [0] a [1] a [2] … a [n-1]

El método comienza a comparar a [0] con a[1]; si no están en orden, los intercambia entre sí. Después sigue comparando a [1] con a [2] y si no están en orden, los intercambia. Se sigue comparando e intercambiando hasta a [n-2] con a[n-1] si están en desorden. Estas operaciones son el primer recorrido a través del arreglo. Este proceso se repite durante n-1 recorrido, teniendo en cuenta que en el recorrido “i se ha puesto el elemento de mayor rango de las posiciones “0, 1, … n-i” en la posición “n-i”. De esta forma cuando i toma el valor de n-1, el vector esta ordenado.

Ventajas y Desventajas.

Ventajas del método:
Fácil de comprender y programar.

Es eficaz.
Consume menos recursos comparado con otros métodos de ordenación.

Desventajas:
Requiere muchas comparaciones
Requiere muchas lecturas/escrituras de memdsfiia
Es recursivo y su implementación no recursiva es complicada.
Es el menos eficiente de los métodos de ordenamiento.

Algoritmo Base

void burbujaM(int *v, int n) {
bool bandera = true;
int li = 0;
do

{
li++;
bandera = true;

for (int i = 0; i < n - li; i++) {
if ( v[i] > v[i+1] ) { // compara los valores
intercambia los datos
int tem = v[i];
v[i] = v[i+1];
v[i+1] = tem;
bandera= false;
}
}
}

while(!bandera);
}

Código en C

PARA DESCARGAR EL PROGRAMA 

AQUÍ EL LINK Y ABAJO EL CÓDIGO

http://www.mediafire.com/view/ebj6k6vf7zwsc4z/burbujaMEJORADA.c

#include
#include
#include
main(){
float X[100], AUX;

int N, paso, j;
int bandera=1;
clrscr();

printf("Cuantos n£meros va a ingresar: ");
scanf("%i",&N);
for(j=0;j 

{

printf("Deme un numero: ");
scanf("%f",&X[j]);
}
for(paso=0;paso {
bandera=0;
for(j=0;j
{
if(X[j] {
bandera=1;
AUX=X[j];
X[j]=X[j+1];
X[j+1]=AUX;
}
}
}
printf("\nLos numeros ordenados de mayor a menor son:\n");
for(j=0;j {
printf("%.2f\n",X[j]);
}
bandera=1;
for(paso=0;paso {
bandera=0;
for(j=0;j {
if(X[j]>X[j+1])
{
bandera=1;
AUX=X[j]; 

X[j]=X[j+1];
X[j+1]=AUX;
}
}
}
printf("\ny de menor a mayor:\n");
for(j=0;j {
printf("%.2f\n",X[j]);
}
getch();
}

Código en Java

PARA DESCARGAR EL PROGRAMA

EN EL LINK DE ABAJO

http://www.mediafire.com/view/d2djpgxjavm1aop/codigo%20en%20java.txt

class OrdenaAlgoritmo {
    public static void ordenar( int [] arreglo) {
 int pasadas = 0;
 int comparaciones = 0;
 for (int i = 0; i < arreglo.length; i++) {
     ++pasadas;
     for (int j = 0; j < arreglo.length - 1; j++) {
  ++comparaciones;
  if (arreglo[j] > arreglo[j + 1]) {
      intercambiar(arreglo, j, j+1);
  }
     }
 }
 estadisticas(pasadas, comparaciones);
    }

    public static void ordenarMejorado( int [] arreglo) {
 int pasadas = 0;
 int comparaciones = 0;
 boolean hayCambios = true;
 for (int i = 0; hayCambios ; i++) {
     ++pasadas;
     hayCambios = false;
     for (int j = 0; j < arreglo.length - 1; j++) {
  ++comparaciones;
  if (arreglo[j] > arreglo[j + 1]) {
      intercambiar(arreglo, j, j+1);
      hayCambios = true;
  }
     }
 }
 estadisticas(pasadas, comparaciones);
    }

   private static void intercambiar(int [] arreglo, int a, int b) {
 int tmp = arreglo[a];
 arreglo[a] = arreglo[b];
 arreglo[b] = tmp;
    }

    private static void estadisticas( int pasadas, int comparaciones) {
 System.out.println( "Pasadas: " + pasadas );
 System.out.println( "Comparaciones: " + comparaciones );
    }
}

-----------------------------------------------------------------------------------------------------

public class OrdenaBurbuja {
    public static void  main (String args[]) {

 int  valores = {15,35,01,05,04,03,19,45,13,02,55,8,
    78,997,451,546,12,16,24,103,99,784,
    4541,15};

 //OrdenaAlgoritmo.ordenar(valores);
 OrdenaAlgoritmo.ordenarMejorado(valores);
 // Mostrar arreglo.
 for (int i = 0; i < valores.length ; i++)
     System.out.println ( "valores["+i+"]: "+  valores[i]);
 
    }
}

Fórmulas

Para calcular el total de comparaciones:

(n - 1 )* (n – 1) = n^2 - 2n + 1 = O(n^2)

Para calcular el total de iteraciones:

2kn - k^2 – k / 2 = 0(n^2)

VIDEO

http://www.youtube.com/watch?v=P4nS6rlZjZ8

Análisis de la complejidad del algoritmo

Por Tiempo:
El ordenamiento se acelera haciendo que el recorrido vaya en direcciones opuestas para que los elementos más pequeños se muevan rápidamente a la parte de superior o delantera del arreglo al mismo tiempo que los más grandes se muevan a la parte inferior o posterior del arreglo.

Por Espacio:
Requiere poco espacio adicional (un registro adicional para contener el valor temporal para intercambiar varias variables) y que es 0(n).

Por Costo:
Dependerá del número total de intercambios los cuales no deben ser mayor que la cantidad de comparaciones porque es probable que la cantidad de intercambios ocupe más tiempo de la ejecución del programa.

Peor caso:
Es cuando se considera el mayor tiempo posible para hacer los intercambios y realizar el ordenamiento. O(nlog n)

Caso probabilístico:
Dependerá del orden en que van entrando los datos, pero solo es un poco mejor al peor caso. Y sigue siendo O(n^2).

Función de Complejidad

La función de complejidad es cuadrática debido a que n elementos requieren n-1 recorridos para dejar el arreglo ordenado.

La formula es la siguiente:

(n - 1)* (n – 1) = n^2 - 2n + 1 = O(n^2)

Bibliografía

Estructura de datos con c y c++
Yedidyah Langsam, Moshe J. Augenstein y Aarón M. Tenenbaum