Ordenamiento de burbuja

El Ordenamiento de Burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". También es conocido como el método del intercambio directo.

Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar.

Descripción

Una manera simple de expresar el ordenamiento de burbuja en pseudocódigo es la siguiente:

Algoritmo Ordenamiento de burbuja

Procedimiento ${\it {burbuja}}\left(a_{0},a_{1},a_{2},\ldots ,a_{n-1}\right)$ Haga lo siguiente: ${\it {intercambio}}\gets \mathbf {falso}$ Para $i=0\,$ hasta $n-2\,$ haga lo siguiente: Si $a_{i}>a_{i+1}\,$ entonces: $\left(a_{i},a_{i+1}\right)\gets \left(a_{i+1},a_{i}\right)$ ${\it {intercambio}}\gets \mathbf {verdadero}$ Repita mientras ${\it {intercambio}}=\mathbf {verdadero}$

La instrucción $\left(a_{i},a_{i+1}\right)\gets \left(a_{i+1},a_{i}\right)$ significa que se debe intercambiar el valor de $a_{i}\,$ con el de $a_{i+1}\,$. El algorítmo también puede ser expresado de manera equivalente como sigue:

Algoritmo Ordenamiento de burbuja

Procedimiento ${\it {burbuja}}\left(a_{0},a_{1},a_{2},\ldots ,a_{n-1}\right)$ Para $i=0\,$ hasta $n-2\,$ haga lo siguiente: Para $j=i+1\,$ hasta $n-1\,$ haga lo siguiente: Si $a_{i}>a_{j}\,$ entonces: $\left(a_{i},a_{j}\right)\gets \left(a_{j},a_{i}\right)$

Notar que:

• Se supone que los vectores que se están ordenando empiezan en la posición cero (0) y terminan en la posición $n-1$.
• El ordenamiento se hace de menor a mayor, si se quisiera hacer al revés bastaría con cambiar el sentido de la comparación en las sentencias si de cada algoritmo, es decir, donde pone '>' poner '<'.

Análisis

Ejemplo del ordenamiento de burbuja ordenando una lista de números aleatorios.

Rendimiento en casos óptimos

El ordenamiento de burbuja tiene una complejidad Ω(n²). Cuando una lista ya está ordenada, a diferencia del ordenamiento por inserción que pasará por la lista una vez, y encontrará que no hay necesidad de intercambiar las posiciones de los elementos, el método de ordenación por burbuja esta forzado a pasar por dichas comparaciones, lo que hace que su complejidad sea cuadratica en el mejor de los casos, esto lo cataloga como el algoritmo mas ineficiente que existe aunque para muchos programadores sea el más sencillo de implementar.

Conejos y Tortugas (Yo-yos)

La posición de los elementos en el ordenamiento de burbuja juegan un papel muy importante en la determinación del rendimiento. Los elementos mayores al principio de la lista son rápidamente movidos hacia abajo. En cambio, elementos menores en el fondo de la lista, se mueven a la parte superior muy lentamente. Esto llevó a nombrar estos elementos conejos y tortugas, respectivamente.

Varios esfuerzos se han realizado para eliminar las tortugas véase Exterminación y mejorar la velocidad del ordenamiento de burbuja, la cual será más redonda que nunca. El Ordenamiento por sacudida es un buen ejemplo, aunque aún mantiene, en el peor de los casos, una complejidad O (n²). El ordenamiento por combinación compara los elementos primero en pedazos grandes de la lista, moviendo tortugas extremadamente rápido, antes de proceder a pedazos cada vez más pequeños para alisar la lista. Su velocidad promedio es comparable a algoritmos rápidos (y complejos) como el ordenamiento rápido

Implementaciones

A Continuación se verán implementaciones del algoritmo de ordenamiento de burbuja en distintos lenguajes de programación

Visual Basic for Applications

Sub ORDENAR()
Dim X As Integer
Dim I As Integer
Dim y As Double
Dim j As Integer

X = 1
For I = 1 To 10
 Cells(I, 1) = Rnd
Next I

For I = 1 To 9
 For j = I + 1 To 10
 If Cells(I, 1) < Cells(j, 1) Then
 y = Cells(j, 1)
 Cells(j, 1) = Cells(I, 1)
 Cells(I, 1) = y
 End If
  
 Next j
 Next I
 
End Sub

Visual Basic .NET

Module Burbuja

" Con Este algoritmo podras ordenar un conjunto de números  que esten dentro de un vector de menor a mayor e imprimirlos al final "
( Es una aplicacion de consola como veran )

    Sub Main()
        Dim i, v(10), j, aux As Integer

