Foro de elhacker.net

Programación => Programación C/C++ => Mensaje iniciado por: m@o_614 en 18 Septiembre 2013, 18:59 pm


Título: analisis codigos de ordenamiento
Publicado por: m@o_614 en 18 Septiembre 2013, 18:59 pm
Saludos tengo que codificar algunos codigos de ordenamiento y despues me pide que los compare de acuerdo a su tiempo de ejecucion, ya sea para un array de 1000, 10000 o 1000000, los codigos ya los tengo hechos

BURBUJA
Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define MAX 100
  4.  
  5. void Ordenacion_Burbuja(int v[],int n);
  6.  
  7. int main()
  8. {
  9.     int i,n,v[MAX];
  10.     printf("Dame el numero de elementos del vector: ");
  11.     scanf("%d",&n);
  12.     for(i=0;i < n;i++)
  13.     {
  14.         printf("Dame el elemento numero %d:\n",i+1);
  15.         scanf("%d",&v[i]);
  16.         system("cls");
  17.     }
  18.     Ordenacion_Burbuja(v,n);
  19.  
  20.     for(i=0;i < n;i++)
  21.        printf("[%d]",v[i]);
  22.     return 0;
  23. }
  24.  
  25. void Ordenacion_Burbuja(int v[],int n)
  26. {
  27.     int i,j,aux;
  28.     for(i=1;i < n;i++)
  29.     {
  30.         for(j=0;j < n-i;j++)
  31.         {
  32.             if(v[j] > v[j+1])
  33.             {
  34.                 aux = v[j+1];
  35.                 v[j+1] = v[j];
  36.                 v[j] = aux;
  37.             }
  38.         }
  39.     }
  40. }
  41.  

INSERCION
Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define MAX 100
  4.  
  5. void metodo_Insercion(int v[],int n);
  6.  
  7. int main()
  8. {
  9.     int i,v[MAX],n;
  10.     printf("Dame el numero de elementos del vector: ");
  11.     scanf("%d",&n);
  12.     for(i=0;i < n;i++)
  13.     {
  14.         printf("Dame el elemento numero %d:\n",i+1);
  15.         scanf("%d",&v[i]);
  16.         system("cls");
  17.     }
  18.     metodo_Insercion(v,n);
  19.     for(i=0;i < n;i++)
  20.        printf("[%d]",v[i]);
  21.     return 0;
  22. }
  23.  
  24. void metodo_Insercion(int v[],int n)
  25. {
  26.     int i,j,aux;
  27.     for(i=1;i < n ;i++)
  28.     {
  29.         for(j=i;j > 0;j--)
  30.         {
  31.             if(v[j] < v[j-1])
  32.             {
  33.                 aux = v[j];
  34.                 v[j] = v[j-1];
  35.                 v[j-1] = aux;
  36.             }
  37.         }
  38.     }
  39.  
  40. }
  41.  

SELECCION

Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define MAX 100
  4.  
  5. void metodo_Seleccion();
  6. int Minimo(int v[],int n);
  7. void intercambiar(int pos,int v[]);
  8.  
  9. int main()
  10. {
  11.     int n,i,v[MAX],pos;
  12.     printf("Dame el numero de elementos del vector: ");
  13.     scanf("%d",&n);
  14.     for(i=0;i < n;i++)
  15.     {
  16.         printf("Dame el elemento numero %d: ",i+1);
  17.         scanf("%d",&v[i]);
  18.         system("cls");
  19.     }
  20.  
  21.     metodo_Seleccion(v,n);
  22.     for(i=0;i < n;i++)
  23.         printf("[%d]",v[i]);
  24.     return 0;
  25. }
  26.  
  27. void metodo_Seleccion(int v[],int n)
  28. {
  29.     int i,j,minimo,aux,pos;
  30.     for(i=0;i < n;i++)
  31.     {
  32.         minimo = v[i];
  33.         pos = i;
  34.         for(j=i+1;j < n;j++)
  35.         {
  36.             if(v[j] < minimo)
  37.             {
  38.                 minimo = v[j];
  39.                 pos = j;
  40.             }
  41.         }
  42.         aux = v[pos];
  43.         v[pos] = v[i];
  44.         v[i] = aux;
  45.     }
  46. }
  47.  

