Ver Mensaje Individual
  #1 (permalink)  
Antiguo 05/05/2010, 19:10
Avatar de extremoo
extremoo
 
Fecha de Ingreso: abril-2009
Mensajes: 54
Antigüedad: 15 años, 7 meses
Puntos: 0
Problema con eficiencia QUICKSORT

hola a todos, les comento que hice un ejercicio con el metodo QUICKSORT con el fin de reducir el tiempo para una lectura de entrada de 1000 datos enteros, el problema es que me esta arrojando mas tiempo que bubblesort cosa que no deberia ser, , alguien me puede ayudar a hacer mas optimo este algoritmo ya que por naturaleza es mas rapido que el mismo bubblesort, saludos

Código C:
Ver original
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<time.h>
  4. #include<string.h>
  5.  
  6. void swap(int *a, int *b)
  7. {
  8.   int t=*a; *a=*b; *b=t;
  9. }
  10. void quicksort(int arr[], int beg, int end)
  11. {
  12.   if (end > beg + 1)
  13.   {
  14.     int piv = arr[beg], l = beg + 1, r = end;
  15.     while (l < r)
  16.     {
  17.       if (arr[l] >= piv)
  18.         l++;
  19.       else
  20.         swap(&arr[l], &arr[--r]);
  21.     }
  22.     swap(&arr[--l], &arr[beg]);
  23.     quicksort(arr, beg, l);
  24.     quicksort(arr, r, end);
  25.   }
  26. }
  27.  
  28.  
  29.  
  30. int main()
  31. {
  32.  
  33.   float total,inicio, final;
  34.   inicio=clock();
  35.   FILE *ARCH, *ARCHI;
  36.  
  37.     int N;
  38.     ARCH = fopen("aleatorio.txt","r");
  39.     fscanf(ARCH,"%i", &N);
  40.     int d[N], a;
  41.  
  42.     a=0;
  43.     for(a=0;a<N;a++)
  44.     {
  45.       fscanf(ARCH,"%i", &d[a]);
  46.     }
  47.  
  48.     ARCHI = fopen("quick_dec.txt","w");
  49.  
  50.   int length;
  51.   length=N;
  52.  
  53.   int i;
  54.   for(i=0;i<length;i++)
  55.     {
  56.       quicksort(d, 0, length);
  57.       fprintf(ARCHI,"%i \n",d[i]);
  58.     }
  59.  
  60.  
  61.   final=clock();
  62.   total=(final-inicio)/(double) CLOCKS_PER_SEC;
  63.   printf("Tiempo de ejecucion : %f [s]\n",total);
  64.  
  65.   fclose(ARCH);  
  66.   fclose(ARCHI);
  67. return 0;
  68. }