Problema con la ejecución de un algoritmo en C

Iniciado por BeFree, 19 Junio 2013, 19:33 PM

0 Miembros y 2 Visitantes están viendo este tema.

BeFree

Hola, tengo que hacer un algoritmo que ordene N números naturales generados en forma aleatoria. Tiene que ejecutarse para 1000, 10000 y 100000. Escribí un código y al ejecutarlo lo hace sin problemas para 1000 y 10000, pero para 100000 no me muestra el resultado, y no puedo hallar el error.
Si me pueden ayudar se los agradecería. Ah trabajo en un entorno linux, que es una virtualización sobre window.

Acá les dejo el código que escribí:

//Secuencial - OrdenacionSectp5.c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

/*Declaración de variables globales*/
unsigned long int MAX=100000;

/*Generar datos*/
void CagarDatos(unsigned long int v[], unsigned long int N)
{
   unsigned long int i,j;
   int duplicado;
   unsigned long int num;
 
   for(i=0; i<N; i++)
   {
      num=1+rand()%N;
      duplicado=0;

       for(j=0; j<=i; j++)
      {
         if(num==v[j])
         {
            duplicado=1;
            break;
         }
      }
      if(duplicado==1)
         i--;
      else
         v=num;
   }
}

/*Ordenar Datos de menor a mayor mediante método burbuja*/
void OrdenarDatos(unsigned long int v[], unsigned long int N)
{
   unsigned long int i,j;
   unsigned long int buffer;

   for(i=0; i<N-1; i++)
  {
     for(j=i+1; j<N; j++)
    {
        if(v>v[j])
       {
          buffer=v[j];
          v[j]=v;
          v=buffer;
       }
    }
  }
}

/*Muestra los datos cargados*/
void MostrarDatos(unsigned long int v[], unsigned long int N)
{
   unsigned long int i;
   
   printf("\n============================================");
   printf("\nNúmeros cargados:\n ");
   for(i=0; i<N; i++)
     printf("-%ld", v);
}

/*Principal*/
int main()
{
   unsigned long int ordenar[MAX];
   time_t inicio, fin;

   srand(time(NULL));
   CagarDatos(ordenar, MAX);
   inicio=time(NULL);
   OrdenarDatos(ordenar, MAX);
   MostrarDatos(ordenar, MAX);

/*Finalización*/
   printf("\n============================================");
   printf("\nLa cantidad de datos ordenados es: %ld", MAX);
   fin=time(NULL);
   printf("\nEl programa ha tardado: %.f segundos", difftime(fin,inicio));
   printf("\n=========================================\n\n");
   return 0;
}

ecfisa

Hola BeFree .

El problema no está en tu código, sino en el método de ordenamiento elegido (Bubble Sort), su eficiencia es de órden exponencial.

Al elevar el número de elementos a cien mil tenes que armarte de paciencia, salir de paseo...y seguramente cuando vuelvas estará el resultado. Cambia por el método: Shell Sort o por Quick Sort.

Saludos. :)

BeFree

Hola ecfisa, el tema es que el ejercicio lo tengo que hacer con ese método...pero bueno si es así me tocará seguir esperando. Gracias por responder  :)

lapras

#3
Supongo que tu código es diferente al que has copiado perque el que has copiado tiene varios fallos. Por ejemplo:

v=num;

debería ser:

v[i]=num;

El código completo corregido debería ser este:


//Secuencial - OrdenacionSectp5.c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

/*Declaración de variables globales*/
unsigned long int MAX=100000;

/*Generar datos*/
void CagarDatos(unsigned long int v[], unsigned long int N)
{
  unsigned long int i,j;
  int duplicado;
  unsigned long int num;
 
  for(i=0; i<N; i++)
  {
     num=1+rand()%N;
     duplicado=0;

      for(j=0; j<=i; j++)
     {
        if(num==v[j])
        {
           duplicado=1;
           break;
        }
     }
     if(duplicado==1)
        i--;
     else
        v[i]=num;
  }
}

/*Ordenar Datos de menor a mayor mediante método burbuja*/
void OrdenarDatos(unsigned long int v[], unsigned long int N)
{
  unsigned long int i,j;
  unsigned long int buffer;

  for(i=0; i<N-1; i++)
 {
    for(j=i+1; j<N; j++)
   {
       if(v[i]>v[j])
      {
         buffer=v[j];
         v[j]=v[i];
         v[i]=buffer;
      }
   }
 }
}

/*Muestra los datos cargados*/
void MostrarDatos(unsigned long int v[], unsigned long int N)
{
  unsigned long int i;
 
  printf("\n============================================");
  printf("\nNúmeros cargados:\n ");
  for(i=0; i<N; i++)
    printf("-%ld", v);
}

