analisis codigos de ordenamiento

[m@o_614]

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 (c) [Seleccionar] Expandir

#include <stdio.h>
#include <stdlib.h>
#define MAX 100

void Ordenacion_Burbuja(int v[],int n);

int main()
{
    int i,n,v[MAX];
    printf("Dame el numero de elementos del vector: ");
    scanf("%d",&n);
    for(i=0;i < n;i++)
    {
        printf("Dame el elemento numero %d:\n",i+1);
        scanf("%d",&v[i]);
        system("cls");
    }
    Ordenacion_Burbuja(v,n);

    for(i=0;i < n;i++)
       printf("[%d]",v[i]);
    return 0;
}

void Ordenacion_Burbuja(int v[],int n)
{
    int i,j,aux;
    for(i=1;i < n;i++)
    {
        for(j=0;j < n-i;j++)
        {
            if(v[j] > v[j+1])
            {
                aux = v[j+1];
                v[j+1] = v[j];
                v[j] = aux;
            }
        }
    }
}


INSERCION

Código (c) [Seleccionar] Expandir

#include <stdio.h>
#include <stdlib.h>
#define MAX 100

void metodo_Insercion(int v[],int n);

int main()
{
    int i,v[MAX],n;
    printf("Dame el numero de elementos del vector: ");
    scanf("%d",&n);
    for(i=0;i < n;i++)
    {
        printf("Dame el elemento numero %d:\n",i+1);
        scanf("%d",&v[i]);
        system("cls");
    }
    metodo_Insercion(v,n);
    for(i=0;i < n;i++)
       printf("[%d]",v[i]);
    return 0;
}

void metodo_Insercion(int v[],int n)
{
    int i,j,aux;
    for(i=1;i < n ;i++)
    {
        for(j=i;j > 0;j--)
        {
            if(v[j] < v[j-1])
            {
                aux = v[j];
                v[j] = v[j-1];
                v[j-1] = aux;
            }
        }
    }

}


SELECCION

Código (c) [Seleccionar] Expandir

#include <stdio.h>
#include <stdlib.h>
#define MAX 100

void metodo_Seleccion();
int Minimo(int v[],int n);
void intercambiar(int pos,int v[]);

int main()
{
    int n,i,v[MAX],pos;
    printf("Dame el numero de elementos del vector: ");
    scanf("%d",&n);
    for(i=0;i < n;i++)
    {
        printf("Dame el elemento numero %d: ",i+1);
        scanf("%d",&v[i]);
        system("cls");
    }

    metodo_Seleccion(v,n);
    for(i=0;i < n;i++)
        printf("[%d]",v[i]);
    return 0;
}

void metodo_Seleccion(int v[],int n)
{
    int i,j,minimo,aux,pos;
    for(i=0;i < n;i++)
    {
        minimo = v[i];
        pos = i;
        for(j=i+1;j < n;j++)
        {
            if(v[j] < minimo)
            {
                minimo = v[j];
                pos = j;
            }
        }
        aux = v[pos];
        v[pos] = v[i];
        v[i] = aux;
    }
}


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

[xiruko]

Aquí tienes un ejemplo exactamente con lo que pides.

Saludos

[Mad Antrax]

aprovechando el hilo, os dejo 15 algoritmos de ordenación representados de forma gráfica/auditiva, me encantan éste tipo de videos:

[youtube=640,360]http://www.youtube.com/watch?v=kPRA0W1kECg[/youtube]

[m@o_614]

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???

[xiruko]

En estos caso se suele hacer que se inicialice de manera aleatoria, asignando números aleatorios con rand() en un ciclo que recorra el array de elementos.

Saludos

[flony]

lindo video

[m@o_614]

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 (c) [Seleccionar] Expandir

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

typedef struct
{
    int numero;
}Arreglo;

void Ordenacion_Burbuja(int v[],int n);

int main()
{
    FILE *fd;
    Arreglo arreglo[5];
    if((fd = fopen("F:\\Analisis_algoritmos","r"))!=NULL)
    {
        Ordenacion_Burbuja(arreglo,5);
        Ordenacion_Burbuja(arreglo,10);
        Ordenacion_Burbuja(arreglo,100);
        Ordenacion_Burbuja(arreglo,1000);
        Ordenacion_Burbuja(arreglo,10000);
        Ordenacion_Burbuja(arreglo,100000);
        Ordenacion_Burbuja(arreglo,1000000);
    }
    return 0;
}

void Ordenacion_Burbuja(int arreglo[],int n)
{
    int i,j,aux;
    for(i=1;i < n;i++)
    {
        for(j=0;j < n-i;j++)
        {
            if(v[j] > v[j+1])
            {
                aux = v[j+1];
                v[j+1] = v[j];
                v[j] = aux;
            }
        }
    }
    for(i=0;i < MAX;i++)
       printf("[%d]",v[i]);
}