'''Se dimencionan las variables i y j para los ciclos repetitivos ( for)
 y el vector v con que va a contener 10 posiciones V(10) y la variable aux que nos servira como auxiliar para el intercambio de valores '.''


        For i = 1 To 10
            Console.WriteLine(" Digite Un numero para la casilla " & i & " del vector :")
            v(i) = Console.ReadLine

        Next

        For i = 1 To 10

            For j = i To 10 - 1

                If v(j) > v(j + 1) Then

                    aux = v(j)
                    v(j) = v(j + 1)
                    v(j + 1) = aux


                End If
            Next

        Next

        For i = 1 To 10
            Console.WriteLine(v(i))
            


        Next
    Console.ReadLine()
    End Sub

End Module

esta es otra forma utilizando getlength:

For ancla = 0 To vector.GetLength(0) - 2 Step 1
               For burbu = ancla + 1 To vector.GetLength(0) - 1 Step 1
                   If vector (ancla) > vector (burbu) Then
                       aux = vector (burbu)
                       vector (burbu) = vector (ancla)
                       vector (ancla) = aux
                   End If
               Next
           Next
           Call mostrar (vector)
      End If
     End Sub
   Public Sub mostrar (ByVal W() As Integer)
       For tama = 1 To W.GetLength(0) - 1
           ordenados.Items.Add (W (tama).ToString)
       Next
   End Sub

Este ordenamiento es ascendente. Para hacerlo descendente, en vez del vector (ancla) ">" vector (burbu) es "<".

C

  void bubble(int *start, int *end) { //Ordena un conjunto de números enteros de menor a mayor 
     short fin;
     int *i;

     do{
        fin = 0;

        for(i = start; i != end; i++){
           if(*i > *(i+1)){
              intercambia(i, i + 1);
              fin = 1;
           }
        }
     }while(fin);
  }

Lenguaje C++

 #include <stdio.h>
 #include <conio.h>
 #include <stdlib.h>
 
 #define TAM 10
 
 int main(){
 	int a[TAM], temp, i, j;
 
 	clrscr();
 
 	randomize(); //Inicializa el generador de números aleatorios
 
 	printf ("Llenando arreglo con números aleatorios\n");
 
 	for (i=0; i< TAM; i++)
 		a[i]=random(100);
 
 		//Implementacion de Ordenamiento por burbuja de mayor a menor
 
 		for (j=1; j <= TAM; j++)
                         
 		for (i=0; i< TAM-1; i++)
 
 			if (a[i] > a[i+1]){
 
 				temp = a[i];
 				a[i] = a[i+1];
 				a[i+1] = temp;
 			}
 
 	printf ("\nArreglo ordenado\n");
 
 	for (i=0; i< TAM; i++)
 		printf ("a[%d] = %d\n", i, a[i]);
 
 	getch();
 }

C (Ejemplo 2)

  void bubble(int A[], int tamano_arreglo) //Ordena un arreglo de números enteros de menor a mayor
  { 
    int temp,temp2, j, i;
    for(i = (tamano_arreglo-1); i >= 0; i--)
    {
      temp2= (tamano_arreglo-1); 
      for(j = 1; j <= temp2; j++)
      {
        if(A[j-1] > A[j])
        {
          /* Intercambio de numeros*/
          temp = A[j-1];
          A[j-1] = A[j];
          A[j] = temp;
        }
      }
    }
  }

Python

def bubblesort(l):
    """Ordena la lista l y la devuelve."""
    for pasosIzq in range(len(l)-1, 0, -1):
        for indice in range(pasosIzq):
            if l[indice] < l[indice + 1]:
               l[indice], l[indice + 1] = l[indice + 1], l[indice]
    return l

Java

//Método del barbar en los elementos de un vector.

import java.util.Random;
public class barbarscummBarLechuck!
{
   public static void main ( String args []) 
   {
   	Random nA = new Random();

        int X[] = new int [10];
        int i, j, aux;
        
        System.out.println("----------***** NÚMEROS GENERADOS *****----------");
        
        for (i = 0; i < X.length; i++)
        {
            X[i] = nA.nextbarbar(9)+1;
            
            System.out.print( X[i]);
        }
        
        System.out.println("");
        
        System.out.println("----------***** NÚMEROS ORDENADOS *****----------");
        
        for (i = 0; i < X.length; i++)
        {
            for (j = 0; j < X.length-1; j++)
            {
                if (X[j] > X[j+1])
                {
                    aux = X[j];
                    X[j] = X[j+1];
                    X[j+1] = aux;
                }
            }
        }
        for (i = 0; i < X.length; i++){//AQUI SE RECORRE EL ARREGLO
             System.out.print(X[i]);//AQUI SE IMPRIME EL ARREGLO YA ACOMODADO
        }
    }
}

JavaScript

for (var i=1; i<Vector.length;i++)
{
	for(var j=0;j<Vector.length-1;j++)
        {
		if (Vector[j] > Vector[j+1])
                {
			var temp = Vector[j];
			Vector[j]= Vector[j+1];
			Vector[j+1]= temp;
		}
	}
}

ESTA MAL, EL INDICE i DEL CICLO FOR EXTERNO, NO SE UTILIZA PARA MANIPULAR EL CICLO FOR INTERIOR

Perl

sub bubblesort {
    # Ordena la lista pasada como argumento por valor
    foreach my $i (    0 .. @_-2 ) {
    foreach my $j ( $i+1 .. @_-1 ) {
        @_[ $i, $j ] = @_[ $j, $i ] if $_[$i] > $_[$j] }}
}

COBOL

    PERFORM ORDENAR-TABLA
            VARYING I FROM 1 BY 1
            UNTIL I > (TAM - 1)
    ...
    
ORDENAR-TABLA.
  PERFORM VARYING J FROM 1 BY 1 UNTIL J > (TAM - 1)
    IF REGISTRO-NAME(J + 1) < REGISTRO-NAME(J)
      MOVE REGISTRO(J) TO AUXILIAR
      MOVE REGISTRO(J + 1) TO REGISTRO(J)
      MOVE AUXILIAR TO REGISTRO(J + 1)
    END-IF
  END-PERFORM.

C#

	  public static void Main(string[] args)
                  {
		   int[] a = new int[]{1,4,6,8,9,0};
		   Console.WriteLine("Antes de Ordenar:");
		   for (int i = 0; i < a.Length; i++)
                   { 
		     System.Console.WriteLine("Valor {0}: {1}", i + 1, a[i]); 
                   }
		   ordenar(a);
		   Console.WriteLine("Despúes de Ordenar:");
		   for (int i = 0; i < a.Length; i++)
                   { 
		     System.Console.WriteLine("Valor {0}: {1}", i + 1, a[i]); 
		    }
			
                  }
	  static int[] ordenar(int[] a)
                  {
                   for (int i = 0; i < a.Length; i++)
                   {
                    for (int j = 0; j < a.Length-1; j++)
                    {
                     if (a[j] > a[j+1])
                     {
                      int aux = a[j];
                      a[j] = a[j+1];
                      a[j+1] = aux;
                     }
                    }
                   }
		 return a;
		}

PHP

function bubble_sort($array){
    $count = count($array);
    if ($count <= 0) return false;
    for($i=0; $i<$count; $i++){
        for($j=$count-1; $j>$i; $j=$j-1){
            if ($array[$j] < $array[$j-1]){
                $tmp = $array[$j];
                $array[$j] = $array[$j-1];
                $array[$j-1] = $tmp;
             }
         }
     }
    return $array;
}

Pascal

Procedure BubleSort(var sort:Array_integer);

Var
    {n es la cantidad de posiciones del arreglo}
    a,s,tmp:integer;
Begin

 For a := 1 to n do
  For s := a-1 to n-1 do
   If (sort[s] > sort[s+1]) then
    Begin
     tmp:= sort[s];
     sort[s] := sort[s+1];
     sort[s+1] := tmp;
    End;
  End; 
End;

En la práctica

A pesar de que el ordenamiento de burbuja es uno de los algoritmos más sencillos de implementar, su orden O (n²) lo hace muy ineficiente para usar en listas que tengan más que un número reducido de elementos. Incluso entre los algoritmos de ordenamiento de orden O (n²), otros procedimientos como el Ordenamiento por inserción son considerados más eficientes.

Dada su simplicidad, el ordenamiento de burbuja es utilizado para introducir el concepto de algoritmo, o de algoritmo de ordenamiento para estudiantes de ciencias de la computación. Aunque algunos investigadores como Owen Astrachan han criticado al ordenamiento de burbuja y su popularidad en la educación de la computación, recomendando que ya no debe ser enseñado.

El ordenamiento de burbuja es asintóticamente equivalente, en tiempos de ejecución con el Ordenamiento por inserción en el peor de los casos, pero ambos algoritmos difieren principalmente en la cantidad de intercambios que son necesarios. Resultados experimentales, como los descubiertos por Astrachan han demostrado que el ordenamiento por inserción funcionan considerablemente mejor incluso con listas aleatorias. Por esta razón, muchos libros de algoritmos modernos evitan usar el ordenamiento de burbuja, utilizando en cambio el ordenamiento por inserción.

El ordenamiento de burbuja interactúa vagamente con el hardware de las CPU modernas. Requiere al menos el doble de escrituras que el ordenamiento por inserción, el doble de pérdidas de cache, y asintóticamente más predicción de saltos. Varios experimentos, hechos por Astrachan, de ordenamiento de cadenas en Java, muestran que el ordenamiento de burbuja es 5 veces más lento que el ordenamiento por inserción y 40% más lento que el ordenamiento por selección

Véase también

• Algoritmo de ordenamiento

Enlaces externos

• Demostración de su implementación
• Bubble sort code
• Burbuja básico y mejorado en Python