Ayuda, ¿Cómo puedo obtener el número de intercambios y comparaciones en un algoritmo de ordenamiento?
Hola Saludos!!!
Me gustaría saber cómo puedo hacerle para contar el número de intercambios y comparaciones que se realizan para ordenar un arreglo. Tengo una clase llamada Ordenamientos en donde tengo 5 métodos estáticos que realizan cada uno un diferente algoritmo de ordenamiento.
Pero el problema es que no sé como modificar cada método para obtener el numero de intercambio y comparaciones. Me gustaría que alguien me pueda dar algún tipo de orientación al respecto.
Muchas gracias…
PD: Adjunto el codigo con los algoritmos
| Adjunto | Tamaño |
|---|---|
| Codigo.txt | 2.36 KB |
- ChEmO1900's blog
- Inicie sesión o regístrese para enviar comentarios
Comentarios
Comparable/Comparator
Si tus ordenamientos manejan listas de puros objetos que implementen Comparable o Comparator, y tú hiciste esas implementaciones, puedes meter en los métodos
compareque se incremente un contador; ese contador se incrementa cada vez que se invoque el método. Si el contador es de instancia, te dirá cuántas veces se comparó cada objeto; si lo haces estático, te dirá cuántas veces se invocó el método en total (y tendrías que reiniciarlo antes de volver a ordenar con otro algoritmo).me hace recordar a mi querido
me hace recordar a mi querido profesor Hector Soza..puedes utilizar java para programar directamente o bien utilizar lapiz y papel hacer los calculos
y supongo que si tu hiciste esas implementaciones tambien puedes sacarlo manualmente te voy a explicar , por ejemplo
el ordenamiento burbuja o tambien conocido como intercambio
veamos los pasitos
vas a recorrer la lista comparando en forma secuencial ( uno a uno) el elemento i con el elemento i +1 entonces si la lista esta desordenada ( si lo que piensas ) se intercambian las posiciones y se continua hasta recorrer la lista.
asi que te va quedar una nueva lista por recorrer , esa nueva lista a de tener el largo n-1 , si bueno espero que me entiendas ya es n-1 porque el mayor queda en la posicion que le corresponde ( se esta ordenado viejo)
asi que el proceso continua con una nueva lista asi que aparece la recursividad, por supuesto que esto continua hasta que ya no exista ningún cambio
en el recorrido de la lista ( de toda la lista ya). asi que si llegas a este punto chan chan la lista esta ordenada o bien chan chan hasta que el numero de elementos sea uno.
10 15 25 3 4
si haces lo que te dije
10 15 3 4 25 (3,4,25)
10 3 4 15 25 (3,4,15)
3 4 10 15 25 (3,4,10)
ahora el numero maximo de comparaciones es n(n-1)/2 (claro en caso que la lista invertida) , y si estuviera ordena el minimo n-1 comparaciones
bueno entonces en promedio se suma cuando no este invertida y cuando este ordenada y se divido por 2
el numero promedio te queda
(n(n-1)/2+(n-1))/2
no soy profesor espero que te quede claro (me gustaría haberlo sido en fin)
el otro que me costo.. jaja no es chiste ..en fin es el quick sort algo importante que ves en lo que hiciste
int pivote = arreglo[( izq + der ) / 2];
el famoso pivote este muchachin distribuye los datos siiiiiiiiiiiiiiiiii en dos la hace tira..jaja
y teniendo dos mitades para ordenar recursivamente por ejemplo
a el pivote es al azar
8 5 3 4 10 12 6 7 15 9
pivote 8
A1=5 3 4 6 7 contemos 9 comparaciones
A2=10 12 15 9
A1 pivote 5
A11 3 4 contemos 4 comparaciones
A12 6 7
A11 pivote 3
A111 0 3 4 contemos 1 comparacion
A112 4
A12 pivote 6
A121 0 6, 7 contemos 1 comparacion
A122 7
En este punto la salida del arreglo A1= 3 4 5 6 7 ya esta ordenada nada que hacer hasta aqui fin.
A2 pivotin 10
A21 9 contemos 3 comp
A22 12 15
pivotin 12
A221 0 1 comp
A222 12 15
Salida A2 9 10 12 15
finalmente 3 4 5 6 7 8 9 10 12 15 total 19 comparaciones
Peor Caso: el pivotin sea el maximo o bien el minimo del arreglo (se manda toda ..jaja)
en funcion de n comparaciones te queda
T(n)=T(n-1)+ n-1
T(1)=0
o sea que esta cuestion tiene un orden n cuadrado
y el mejor de los casos ( si como los grandes amigos mitad y mitad) ajjaj
es decir que el pivotin divida en partes iguales
T(1)=0
T(n)=2T(n/2)+ n-1
te acuerdas que saca la mitad empezamos comparar ahi aparece ese n-1 y n/2 porque parte en dos
aplica log
T(n) - 0(n lg n)
falta uno escribir eso aqui solo con este blog no ...
es una ecuacion grande es el caso de caso promedio en donde el pivotin tiene 1/n probabilidad de ser elegedio el rey
buen en fin ese es el asunto pudes hacer esto mismo con todo los algoritmo de seleccion suerte amigo y busca un libro o consutla a un profesor
si entendiste bien y sino andate a la chu.....jaajaj
Pues una opción es agregar un
Pues una opción es agregar un contador e incrementarlo.
public static void burbuja( int arreglo[] ) { int intercambio = 0; int comparaciones = 0; ... if( arreglo[j] > arreglo[ j + 1 ] ) { comparaciones++; ... intercambio++; ... }Algo así?
Muy Bien
Muchas gracias por respoderme. Seguire sus indicaciones
duda!
antes que nada uyna disculpa por revivir el tema, pero estoy viendo justamente este tema, en una instancia pense igual un contador en el if, peor supongamos que tenemos un arrgelo d 5 y lo ordenamos por burbuja el numero d comparaciones es 10 y el contador arroja 5, d 10 se supone que debe ser 45 y el contador arroja algo asi como 18,entons no creo que sea la solucion optima, entonces alguna otra recomendacion, cabe aclarar ke trabajo condatos primitivos. D antemano gracias por la ayuda
@puzzlemaniaco Quizá tu
@puzzlemaniaco Quizá tu arreglo ya estaba casi ordenado y no hizo ningún ( o pocos ) intercambios:
Considera:
Este con BubbleSort solo haría 2 intercambios.
:)
mmmm no se supone que aunque este arreglado el burbuja hace las comparaciones?
Bueno si lo pusiste como en
Bueno si lo pusiste como en el código de muestra, en realidad el contador se incrementa cuando hace permutaciones.
Sin ver tú código pues es mucho más difícil saber de que estamos hablando.
burbuja.addActionListener(ne
{
public void actionPerformed(ActionEvent e)
{
int [] arre=new int[MAX];
int i,j,temp,cont=0;
String salida="";
arre=promedio();
long tiempoInicio = System.currentTimeMillis();
for(i=1;i<arre.length;i++)
{
for(j=arre.length-1;j>=i;j--)
if(arre[j]<arre[j-1])
{
temp=arre[j];
arre[j]=arre[j-1];
arre[j-1]=temp;
}
cont++
}
long totalTiempo = System.currentTimeMillis() - tiempoInicio;
for(int x=0;x<arre.length;x++)
salida+="arre "+"["+x+"]"+ " = "+arre[x]+ "\n";
area.setText("");
centro.setVisible(true);
scrollpane.setVisible(true);
area.append("Metodo de la Burbuja"+"\n" +salida + "Tiempo en ordenar: "+ totalTiempo +" milisegundos" "intercambios"+cont);
area.getSelectedText();
centro.add(scrollpane);
}//dl evento
});
PUes a mi se me ocurrio algo asi, d momento calculo segun yo el tiempo d ejecucion pero tambien me gustaria saber las comparaciones
Ahhh .. .ya.. Por eso digo
Ahhh .. .ya..
Por eso digo que los if's for's while's y todo lo que pueda llevar llave DEBEN de llevar llave.
Tu contador lo estás poniendo debajo del if, e identado con el 2do for, pero no pertenece al 2do for sino al primero mira:
for(i=1;i<arre.length;i++) //<-- primer for
{
for(j=arre.length-1;j>=i;j--) //<-- segundo for SIN llave
if(arre[j]<arre[j-1]) //<-- cuerpo del for
{
temp=arre[j];
arre[j]=arre[j-1];
arre[j-1]=temp;
}
cont++ //<-- este pertenece al primero
}
Por eso te sale 5, porque el contador se incrementa solo 5 veces.
Intenta con:
for( int i = 1; i < arre.length; i++ ) {
for( int j = arre.length - 1; j >=i ; j--) {
if( arre[j] < arre[j - 1]) {
temp=arre[j];
arre[j]=arre[j-1];
arre[j-1]=temp;
}
cont++ //Ahora si está dentro del 2do for.
}
}
Si?
Por cierto, como recomendación fíjate en el estilo que pongo en el código, ese es un estilo más común en Java, el que tienes es más común en C. Aunque a la máquina le da exactamente lo mismo, es recomendable adoptar el estilo del lenguaje. Es como el acento.
Espero que te sirva.
P.D. No corrí el código ni nada, nomás he eché un ojo, pero debería de funcionar.
lo he probado asi como deica
lo he probado asi como deica y funciona arroka el numero de comparaciones gracias por la ayuda, repecto al consejo estoy aprendiendo a porgrmar como segun debe ser ya sabes con clases abstractas,encapsulamientos, y demas y no habia escchuado d tu consejo, asi ke gracias tambien por eso.... un saludo y buena vibra
Jejej si.. Lo que pasa es
Jejej si..
Lo que pasa es que la mayoría de los lugares se enfoca en lo técnico, en como funcionan las cosas y demás, pero pocos se centran en lo cualitativo, en la importancia que tiene escribir código que otros humanos puedan comprender ( o más bien si hay pero cuando estás buscando sobre "encapsulamiento" - por ejemplo - pues no hablan de esto )
También es un aspecto polemico, sobre todo para quién ya lleva varios años programando de una forma; es difícil cambiar sus hábitos, pero tratándose de alguien que como en tu caso esta aprendiendo me parece una excelente oportunidad para mencionarlo ( y espero que no te ofendas como otros cuando noto que como tu mismo dices, estás aprendiendo , pffff ) .
Por ejemplo en StackOverflow hace como 3 años tuve un "intercambio" de opiniones ( ver comentarios ) con Jon Skeet que es el usuario #1 de StackOverflow de entre más de 660 mill usuarios ( muchos de ellos empleados de Google por ejemplo , el mismo lo es ) sobre estas convenciones. Él es un hacker que utiliza principalmente C# y Java y los domina ampliamente y en esa ocasión le hice notar sobre las llaves y la convenciones de Java y etc. y su respuesta fue que si bien entre los nombres de clases, métodos y variables si hay una convención ampliamente aceptada ( classes empiezan con Mayúscula, variables y métodos con minúscula, nombres en CamelCase en vez de no_se_como ) para las llaves es muy debatible.
Aún así y como decía al principio, es bueno que si alguien va empezando se le recomiende este estilo; es el más común en la gran mayoría del código escrito en Java. Cuando ya lo conozcas y lo domines y si aún así quieres seguir tu propia convención pues también está bien.
Me acuerdo que @marce me sugirió que hiciera un post sobre esto. Lo voy a hacer, pero lo quiero hacer de una forma que se pueda entender y leer fácilmente. No tiene caso tirar un pared de texto.
Mientras tanto acá están las Convenciones para codificar del lenguaje de programación Java ( Inglés ) escritos en 1999.
Saludos.