gracias por su ayuda

[rir3760]

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 (c) [Seleccionar] Expandir

FILE *salida;

/* ... */

if ((salida = fopen(NOM_SALIDA, "wt")) == NULL){
   /* Manejo de error */
}

El siguiente paso es enviar los datos al archivo mediante un bucle, las tres opciones son:

Código (c) [Seleccionar] Expandir

/* A) Se imprime la serie 0 .. MAX-1 en el archivo */
for (i = 0; i < MAX; i++)
   fprintf(salida, "%d\n", i);

/* B) Se imprime la serie MAX-1 .. 0 en el archivo */
i = MAX;
while (i > 0){
   i--;
   
   fprintf(salida, "%d\n", i);
}

/* C) Se imprimen valores aleatorios en el archivo */
for (i = 0; i < MAX; i++)
   fprintf(salida, "%d\n", rand());

El ultimo paso es simplemente cerrar el archivo.

Creo que la cosa va mas o menos asi:

Código (c) [Seleccionar] Expandir

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

typedef struct
{
    int numero;
}Arreglo;

void Ordenacion_Burbuja(int v[],int n);

int main()
{
    FILE *fd;
    Arreglo arreglo[5];
    if((fd = fopen("F:\\Analisis_algoritmos","r"))!=NULL)
    {
        Ordenacion_Burbuja(arreglo,5);
        Ordenacion_Burbuja(arreglo,10);
        Ordenacion_Burbuja(arreglo,100);
        Ordenacion_Burbuja(arreglo,1000);
        Ordenacion_Burbuja(arreglo,10000);
        Ordenacion_Burbuja(arreglo,100000);
        Ordenacion_Burbuja(arreglo,1000000);
    }
    return 0;
}

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

[m@o_614]

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 (c) [Seleccionar] Expandir

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

void Ordenacion_Burbuja(long v[],long n,FILE *fd);
void analizar_Burbuja(char nombreArchivo[],FILE *fd,long n);

int main()
{
   FILE *fd;
   if((fd = fopen("F:\\Analisis_algoritmos.txt","w"))!=NULL)
   {/*
       analizar_Burbuja("5-Ordenados",fd,5);
       analizar_Burbuja("10-Ordenados",fd,10);
       analizar_Burbuja("100-Ordenados",fd,100);
       analizar_Burbuja("1000-Ordenados",fd,1000);
       analizar_Burbuja("10000-Ordenados",fd,10000);
       analizar_Burbuja("100000-Ordenados",fd,100000);
       analizar_Burbuja("1000000-Ordenados",fd,1000000);*/

       analizar_Burbuja("5-Desordenados",fd,5);/*
       analizar_Burbuja("10-Desordenados",fd,10);
       analizar_Burbuja("100-Desordenados",fd,100);
       analizar_Burbuja("1000-Desordenados",fd,1000);
       analizar_Burbuja("10000-Desordenados",fd,10000);
       analizar_Burbuja("100000-Desordenados",fd,100000);
       analizar_Burbuja("1000000-Desordenados",fd,1000000);*/

   }
   else
      printf("No se pudo leer archivo");
   return 0;
}

void Ordenacion_Burbuja(long v[],long n,FILE *fd)
{
   int i,j,aux;
   for(i=1;i < n;i++)
   {
       for(j=0;j < n-i;j++)
       {
           if(v[j] > v[j+1])
           {
               aux = v[j+1];
               v[j+1] = v[j];
               v[j] = aux;
           }
       }
   }
   fwrite(v,sizeof(int),n,fd);
}

void analizar_Burbuja(char nombreArchivo[],FILE *fd,long n)
{
   int i;
   FILE *entrada;
   long *arreglo;
   char ruta[50];

   sprintf(ruta,"F:\\%s.txt",nombreArchivo);
   puts(ruta);

   if((entrada = fopen(ruta,"r"))!=NULL)
   {
       arreglo = (long*)malloc(n*sizeof(long));
       i = 0;
       while(!feof(entrada))
       {
           fscanf(entrada,"%ld",&arreglo[i]);
           i++;
       }
       Ordenacion_Burbuja(arreglo,n,fd);
   }
   else
      printf("No se pudo abrir archivo");

}


de antemano gracias

[rir3760]

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 (c) [Seleccionar] Expandir

void Ordenacion_Burbuja(long v[], long n, FILE *fd)
{
   /* ... */
   
   fwrite(v, sizeof(int), n, fd);
}
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