Algoritmos de ordenación. Metodo de la Burbuja

El algoritmo de la burbuja es uno de los métodos de ordenación más conocidos y uno de los primeros que aprenden los programadores.

Consiste en comparar pares de elementos adyacentes en un array y si están desordenanos intercambiarlos hasta que estén todos ordenados.

Si A es el array a ordenar, se realizan A.length-1 pasadas. Si la variable i es la que cuenta el número de pasadas, en cada pasada i se comprueban los elementos adyacentes desde el primero hasta A.length-i-1 ya que el resto hasta el final del array están ya ordenados. Si los elementos adyacentes están desordenados se intercambian.

El método de ordenación de la burbuja en java para ordenar un array A es el siguiente:

public static void burbuja(int [] A){
         int i, j, aux;
         for(i=0;i<A.length-1;i++)
              for(j=0;j<A.length-i-1;j++)
                   if(A[j+1]<A[j]){
                      aux=A[j+1];
                      A[j+1]=A[j];
                      A[j]=aux;
                   }
}

Ejemplo de ejecución:


Ya están ordenados, pero los dos bucles for seguirán ejecutándose hasta el final.
El tiempo de ejecución del algoritmo de la burbuja es del orden O(n2)
Es uno de los peores algoritmos de ordenación en cuanto a tiempo de ejecución, solamente es recomendable su uso para ordenar listas con un número pequeño de elementos.


