Bubble Sort (Intercambio directo)

Inicio ¿Sidebar? RSS @MisAlgoritmos at Twitter

Bubble Sort (Intercambio directo)

El método de intercambio directo, conocido coloquialmente con el nombre de la burbuja, es el más utilizado por los estudiantes principiantes de computación, por su fácil comprensión y programación. Pero es preciso señalar que es probablemente el método más ineficiente (Para eficientes tenemos el Ordenamiento Rápido).

El método de intercambio directo puede trabajar de dos maneras diferentes.

  1. llevando los elementos más pequeños hacia la parte izquierda del arreglo.
  2. llevando los elementos más grandes hacia la parte derecha del mismo.

La idea básica de este algoritmo consiste en comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que todos se encuentren ordenados. Se realizan N-1 pasadas, transportando en cada una de las mismas el menor o mayor elemento (Según sea el caso) su posición ideal. Al final de las N-1 pasadas los elementos del arreglo estarán ordenados.

la siguiente, es una implementación en Pseudocódigo, donde A es un arreglo de N elementos

BURBUJA(A,N)
{I, J y AUX son variables de tipo entero}
1. Repetir con I desde 2 hasta N
       1.1 Repetir con J desde N hasta I
              1.1.1 Si A[J-1] > A[J] entonces
                     Hacer AUX ? A[J-1]
                     A[J-1] ? A[J]
                     A[J] ? AUX
              1.1.2 {Fin del condicional del paso 1.1.1}
       1.2 {Fin del ciclo del paso 1.1}
2. {Fin del ciclo del paso 1}
Implementación en PHP.
  1. function burbuja($A){
  2.       $N = count($A)-1;
  3.       for($i=1;$i < = $N;$i++)
  4.          for($j=$N;$j>=$i;$j--)
  5.             if($A[$j-1]>$A[$j]){
  6.                   $aux = $A[$j-1];
  7.                   $A[$j-1] = $A[$j];
  8.                   $A[$j] = $aux;
  9.                }
  10.       return $A;
  11.    }
There are 8 comments. for this entry.