El problema es que no tengo idea como determinar los tiempos que le toma a cada uno ordenar un vector, como se puede hacer???

de antemano gracias

Título: Re: analisis codigos de ordenamiento
Publicado por: xiruko en 18 Septiembre 2013, 19:05 pm
Aquí (http://c.conclase.net/librerias/?ansifun=time) tienes un ejemplo exactamente con lo que pides.

Saludos

Título: Re: analisis codigos de ordenamiento
Publicado por: Mad Antrax en 18 Septiembre 2013, 19:17 pm
aprovechando el hilo, os dejo 15 algoritmos de ordenación representados de forma gráfica/auditiva, me encantan éste tipo de videos:

kPRA0W1kECg

Título: Re: analisis codigos de ordenamiento
Publicado por: m@o_614 en 19 Septiembre 2013, 04:38 am
muchas gracias a ambos por sus respuestas, una ultima duda el profesor me pidio que comparara los tiempos de ejecucion de los algoritmos con vectores de tamanio que va desde el 10 hasta el millon!!!! y eso me parece demasiado estarle ingresando numerito por numerito, creen que es mejor crear un archivo que ya tenga los numeros y despues ya que abra el archivo y los ordene o que otra opcion hay???


Título: Re: analisis codigos de ordenamiento
Publicado por: xiruko en 19 Septiembre 2013, 05:40 am
En estos caso se suele hacer que se inicialice de manera aleatoria, asignando números aleatorios con rand() (http://c.conclase.net/librerias/?ansifun=rand) en un ciclo que recorra el array de elementos.

Saludos

Título: Re: analisis codigos de ordenamiento
Publicado por: flony en 19 Septiembre 2013, 23:47 pm
lindo video

Título: Re: analisis codigos de ordenamiento
Publicado por: m@o_614 en 20 Septiembre 2013, 02:27 am
xiruko yo tambien pensaba que con la funcion rand() seria todo mas facil, pero el profesor me dijo que tengo que utilizar archivos ordenados, inversamente ordenados y aleatorios, de 10, 100,1000,10000,100000,1'000,000, y ps como las cantidades son tan grandes no puedo ingresarle numero por numero y como son ordenadas y no solo aleatorias no puedo usar el rand(),voy a tener que usar archivos, pero yo todavia estoy muy verde en eso.

Estaba pensando que en un archivo.txt meterle los numeros y despues irlos leyendo o algo asi pero la verdad no se muy bien como le voy a hacer

Creo que la cosa va mas o menos asi:
Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <unistd.h>
  4.  
  5. typedef struct
  6. {
  7.     int numero;
  8. }Arreglo;
  9.  
  10. void Ordenacion_Burbuja(int v[],int n);
  11.  
  12. int main()
  13. {
  14.     FILE *fd;
  15.     Arreglo arreglo[5];
  16.     if((fd = fopen("F:\\Analisis_algoritmos","r"))!=NULL)
  17.     {
  18.         Ordenacion_Burbuja(arreglo,5);
  19.         Ordenacion_Burbuja(arreglo,10);
  20.         Ordenacion_Burbuja(arreglo,100);
  21.         Ordenacion_Burbuja(arreglo,1000);
  22.         Ordenacion_Burbuja(arreglo,10000);
  23.         Ordenacion_Burbuja(arreglo,100000);
  24.         Ordenacion_Burbuja(arreglo,1000000);
  25.     }
  26.     return 0;
  27. }
  28.  
  29. void Ordenacion_Burbuja(int arreglo[],int n)
  30. {
  31.     int i,j,aux;
  32.     for(i=1;i < n;i++)
  33.     {
  34.         for(j=0;j < n-i;j++)
  35.         {
  36.             if(v[j] > v[j+1])
  37.             {
  38.                 aux = v[j+1];
  39.                 v[j+1] = v[j];
  40.                 v[j] = aux;
  41.             }
  42.         }
  43.     }
  44.     for(i=0;i < MAX;i++)
  45.        printf("[%d]",v[i]);
  46. }
  47.  

gracias por su ayuda

Título: Re: analisis codigos de ordenamiento
Publicado por: rir3760 en 21 Septiembre 2013, 03:17 am
Cita de: m@o_614 en 20 Septiembre 2013, 02:27 am
el profesor me dijo que tengo que utilizar archivos ordenados, inversamente ordenados y aleatorios, de 10, 100,1000,10000,100000,1'000,000, y ps como las cantidades son tan grandes no puedo ingresarle numero por numero y como son ordenadas y no solo aleatorias no puedo usar el rand(),voy a tener que usar archivos, pero yo todavia estoy muy verde en eso.
Es fácil, para abrir el archivo:
Código
  1. FILE *salida;
  2.  
  3. /* ... */
  4.  
  5. if ((salida = fopen(NOM_SALIDA, "wt")) == NULL){
  6.    /* Manejo de error */
  7. }

El siguiente paso es enviar los datos al archivo mediante un bucle, las tres opciones son:
Código
  1. /* A) Se imprime la serie 0 .. MAX-1 en el archivo */
  2. for (i = 0; i < MAX; i++)
  3.    fprintf(salida, "%d\n", i);
  4.  
  5. /* B) Se imprime la serie MAX-1 .. 0 en el archivo */
  6. i = MAX;
  7. while (i > 0){
  8.    i--;
  9.  
  10.    fprintf(salida, "%d\n", i);
  11. }
  12.  
  13. /* C) Se imprimen valores aleatorios en el archivo */
  14. for (i = 0; i < MAX; i++)
  15.    fprintf(salida, "%d\n", rand());

El ultimo paso es simplemente cerrar el archivo.


Cita de: m@o_614 en 20 Septiembre 2013, 02:27 am
Creo que la cosa va mas o menos asi:
Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <unistd.h>
  4.  
  5. typedef struct
  6. {
  7.     int numero;
  8. }Arreglo;
  9.  
  10. void Ordenacion_Burbuja(int v[],int n);
  11.  
  12. int main()
  13. {
  14.     FILE *fd;
  15.     Arreglo arreglo[5];
  16.     if((fd = fopen("F:\\Analisis_algoritmos","r"))!=NULL)
  17.     {
  18.         Ordenacion_Burbuja(arreglo,5);
  19.         Ordenacion_Burbuja(arreglo,10);
  20.         Ordenacion_Burbuja(arreglo,100);
  21.         Ordenacion_Burbuja(arreglo,1000);
  22.         Ordenacion_Burbuja(arreglo,10000);
  23.         Ordenacion_Burbuja(arreglo,100000);
  24.         Ordenacion_Burbuja(arreglo,1000000);
  25.     }
  26.     return 0;
  27. }
Ese programa no va a funcionar ya que tiene varios errores, algunos de ellos graves. Por ejemplo declaras una estructura con un solo campo lo que no tiene caso, declaras un array de estructuras pero la función espera un array de enteros (tipo int), declaras un array de 5 elementos pero tratas de utilizarlo para procesar mas números de los que puede almacenar, no es necesario incluir el encabezado <unistd.h>, etc.

Un saludo

Título: Re: analisis codigos de ordenamiento
Publicado por: m@o_614 en 21 Septiembre 2013, 22:48 pm
saludos rir3760 le hice algunos cambios al codigo le puse que me leyera los elemento que tengo en un archivo de texto y me los guardara en un arreglo que luego le voy a pasar a la funcion Ordenacion_burbuja para que me los ordene y en esa misma funcion con un fwrite le digo que me imprima en otro archivo el arreglo ya ordenado el problema es que me imprime basura en el archivo Analisis_algoritmos, que es el que cree para que se escribiera en el

Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <unistd.h>
  4.  
  5. void Ordenacion_Burbuja(long v[],long n,FILE *fd);
  6. void analizar_Burbuja(char nombreArchivo[],FILE *fd,long n);
  7.  
  8. int main()
  9. {
  10.     FILE *fd;
  11.     if((fd = fopen("F:\\Analisis_algoritmos.txt","w"))!=NULL)
  12.     {/*
  13.         analizar_Burbuja("5-Ordenados",fd,5);
  14.         analizar_Burbuja("10-Ordenados",fd,10);
  15.         analizar_Burbuja("100-Ordenados",fd,100);
  16.         analizar_Burbuja("1000-Ordenados",fd,1000);
  17.         analizar_Burbuja("10000-Ordenados",fd,10000);
  18.         analizar_Burbuja("100000-Ordenados",fd,100000);
  19.         analizar_Burbuja("1000000-Ordenados",fd,1000000);*/
  20.  
  21.         analizar_Burbuja("5-Desordenados",fd,5);/*
  22.         analizar_Burbuja("10-Desordenados",fd,10);
  23.         analizar_Burbuja("100-Desordenados",fd,100);
  24.         analizar_Burbuja("1000-Desordenados",fd,1000);
  25.         analizar_Burbuja("10000-Desordenados",fd,10000);
  26.         analizar_Burbuja("100000-Desordenados",fd,100000);
  27.         analizar_Burbuja("1000000-Desordenados",fd,1000000);*/
  28.  
  29.     }
  30.     else
  31.        printf("No se pudo leer archivo");
  32.     return 0;
  33. }
  34.  
  35. void Ordenacion_Burbuja(long v[],long n,FILE *fd)
  36. {
  37.     int i,j,aux;
  38.     for(i=1;i < n;i++)
  39.     {
  40.         for(j=0;j < n-i;j++)
  41.         {
  42.             if(v[j] > v[j+1])
  43.             {
  44.                 aux = v[j+1];
  45.                 v[j+1] = v[j];
  46.                 v[j] = aux;
  47.             }
  48.         }
  49.     }
  50.     fwrite(v,sizeof(int),n,fd);
  51. }
  52.  
  53. void analizar_Burbuja(char nombreArchivo[],FILE *fd,long n)
  54. {
  55.     int i;
  56.     FILE *entrada;
  57.     long *arreglo;
  58.     char ruta[50];
  59.  
  60.     sprintf(ruta,"F:\\%s.txt",nombreArchivo);
  61.     puts(ruta);
  62.  
  63.     if((entrada = fopen(ruta,"r"))!=NULL)
  64.     {
  65.         arreglo = (long*)malloc(n*sizeof(long));
  66.         i = 0;
  67.         while(!feof(entrada))
  68.         {
  69.             fscanf(entrada,"%ld",&arreglo[i]);
  70.             i++;
  71.         }
  72.         Ordenacion_Burbuja(arreglo,n,fd);
  73.     }
  74.     else
  75.        printf("No se pudo abrir archivo");
  76.  
  77. }
  78.  

de antemano gracias

Título: Re: analisis codigos de ordenamiento
Publicado por: rir3760 en 22 Septiembre 2013, 03:13 am
Sin animo de molestar pero ya en varias ocasiones te he indicado que:
1) No es necesario incluir el encabezado <unistd.h>.
2) No se debe utilizar la función feof para controlar un bucle.