35 comentarios:

  1. Estoy impresionado por la sencillez de tus cursillos. Muchas gracias.

    ResponderEliminar
  2. el procedimiento esta mal. Si en el segundo for, en la condicion se le resta a la longitud del vector "i" y a su vez se le resta 1 (A.length-i-1) en la primera vuelta causaria error, ya que si la longitud (tomando el ejemplo dado aqui) del vector es 6 y j inicia en 0, el segundo for llegaria hasta 6-0-1, osea hasta 5, y cuando entre al if y compare A[j+1] va a tirar un error de fuera de indice, porque estaria buscando la posicion 6, que no existe.
    Para que el metodo funcione apropiadamente, en el segundo for, la condicion debe ser j<A.length-2, si se realiza asi, el metodo funciona a la perfeccion y no tira errores.

    ResponderEliminar
    Respuestas
    1. Fíjate que la condición del segundo for es j<A.length-i-1. Con una longitud 6, en la primera vuelta este for empieza con j = 0 y se repite mientras j < 6-0-1 o sea mientras j < 5. Cuando j vale 5 este for no se realiza. Si lo ejecutas comprobarás que funciona correctamente.
      Un saludo y gracias por seguir el blog.

      Eliminar
    2. El comentario anterior tiene razón, lo ejecuté y tu código lanza una ArrayIndexOutOfBoundsException, el código no funciona del todo bien, pero muy buen aporte aún así

      Eliminar
    3. Lo acabo de ejecutar para comprobarlo y a mí me funciona sin errores. Sabes en qué línea da el error? Si puedes escribe el código completo con el main del programa que estás usando para poder descubrir donde está el error.
      Saludos

      Eliminar
  3. PLISS QUISIERA SABER COMO PUEDE RESOLVER ESTE EJERCICIO ME FALTA LA ULTIMA PARTE
    package MisAplicaciones;

    /** APP QUE PERMITA REGISTRAR LA EDAD
    * DE 5 PERSONAS Y MUESTRE UNA LISTADO
    * DE EDADES EN ORDEN DESCEBDENTE(EMPLEAR VECTOR)
    */
    import java.util.Vector;
    import java.util.Scanner;
    public class PruevaVector
    {
    public static void main(String[] xx)
    { //CREA OBJETO VECTOR
    Scanner sc= new Scanner(System .in);
    Vector vec1= new Vector();
    vec1.addElement(17);
    vec1.addElement(15);
    vec1.addElement(18);
    vec1.addElement(25);
    vec1.addElement(45);
    System.out.println("LAS EDADES INGRESADAS SON:");
    for(int x=0;x<vec1.size();x++)

    {
    System.out.println("la edad es: "+vec1.elementAt(x));

    }

    }

    }

    ResponderEliminar
  4. CONFIRMO QUE EL CODIGO FUNCIONA, LO USE EN MI APP JAVA Y FUNCIONO PERFECTO SIN ERRORES!

    ResponderEliminar
  5. Más facil e intuitivo:
    for (int i = 0; i < nums.length; i++) {
    for (int j = i + 1; j < nums.length; j++) {

    if (nums[i] > nums[j]) {
    aux = nums[i];
    nums[i] = nums[j];
    nums[j] = aux;

    }
    }
    }

    ResponderEliminar
    Respuestas
    1. Muchas gracias, me sirvió mucho

      Eliminar
    2. Hola, gracias por dejar el comentario. Este código que propones ordena pero no por el método de la burbuja. El método de la burbuja compara cada elemento con el que tiene a justo a continuación y si están desordenados los intercambia. El código que tu propones compara un elemento con todos los demás hasta el final y si es mayor lo intercambia.

      Eliminar
  6. hay les va otro código para lo mismo. también muestra las pasadas.

    public class Burbuja {


    public static void main(String[] args) {
    int [] arre={1, 23, 10, 9, 5};
    burbuja (arre);
    }

    public static void burbuja(int [] A){
    int j,k, aux;
    boolean f=false;
    String pasada="";
    for (k=0;k<A.length;k++) {
    for(j=1;j<A.length;j++) {
    if(A[j]<A[j-1]){
    aux=A[j];
    A[j]=A[j-1];
    A[j-1]=aux;
    System.out.println("A[j]="+A[j]+" A[j-1]="+A[j-1]+" AUX="+aux);
    for(int i=0;i<A.length;i++){
    pasada+=" "+Integer.toString(A[i]);
    }
    System.out.println("Arreglo A={" +pasada+" }");
    pasada="";

    }

    }
    }

    }
    }

    ResponderEliminar
    Respuestas
    1. falta el main,,, ese como va??? ayudame plis,, es el unico error que me marca que falta la estructura main,,,, tu programa no marco ningun error,,, solo eso pasame el main plis,,,

      Eliminar
  7. Viejito como ordeno la diagonal principal de una matriz gracias

    ResponderEliminar
  8. Hola, he probado tu algoritmo tal como esta y funciona de maravilla. tanto en orden ascendente como en descendente.


    saludos.

    ResponderEliminar
  9. a la verdad que el primero esta bien yo estudio ingenieria informatica pero este nivel esta muy por debajo del mio eso lo daba cuando estudiaba DPOO ahora en estructura de datos no se hace asi ya luego le cuelgo el codigo para que lo vean es mucho mejor

    ResponderEliminar
    Respuestas
    1. Gracias por el comentario. Este algoritmo y en general todos lo ejercicios que aparecen en este blog están dirigidos a aquellos que están empezando en el mundo de la programación. Como dices, se estudian en niveles básicos de programación estructurada y orientada a objetos y son la base para luego poder continuar con niveles más avanzados ;)

      Eliminar
  10. pues a mi me marca error,,, en donde esta el punto y coma,,,,,,

    ResponderEliminar
  11. y en la sentencia void int... tambien ahi marca error,,,,,

    ResponderEliminar
  12. a qui les dejo uno chequenlo

    import javax.swing.*;

    public class burbuja{

    static int arre[];
    int n;
    int aux ;
    public burbuja(){

    n=Integer.parseInt(JOptionPane.showInputDialog("dame el tamaño de el arreglo"));
    arre=new int [n] ;

    }

    public void captura (){
    int ele;

    for (int i=0; i arre[j+1] ){

    aux=arre[j];
    arre[j]=arre[j+1];
    arre[j+1]=aux;
    }
    }





    }

    }
    public void imprimir(){
    System.out.println ("el vector quedadela siguiente forma ");
    for(int k=0; k<n;k++){

    System.out.println ("elemento del vector "+k+" "+ arre[k]);

    }
    }
    public static void main (String[] args) {

    burbuja prueva=new burbuja();
    prueva.captura();

    prueva.ordenar ();
    prueva.imprimir();

    }
    }

    ResponderEliminar
  13. alguien me puede ayudar con el tema de arreglos ,métodos, propiedades get,lengt...
    gracias..

    ResponderEliminar
  14. burbujas para arraylist??? alquien sabe como
    aunq me encantaria un merge

    ResponderEliminar
    Respuestas
    1. En esta entrada tienes un ejemplo
      http://puntocomnoesunlenguaje.blogspot.com.es/2013/02/arraylist-de-objetos-en-java.html

      saludos

      Eliminar
  15. int aux=0.0;

    for(int j=0; j< datos.length-1;j++){
    for(int i=0; i < datos.length-1; i++){
    if(datos[i]>datos[i+1]){
    aux = datos[i+1];
    datos[i+1] = datos[i];
    datos[i]=aux;
    }
    }
    }

    ResponderEliminar
    Respuestas
    1. se me fue el 0.0 en la declaración de la variable aux, esque anteriormente la tenia declarada como doublé para un ejemplo diferente.. me funciona a la perfeccion este codigo

      Eliminar
  16. si alguno de estos elementos del array fuera nulo imaginando que los elementos del array son objetos de una clase determinada, se colocarian al final del array?

    ResponderEliminar
  17. jajajaja usa el meto array2[]=Array.sort(array[])

    ResponderEliminar
  18. En realidad este es el método burbuja, el que tu propones hace recorrer todo el vector la misma cantidad de veces que elementos tengas.. En un vector de 1 millon de elementos seria poco producente. Te dejo este código:

    public static void burbuja(int [] A){
    int i, j, aux;
    for(i=0;i<A.length-2;i++){
    j = i;
    while (i <= j) && (A[j+1]<A[j]) {
    aux=A[j+1];
    A[j+1]=A[j];
    A[j]=aux;
    j--;
    }
    }

    }

    ResponderEliminar
  19. con Vector, el vector que utilizo es indefinido, osea que no tiene un tamaño fijo, solo sirve para reordenar. suponiendo que tiene una longitud de n elementos, lo obtenemos con size();
    Vector numeros = new Vector<>();
    int aux, longitud = numeros.size();
    for (int i = 0; i < longitud - 1 ; i++) {
    for (int j = 0; j < longitud -i -1; j++) {
    if (numeros.get(j+1)>numeros.get(j)) {
    aux = numeros.get(j+1);
    numeros.set(j+1,numeros.get(j));
    numeros.set(j, aux);
    }
    }
    }

    ResponderEliminar
    Respuestas
    1. Buen aporte Alonso, Gracias por compartir.

      Eliminar
  20. alguien me puede ayudar con esto:


    public static void main(String[] args) {
    Scanner read = new Scanner (System.in);

    int vec1[] = new int [10];
    int vec2[] = new int [10];
    int arreglos[] = new int [10];
    int aux=0, m=0, n=0;
    for (int i=0; i<vec1.length-1; i++)
    {
    System.out.println("1... digite 10 elementos");
    vec1[i]= Integer. parseInt(read.next());
    for (m=0; m<vec1.length-i-1;m++)
    {
    if (vec1[m+1]<vec1[m])
    {
    aux= vec1[m+1]=vec1[m];
    vec1[m+1]= vec1[m];
    vec1[m]= aux;
    }
    }
    }
    for (int i=0; i<vec2.length-1; i++)
    {
    System.out.println("2... digite 10 elementos");
    vec2[i]= Integer. parseInt(read.next());
    for (n=0; n<vec2.length-i-1;n++)
    {
    if (vec2[n+1]<vec1[n])
    {
    aux= vec2[n+1]=vec2[n];
    vec2[n+1]= vec2[n];
    vec2[n]= aux;
    }
    }
    }
    esto es lo que tengo y debo ordenarlos de menor a mayor

    ResponderEliminar
    Respuestas
    1. asi dice el ejercicio:
      Se tienen dos arreglos unidimensionales. Uno de ellos con 10 elementos y, el otro con 10 elementos. Los elementos de los dos arreglos se encuentran ordenados en forma ascendente. Elabore un algoritmo que entre los dos vectores se forme uno nuevo de N + M elementos, el cual contendrá los elementos de los dos arreglos ordenados de menor a mayor.

      Eliminar