Ordenación método de la burbuja

Este es tu lugar para hablar de programación, compartir, crear y desarrollar nuevos proyectos

Moderador: Moderadores

Ordenación método de la burbuja

Notapor neveldine » Sab Dic 12, 2015 8:30 pm

Hola,

Por qué en el caso medio tenemos 3(n^2-n)/4 comparaciones. Entiendo que viene de (n-1)/2 * (3/2)*n
Pero no entiendo por qué el (3/2) * n. ¿Es decir, por qué hay 3 intercambios por cada elemento desordenado?

Gracias anticipadas.

Un cordial saludo
neveldine
:-)
:-)
 
Mensajes: 1
Registrado: Sab Dic 12, 2015 8:27 pm

Re: Ordenación método de la burbuja

Notapor Yorkshire » Vie Dic 18, 2015 9:37 pm

Si no recuerdo mal, el número de comparaciones depende del número de elementos y es de (n^2-n)/2

Si se hacen 3 intercambios por comparación de cada elemento desordenado, tenemos que el caso peor será 3(n^2-n)/2, es decir, hay que hacer los 3 intercambios en cada elemento porque están todos desordenados.
El caso medio es el que haga la mitad de lo anterior: 3(n^2-n)/2/2 = 3(n^2-n)/4

Los tres intercambios son los necesarios para intercambiar los valores usando una variable auxiliar:
aux = v(i)
v(i) = v(i+1)
v(i+1) = aux

Saludos
Linux registered user #346840
Avatar de Usuario
Yorkshire
Gran Wadalbertita
Gran Wadalbertita
 
Mensajes: 4488
Registrado: Mié Ene 26, 2005 5:05 pm
Ubicación: -<|:-P[G]

Re: Ordenación método de la burbuja

Notapor Newhack » Dom Dic 20, 2015 8:30 pm

Uff, gracias por responder, porque a mi, aunque recuerde algo, se me da fatal expresarlo en forma matemática.
Me hago lios intentando traducirlo (de y hacia) esta manera.
Mi estilo es mas "rollero y plano". :lol:
Avatar de Usuario
Newhack
<|:-D
<|:-D
 
Mensajes: 1871
Registrado: Jue Dic 20, 2007 7:36 pm


Volver a Programación

¿Quién está conectado?

Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 2 invitados