/*Principal*/
int main()
{
  unsigned long int ordenar[MAX];
  time_t inicio, fin;

  srand(time(NULL));
  CagarDatos(ordenar, MAX);
  inicio=time(NULL);
  OrdenarDatos(ordenar, MAX);
  MostrarDatos(ordenar, MAX);

/*Finalización*/
  printf("\n============================================");
  printf("\nLa cantidad de datos ordenados es: %ld", MAX);
  fin=time(NULL);
  printf("\nEl programa ha tardado: %.f segundos", difftime(fin,inicio));
  printf("\n=========================================\n\n");
  return 0;
}


Pues eso que bubblesort es lentillo.

Edit funcionar, funciona:
============================================
La cantidad de datos ordenados es: 100000
El programa ha tardado: 142 segundos
=========================================

Que conste que mi ordenador tiene una atom.

rir3760

Cita de: BeFree en 19 Junio 2013, 19:33 PM
Hola, tengo que hacer un algoritmo que ordene N números naturales generados en forma aleatoria. Tiene que ejecutarse para 1000, 10000 y 100000. Escribí un código y al ejecutarlo lo hace sin problemas para 1000 y 10000, pero para 100000 no me muestra el resultado, y no puedo hallar el error.
Ese problema puede generarse debido a la declaración del array "ordenar" en la función principal:
unsigned long int MAX=100000;

/* ... */

/*Principal*/
int main()
{
   unsigned long int ordenar[MAX];

/* ... */

Un tema relacionado donde se explica el porque es Error al ejecutar un programa en C que he compilado [Windows 8]

Un saludo
C retains the basic philosophy that programmers know what they are doing; it only requires that they state their intentions explicitly.
--
Kernighan & Ritchie, The C programming language

leosansan

Cita de: BeFree en 19 Junio 2013, 19:33 PM
Hola, tengo que hacer un algoritmo que ordene N números naturales generados en forma aleatoria. Tiene que ejecutarse para 1000, 10000 y 100000. Escribí un código y al ejecutarlo lo hace sin problemas para 1000 y 10000, pero para 100000 no me muestra el resultado, y no puedo hallar el error.


Como indicó lapras, no hay error sino "lentitud" en el proceso, tanto de generación como en el de ordenación, más en este último.

Para que veas lo que pasa he incluido un par de printf y así compruebas que incluso en el caso de 100000 está el programa "trabajando". Te lo dejo con MAX=100 porque con los printf y la limpieza de pantalla, el proceso se ralentiza enormemente:


Código (cpp) [Seleccionar]
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

/*Declaración de variables globales*/
unsigned long int MAX=100;

/*Generar datos*/
void CagarDatos(unsigned long int v[], unsigned long int N)
{
   unsigned long int i,j;
   int duplicado;
   unsigned long int num;

   for(i=0; i<N; i++)
   {
      num=1+rand()%N;
      duplicado=0;
        printf("Generando: %d",i+1);
        system("cls");
       for(j=0; j<=i; j++)
      {
         if(num==v[j])
         {
            duplicado=1;
            break;
         }
      }
      if(duplicado==1)
         i--;
      else
         v[i]=num;
   }
}

/*Ordenar Datos de menor a mayor mediante método burbuja*/
void OrdenarDatos(unsigned long int v[], unsigned long int N)
{
   unsigned long int i,j;
   unsigned long int buffer;

   for(i=0; i<N-1; i++)
  {
     for(j=i+1; j<N; j++)
    {
        if(v[i]>v[j])
       {
          printf("Ordenando: %d",i+1);
          system("cls");
          buffer=v[j];
          v[j]=v[i];
          v[i]=buffer;
       }
    }
  }
}

/*Muestra los datos cargados*/
void MostrarDatos(unsigned long int v[], unsigned long int N)
{
   unsigned long int i;

   printf("\n============================================");
   printf("\nNúmeros cargados:\n ");
   for(i=0; i<N; i++)
     printf("-%ld", v);
}

/*Principal*/
int main()
{
   unsigned long int ordenar[MAX];
   time_t inicio, fin;

   srand(time(NULL));
   CagarDatos(ordenar, MAX);
   inicio=time(NULL);
   OrdenarDatos(ordenar, MAX);
   MostrarDatos(ordenar, MAX);

/*Finalización*/
   printf("\n============================================");
   printf("\nLa cantidad de datos ordenados es: %ld", MAX);
   fin=time(NULL);
   printf("\nEl programa ha tardado: %.f segundos", difftime(fin,inicio));
   printf("\n=========================================\n\n");
   return 0;
}


Saluditos!
   


BeFree

Hola leosansan, si hice esa comprobación. Gracias por responder  :)

BeFree

Cita de: lapras en 19 Junio 2013, 23:40 PM
Supongo que tu código es diferente al que has copiado perque el que has copiado tiene varios fallos. Por ejemplo:

v=num;

debería ser:

v[i]=num;

El código completo corregido debería ser este:


//Secuencial - OrdenacionSectp5.c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

/*Declaración de variables globales*/
unsigned long int MAX=100000;

