Ordenación: método de la burbuja

[mvk]

Hi! Estoy programando en C, pero pongo la duda en está sección, ya que pienso que es más generica que de un lenguaje en particular.

Me encuentro con que en un análisis de las comparaciones que hay que hacer se tiene:

caso más desfavorable: (n-1)+(n-2)+...+2+1 = (n-1)(n/2)

El sacar (n-1)+(n-2)+...+2+1 lo entiendo pero, ¿Como se llega a la expresión (n-1)(n/2) ?

Supongo que es una sucesión pero no llego a esa expresión  

Agradezco toda ayuda que me podáis brindar.

[[Case]]

Es facil de ver una vez teniendo la idea de donde surgio.

Usare un ejemplo, desde el 1 al 100.
En este caso n = 100.

Ahora si te das cuenta, 1 + 100 = 101, 2 + 99 = 101, 3 + 98 = 101. Asi hasta 50 + 51 = 101.

n/2 es el numero de veces que sumamos 101, que es 50 en este caso.
Y n + 1 es por que la suma de i + n - (i - 1) = n + 1 con i desde 0 hasta n
Que es 101.

Esto nos da la formula (n + 1)(n/2) = n + (n-1) + .. + 2 + 1

Por ultimo y el paso simple. Dado que tu lo que quieres es demostrar la suma desde 0 hasta n - 1, solamente nos falta restar n a la formula (n +1)(n/2).

(n +1)(n/2) - n = (n^2 + n)/2 - 2n/2 = (n^2-n)/2 = (n-1)(n/2)

Y de ahi sale, la demostracion formal debe de salir por inducción sobre n.

[mvk]

Hola Case, me he quedado así La verdad es que esto demuestra que estoy muy pez todavía. Lo de n/2 partiendo de 100+1, ok, pero eso de i + n - (i - 1) ya me he perdido, no entiendo que relación tiene con lo demás

Gracias por la paciencia

[[Case]]

Si perdo, ahi no lo explique bien.
Mira

La serie en si es:

Desde el i = 1 hasta i = n  ∑i

Que es: 1 + 2 + 3 + ... + n.

Entonces lo que hago es cambiar el orden, en lugar de; 1 +2 + ... + n lo pongo así:

[1 + n] + [2 + n - 1] + [3 + n - 2] + ... + [(n/2) + (n/2 + 1)]

Si te das cuenta cada numero entre corchetes siempre da n + 1, en el caso del ejemplo siempre da 101 = 100 + 1. Y el numero de veces que sumaste n + 1 fue n/2.

Por lo tanto queda (n + 1)(n/2).

Lo demas es seguir la demostracion que te habia puesto.

[mvk]

La serie pones que es sumatorio de i, pero yo hasta donde entiendo, tengo:
(n-1)+(n-2) + (n-3) +... + 2 + 1
Con lo que aquí ya me pierdo.

Y luego, la serie 1 + 2 + ... + n, la conviertes en sumatorios de (n+1), pero sumar (n+1) + (n+1) + (n + 1) +... no es lo mismo que ir 1 + 2 + ... + n.

Puff que lio, voy a darte mucha berra, pero es que tío, no me entra en la almendra.

[mvk]

Soy un boludo, por fin lo entendí!!!!!!

Gracias otra vez, Case.

xau