Ir a contenido


Foto

Ordenamiento de burbuja(Bubble Sort)


  • Please log in to reply
No replies to this topic

#1 Elias G.

Elias G.

    Senior Programmer

  • Tech Admin
  • PipPipPipPip
  • 539 Mensajes:
  • Gender:Male
  • Location:Republica Dominicana
  • Interests:Todo lo que tenga que ver con programacion puesto que estoy iniciando en esta.

Escrito 10 junio 2009 - 09:06

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.
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 '<'.

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 (n2). 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.

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;
 
	 do{
		fin = 0;
 
		for(int *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 de la burbuja 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.nextInt(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++){
			 System.out.print(X[i]);
		}
	}
}

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;
		}
	}
}

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#

int[] a = new int[]{1,4,6,8,9,0};
		System.Console.WriteLine("Programa en C#");
		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;
				  }
			  }
		   }
		   System.Console.WriteLine("Ahora los Imprimo");
		   for (int i = 0; i < a.Length; i++)
		   { System.Console.WriteLine("Valor {0}: {1}", i + 1, a[i]); }

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;





0 usuarios están leyendo este tema

0 miembros, 0 invitados, 0 usuarios anónimos

Tecnología y soporte por web hosting