Ordenamiento de burbuja
| ||||||
Algoritmo de ordenamiento. 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.
Sumario
Descripción
El procedimiento de la burbuja es el siguiente: § Ir comparando desde la casilla 0 número 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.
Dado un vector a1, a2, a3, ... an
1) Comparar a1 con a2 e intercambiarlos si a1>a2 (o a12)
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-++){ 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 siguiente ejemplo muestra el proceso de forma gráfica:
Análisis del Costo Computacional
Al algoritmo de la burbuja, para ordenar un vector de n términos, tiene que realizar siempre el mismo número de comparaciones:
Esto es, el número de comparaciones c(n) no depende del orden de los términos, si no del número de términos.
Por lo tanto la cota ajustada asintótica del número de comparaciones pertenece al orden de n cuadrado.
El numero de intercambios i(n), que hay que realizar depende del orden de los términos y podemos diferencia, el caso mejor, si el vector esta previamente ordenado, y el caso peor, si el vector esta ordenado en orden inverso.
Por lo que no se puede determinar una cota ajustada asintótica del número de intercambios, dado que este dependerá del orden del vector en cuestión.
Rendimiento en el caso desfavorable
Si pasamos al algoritmo un vector ordenado en orden inverso realizara un número de comparaciones:
Como ya hemos dicho anteriormente, y tendrá que realizar un número igual de intercambios entre los términos del vector, dado que en cada comparación los términos estarán desordenados, y se realizará el intercambio.
Por lo tanto en el caso más desfavorable tanto el número de comparaciones como el de intercambios coinciden:
El número de comparaciones o de intercambios en el caso más desfavorable pertenece al orden de n cuadrado.
Rendimiento en casos óptimos
En el caso óptimo, el más favorable, es la ordenación que un vector ya ordenado, en este caso el número de comparaciones será el mismo que en cualquier otro caso:
La cota inferior asintótica del número de comparaciones pertenece al orden de n cuadrado, como en los demás casos, pero en todas las comparaciones el orden es el correcto y por tanto no se realiza ningún intercambio:
Por lo tanto el coste de intercambios no depende de n, y es constante:
El ordenamiento de burbuja tiene una complejidad Ω(n²) igual que ordenamiento por selecció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 está forzado a pasar por dichas comparaciones, lo que hace que su complejidad sea cuadrática en el mejor de los casos. Esto lo cataloga como el algoritmo más ineficiente que existe, aunque para muchos programadores sea el más sencillo de implementar.
Aplicación
A pesar de que el ordenamiento de burbuja es uno de los algoritmos más sencillos de implementar, su orden O(n2) 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(n2), 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 de ordenamiento para estudiantes de ciencias de la computación. A pesar de esto, algunos investigadores como Owen Astrachan han criticado su popularidad en la enseñanza de ciencias de la computación, llegando a recomendar su eliminación de los planes de estudio. Sumado a esto, Jargon File, un libro ampliamente citado en la cultura hacker, lo denomina "el mal algoritmo genérico", y Donald Knuth, uno de los mayores expertos en ciencias de la computación, afirma que el ordenamiento de burbuja "no parece tener nada para recomendar su uso, a excepción de un nombre pegajoso y el hecho de que conlleva a problemas teóricos interesantes". 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 funciona considerablemente mejor incluso con listas aleatorias. Por esta razón, muchos libros de algoritmos modernos evitan usar el ordenamiento de burbuja, reemplazándolo por 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 de ordenamiento de cadenas en Java hechos por Astrachan 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.
Implementación
A continuación se muestra el Ordenamiento de burbuja en algunos de los lenguajes de programación más usados:
- C
//Ordenamiento por método de la Burbuja void ordenamientoBurbuja(int v[], int util_v) {
int temp, i, j;
for (i = 0; i < util_v -1 ; i++) {
for (j = i + 1; j < util_v ; j++) {
if (v[i] > v[j]) {
temp = v[i];
v[i] = v[j];
v[j] = temp;
}
}
} }
- C++
template<typename _Ty> void bubble_sort(vector<_Ty> & v){
for (size_t i = 0; i < v.size() - 1; ++i){
for (size_t j = i + 1; j < v.size(); ++j){
if (v[i] > v[j])
swap(v[i], v[j]);
}
}
}
- C#
Public int[] OrdenarBurbuja(int[]x)
{
int t= x.Length, temp;
for(int i=1 ; i< t ; i++)
for(int j = t-1 ; j >= i; j--)
{
if(x[j] < x[j-1])
{
temp= x[j];
x[j]= x[j-1];
x[j-1]= temp;
}
}
return x;
}
- Java
//Ordenamiento por Burbuja
// by ramses2999
publicstatic int[] OrdenarBurbuja(int[] n){
int temp;
int t = n.length;
for (int i = 1; i < t; i++) {
for (int k = t- 1; k >= i; k--) {
if(n[k] < n[k-1]){
temp = n[k];
n[k] = n[k-1];
n[k-1]= temp;
}//fin if
}// fin 2 for
}//fin 1 for
return n;
}//fin
- Perl
sub bubblesort {
# Ordena la lista pasada como argumento por valor
for my $i ( 0 .. @_-2 ) {
for my $j ( $i+1 .. @_-1 ) {
@_[ $i, $j ] = @_[ $j, $i ] if $_[$i] > $_[$j];
}}
}
- Visual Basic
Private Sub OrdenarBurbuja(ByRef VectorOriginal() As Integer)
Dim Temp, Longitud As Integer
Longitud = UBound(VectorOriginal) - 2
For b = 0 To Longitud
For a = 0 To Longitud
If VectorOriginal(a) > VectorOriginal(a + 1) Then
Temp = VectorOriginal(a + 1)
VectorOriginal(a + 1) = VectorOriginal(a)
VectorOriginal(a) = Temp
EndIf
Next
Next
End Sub
- PHP
<?php
//Ordenamiento por burbuja $numeros = array(9, 4, -1, 7, 8, 11, 6, 12, 10, 5);
$n = count($numeros);
for ($i = 1; $i<$n; $i++) {
for ($j = $n-1; $j >= $i; $j--) {
echo "i: $i, j: $j\n";
echo "Comparando " . $numeros[$j-1] . " y " . $numeros[$j] . "\n";
if ($numeros[$j-1] > $numeros[$j]) {
$aux = $numeros[$j];
$numeros[$j] = $numeros[$j-1];
$numeros[$j-1] = $aux;
}
}
}
print_r($numeros);
- Pascal
Procedure Burbuja(var lista:vector;size:integer); var i,j:integer;
begin
for i:=1 to size-1 do
for j:=1 to size-i do
begin
if lista[j]>lista[j+1] then
begin
aux:=lista[j];
lista[j]:=lista[j+1];
lista[j+1]:=aux
end;
end;
end;
Ver además
- Algoritmo de ordenamiento
- Algoritmo de búsqueda
- Algoritmo de Kruskal
- Algoritmo de Euclides
- Algoritmo de Prim
- Algoritmo de Boruvka
- Algoritmo de Gutmann
- Algoritmo criptográfico
- Algoritmo
- Algoritmo de Ordenamiento Shell
- Algoritmo genético
- Algoritmo de ordenamiento por selección
- Algoritmo de árboles de decisión de Microsoft
- Algoritmo de Búsqueda Heurística A*
- Algoritmo asimétrico
Fuentes
- Aprenda C/C++.
- Estructuras de datos.
- Wikipedia.
