style="display:inline-block;width:728px;height:90px"
data-ad-client="ca-pub-5164839828746352"
data-ad-slot="7563230308">

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

AdjuntoTamaño
Codigo.txt2.36 KB

Comentarios

Opciones de visualización de comentarios

Seleccione la forma que prefiera para mostrar los comentarios y haga clic en «Guardar las opciones» para activar los cambios.
Imagen de ezamudio

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 compare que 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

Imagen de puzzlemaniaco

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:

[1,2,4,3,5,6,7,8,10,9]

Este con BubbleSort solo haría 2 intercambios.

Imagen de puzzlemaniaco

:)

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.

Imagen de puzzlemaniaco

 burbuja.addActionListener(ne

 burbuja.addActionListener(new ActionListener()
         {

                 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.

Imagen de puzzlemaniaco

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.

style="display:inline-block;width:728px;height:90px"
data-ad-client="ca-pub-5164839828746352"
data-ad-slot="7563230308">