Revisando el programa un error se encuentra en la función:
Código
  1. void Ordenacion_Burbuja(long v[], long n, FILE *fd)
  2. {
  3.    /* ... */
  4.  
  5.    fwrite(v, sizeof(int), n, fd);
  6. }
Ahí indicas que el tamaño del elemento es igual a "sizeof(int)" cuando debería ser "sizeof(long)".

Ademas de eso por alguna extraña razón lees los numeros con fscanf (texto con formato) y los escribes con fwrite (bytes "crudos"). Deberías utilizar el mismo modo (de preferencia texto con formato) y publicar ejemplos de los archivos de entrada y salida.

Un saludo

Título: Re: analisis codigos de ordenamiento
Publicado por: m@o_614 en 22 Septiembre 2013, 19:33 pm
Saludos rir3760 ya le quite al codigo la libreria unistd.h, ya entendi que no es necesario usarla, pero con respecto al feof no tengo idea de que otra manera sustituirlo.le hice unos cambios al codigo para que en vez de que me imprimiera el vector ordenado en el archivo me imprima el numero de intercambios que se hacen en el metodo de ordenamiento pero me imprime una cantidad que no es en un arreglo  desordenado me dice que solo necesita un intercambio

Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. void Ordenacion_Burbuja(int v[],int n,FILE *fd);
  5. void analizar_Burbuja(char nombreArchivo[],FILE *fd,int n);
  6.  
  7. int main()
  8. {
  9.     FILE *fd;
  10.     if((fd = fopen("F:\\Analisis_algoritmos.txt","w"))!=NULL)
  11.     {/*
  12.         analizar_Burbuja("5-Ordenados",fd,5);
  13.         analizar_Burbuja("10-Ordenados",fd,10);
  14.         analizar_Burbuja("100-Ordenados",fd,100);
  15.         analizar_Burbuja("1000-Ordenados",fd,1000);
  16.         analizar_Burbuja("10000-Ordenados",fd,10000);
  17.         analizar_Burbuja("100000-Ordenados",fd,100000);
  18.         analizar_Burbuja("1000000-Ordenados",fd,1000000);*/
  19.  
  20.         analizar_Burbuja("5-Desordenados",fd,5);/*
  21.         analizar_Burbuja("10-Desordenados",fd,10);
  22.         analizar_Burbuja("100-Desordenados",fd,100);
  23.         analizar_Burbuja("1000-Desordenados",fd,1000);
  24.         analizar_Burbuja("10000-Desordenados",fd,10000);
  25.         analizar_Burbuja("100000-Desordenados",fd,100000);
  26.         analizar_Burbuja("1000000-Desordenados",fd,1000000);*/
  27.  
  28.     }
  29.     else
  30.        printf("No se pudo leer archivo");
  31.     return 0;
  32. }
  33.  
  34. void Ordenacion_Burbuja(int v[],int n,FILE *fd)
  35. {
  36.     int i,j,aux,intercambio=0;
  37.     for(i=1;i < n;i++)
  38.     {
  39.         for(j=0;j < n-i;j++)
  40.         {
  41.             if(v[j] > v[j+1])
  42.             {
  43.                 aux = v[j+1];
  44.                 v[j+1] = v[j];
  45.                 v[j] = aux;
  46.                 intercambio++;
  47.             }
  48.         }
  49.     }
  50.     fprintf(fd,"El numero de intercambios es %d",intercambio);
  51. }
  52.  
  53. void analizar_Burbuja(char nombreArchivo[],FILE *fd,int n)
  54. {
  55.     int i;
  56.     FILE *entrada;
  57.     int *arreglo;
  58.     char ruta[50];
  59.  
  60.     sprintf(ruta,"F:\\%s.txt",nombreArchivo);
  61.     puts(ruta);
  62.  
  63.     if((entrada = fopen(ruta,"r"))!=NULL)
  64.     {
  65.         arreglo = (int*)malloc(n*sizeof(int));
  66.         i = 0;
  67.         while(!feof(entrada))
  68.         {
  69.             fscanf(entrada,"%d",&arreglo[i]);
  70.             i++;
  71.         }
  72.         Ordenacion_Burbuja(arreglo,n,fd);
  73.     }
  74.     else
  75.        printf("No se pudo abrir archivo");
  76.  
  77. }
  78.  

