Metodo burbuja

Solo disponible en BuenasTareas
  • Páginas : 2 (470 palabras )
  • Descarga(s) : 0
  • Publicado : 7 de enero de 2011
Leer documento completo
Vista previa del texto
Concepto
* Burbuja: Consiste en comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que estén todos ordenados. Con el array anterior, {40,21,4,9,10,35}:
* primera pasada:{21,40,4,9,10,35} <-- Se cambia el 21 por el 40.
{21,4,40,9,10,35} <-- Se cambia el 40 por el 4.
{21,4,9,40,10,35} <-- Se cambia el 9 por el 40.
{21,4,9,10,40,35} <-- Se cambia el 40por el 10.
{21,4,9,10,35,40} <-- Se cambia el 35 por el 40.
P

* Segunda pasada:
{4,21,9,10,35,40} <-- Se cambia el 21 por el 4.
{4,9,21,10,35,40} <-- Se cambia el 9 por el 21.{4,9,10,21,35,40} <-- Se cambia el 21 por el 10.
* Ya están ordenados, pero para comprobarlo habría que acabar esta segunda comprobación y hacer una tercera.

Pasos a seguir
* Los pasos aseguir utilizando este método son los siguientes, imaginando que deseamos realizar una ordenación creciente:
* 1.- Se compara el primer elemento con el segundo. Si están desordenados se intercambian.Luego se mira el segundo con el tercero, intercambiando también si es necesario. Así hasta que llegamos al último elemento. De esta forma tenemos en la última posición de nuestra tabla el elemento másgrande.

* 2.- Repetimos lo mismo que antes pero ahora con todos los elemento, menos el último, que ya está ordenado.
* 3.- Repetimos el primer paso pero esta vez con otro elemento menos, yaque este también está ordenado. Este método finaliza en el momento en el que se han realizado tantas pasadas como objetos - 1 hay en la lista. Su hace menos 1 pasadas porque el primero de losobjetos, como es lógico si pensamos que los demás ya están ordenados, ya está ordenado.

Ejemplo
* Si el array tiene N elementos, para estar seguro de que el array está ordenado, hay que hacer N-1pasadas, por lo que habría que hacer (N-1)*(N-i-1) comparaciones, para cada i desde 1 hasta N-1. El número de comparaciones es, por tanto, N (N-1)/2, lo que nos deja un tiempo de ejecución, al igual que...
tracking img