/*Generar datos*/
void CagarDatos(unsigned long int v[], unsigned long int N)
{
  unsigned long int i,j;
  int duplicado;
  unsigned long int num;
 
  for(i=0; i<N; i++)
  {
     num=1+rand()%N;
     duplicado=0;

      for(j=0; j<=i; j++)
     {
        if(num==v[j])
        {
           duplicado=1;
           break;
        }
     }
     if(duplicado==1)
        i--;
     else
        v[i]=num;
  }
}

/*Ordenar Datos de menor a mayor mediante método burbuja*/
void OrdenarDatos(unsigned long int v[], unsigned long int N)
{
  unsigned long int i,j;
  unsigned long int buffer;

  for(i=0; i<N-1; i++)
 {
    for(j=i+1; j<N; j++)
   {
       if(v[i]>v[j])
      {
         buffer=v[j];
         v[j]=v[i];
         v[i]=buffer;
      }
   }
 }
}

/*Muestra los datos cargados*/
void MostrarDatos(unsigned long int v[], unsigned long int N)
{
  unsigned long int i;
 
  printf("\n============================================");
  printf("\nNúmeros cargados:\n ");
  for(i=0; i<N; i++)
    printf("-%ld", v);
}

/*Principal*/
int main()
{
  unsigned long int ordenar[MAX];
  time_t inicio, fin;

  srand(time(NULL));
  CagarDatos(ordenar, MAX);
  inicio=time(NULL);
  OrdenarDatos(ordenar, MAX);
  MostrarDatos(ordenar, MAX);

/*Finalización*/
  printf("\n============================================");
  printf("\nLa cantidad de datos ordenados es: %ld", MAX);
  fin=time(NULL);
  printf("\nEl programa ha tardado: %.f segundos", difftime(fin,inicio));
  printf("\n=========================================\n\n");
  return 0;
}


Pues eso que bubblesort es lentillo.

Edit funcionar, funciona:
============================================
La cantidad de datos ordenados es: 100000
El programa ha tardado: 142 segundos
=========================================

Que conste que mi ordenador tiene una atom.

///////////////
A mi me tardo más tiempo casi 6 min, y tengo un i5, pero supongo que tiene que ver con la virtualización!! Gracias por la ayuda

BeFree

Cita de: BeFree en 19 Junio 2013, 19:33 PM
Hola, tengo que hacer un algoritmo que ordene N números naturales generados en forma aleatoria. Tiene que ejecutarse para 1000, 10000 y 100000. Escribí un código y al ejecutarlo lo hace sin problemas para 1000 y 10000, pero para 100000 no me muestra el resultado, y no puedo hallar el error.
Si me pueden ayudar se los agradecería. Ah trabajo en un entorno linux, que es una virtualización sobre window.

Acá les dejo el código que escribí:

//Secuencial - OrdenacionSectp5.c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

/*Declaración de variables globales*/
unsigned long int MAX=100000;

/*Generar datos*/
void CagarDatos(unsigned long int v[], unsigned long int N)
{
   unsigned long int i,j;
   int duplicado;
   unsigned long int num;
 
   for(i=0; i<N; i++)
   {
      num=1+rand()%N;
      duplicado=0;

       for(j=0; j<=i; j++)
      {
         if(num==v[j])
         {
            duplicado=1;
            break;
         }
      }
      if(duplicado==1)
         i--;
      else
         v=num;
   }
}

/*Ordenar Datos de menor a mayor mediante método burbuja*/
void OrdenarDatos(unsigned long int v[], unsigned long int N)
{
   unsigned long int i,j;
   unsigned long int buffer;

   for(i=0; i<N-1; i++)
  {
     for(j=i+1; j<N; j++)
    {
        if(v>v[j])
       {
          buffer=v[j];
          v[j]=v;
          v=buffer;
       }
    }
  }
}

/*Muestra los datos cargados*/
void MostrarDatos(unsigned long int v[], unsigned long int N)
{
   unsigned long int i;
   
   printf("\n============================================");
   printf("\nNúmeros cargados:\n ");
   for(i=0; i<N; i++)
     printf("-%ld", v);
}

/*Principal*/
int main()
{
   unsigned long int ordenar[MAX];
   time_t inicio, fin;

   srand(time(NULL));
   CagarDatos(ordenar, MAX);
   inicio=time(NULL);
   OrdenarDatos(ordenar, MAX);
   MostrarDatos(ordenar, MAX);

/*Finalización*/
   printf("\n============================================");
   printf("\nLa cantidad de datos ordenados es: %ld", MAX);
   fin=time(NULL);
   printf("\nEl programa ha tardado: %.f segundos", difftime(fin,inicio));
   printf("\n=========================================\n\n");
   return 0;
}

------------------------------------------------------------------------------------------------

Hola, pude resolver el problema...Ahora tengo otro, me pide que los números desordenados generados en forma aleatoria se guarden en un archivo de texto...y estuve dándole vueltas al asunto y no lo pude resolver, a ver si alguien me puede dar una mano!!  :)