de antemano gracias

Título: Re: analisis codigos de ordenamiento
Publicado por: rir3760 en 24 Septiembre 2013, 06:36 am
Cita de: m@o_614 en 22 Septiembre 2013, 19:33 pm
con respecto al feof no tengo idea de que otra manera sustituirlo.
Solo tienes que verificar el valor de retorno de la función de entrada/salida, casi todas retornan un valor particular en caso de error o fin de archivo.

En el caso de fscanf esta retorna el numero de conversiones realizadas con exito o EOF en caso de error o fin de archivo, tu bucle:
Código
  1. i = 0;
  2. while(!feof(entrada))
  3. {
  4.    fscanf(entrada,"%d",&arreglo[i]);
  5.    i++;
  6. }
Realiza una iteración de mas y es demasiado largo. Utilizando el valor de retorno de fscanf se puede reducir a:
Código
  1. for (i = 0; i < n && fscanf(entrada, "%d", arreglo + i) == 1; i++)
  2.    ;
Se debe realizar la verificación "i < n" para asegurarnos de no leer mas de lo que se puede almacenar en el bloque de memoria.

Cita de: m@o_614 en 22 Septiembre 2013, 19:33 pm
le hice unos cambios al codigo para que en vez de que me imprimiera el vector ordenado en el archivo me imprima el numero de intercambios que se hacen en el metodo de ordenamiento pero me imprime una cantidad que no es en un arreglo  desordenado me dice que solo necesita un intercambio
Si el archivo de entrada es correcto (texto plano) el programa da los resultados esperados, eso lo debes verificar en tu PC.

Un saludo


Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines