[pierrot]

Dado el siguiente algoritmo que recibe como parámetro un arreglo a de tamaño n de enteros distintos, interesa calcular el costo en el mejor (\( T_B(n) \)) y peor (\( T_W(n) \)) caso, considerando simultáneamente las dos siguientes operaciones elementales:

-La comparación entre elementos de a con costo c1.
-La asignación en el arrego a con costo c2.

Se pide:

1) Indique en forma genérica las entradas de tamaño n que maximizan el costo y luego calcule el costo del peor caso.

2) Indique en forma genérica las entradas de tamaño n que minimizan el costo y luego calcule el costo del mejor caso.


for(int=1; i<n-2; i=i+4){
   if (a[i] > a[i+2])
      swap(a, i-1, i+1);
}

for(int=0; i<n; i=i++){
   for(j=i+1; j<=n; i++)
      if (a[i] > a[j])
         swap(a, i, j);
}

void swap (int* a; int i; int j){
   int aux=a[i];
   a[i]=a[j];
   a[j]=aux;
}


Para el apartado 2) es claro que el mejor caso se da cuando el arreglo está ordenado. Pero para el apartado 1), ¿cuándo se da el peor caso? ¿Será cuando el arreglo está ordenado en sentido inverso? No lo veo tan claro.

[Phicar]

Hola pabloN, sí el peor caso es el que estén al revés..nota que se necesitan \( n^2-\displaystyle\binom{n}{2} \) o \( O(n^2) \)



Ahora, para tu problema, pues usa el arreglo para hacer la inversa...digamos el arreglo más complicado(longitud 10) para el bubble sort sería 10 9 8 7 6 5 4 3 2 1 pero el for de antes lo volverá así

8 9 10 7 4 5 6 3 2 1 luego si lo metes de ésta forma, te quedará ordenado al revés. Así que al algoritmo le tomará \( 10^2-\displaystyle\binom{10}{2}+2 \) swaps.

para curarme en dudas hice un bruteforce..

import java.util.*;
public class pablo{
public static int max = -1;
public static void main(String args[]){
gen(10,new Vector<Integer>(),10);
System.out.println(max);
}
public static int buble(Vector<Integer> aa){
int a[] = new int[aa.size()];
for(int n = 0;n<aa.size();n++)
a[n]=aa.get(n);
int res = 0;
for(int i=1; i<aa.size()-2; i=i+4){
if (a > a[i+2]){
res++;
a[i-1]^=a[i+1];
a[i+1]^=a[i-1];
a[i-1]^=a[i+1];
}
}
for(int i=0; i<aa.size();i++){
for(int j=i+1; j<aa.size(); j++)
if (a > a[j]){
res++;
a^=a[j];
a[j]^=a;
a^=a[j];
}
}
return res;
}
public static void gen(int a,Vector<Integer> b,int c){
if(a==0){
int bu = buble(b);
if(bu>max){
max = bu;
System.out.println(b+" "+max);
}
return;
}
for(int n = 1;n<=c;n++){
Vector<Integer> tmp = (Vector<Integer>)b.clone();
if(!tmp.contains(n)){
tmp.add(n);
gen(a-1,tmp,c);
}
}
}
}

Saludos

[pierrot]

¡Muchas gracias, Phicar!

Ésto me ha servido mucho:

Ahora, para tu problema, pues usa el arreglo para hacer la inversa...digamos el arreglo más complicado(longitud 10) para el bubble sort sería 10 9 8 7 6 5 4 3 2 1 pero el for de antes lo volverá así

8 9 10 7 4 5 6 3 2 1 luego si lo metes de ésta forma, te quedará ordenado al revés.

No lo había notado  .