Problema con eficiencia QUICKSORT

[extremoo]

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:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
 
void swap(int *a, int *b)
{
  int t=*a; *a=*b; *b=t;
}
void quicksort(int arr[], int beg, int end)
{
  if (end > beg + 1)
  {
    int piv = arr[beg], l = beg + 1, r = end;
    while (l < r)
    {
      if (arr[l] >= piv)
        l++;
      else
        swap(&arr[l], &arr[--r]);
    }
    swap(&arr[--l], &arr[beg]);
    quicksort(arr, beg, l);
    quicksort(arr, r, end);
  }
}
 
 
 
int main()
{
 
  float total,inicio, final;
  inicio=clock();
  FILE *ARCH, *ARCHI;
 
    int N;
    ARCH = fopen("aleatorio.txt","r"); 
    fscanf(ARCH,"%i", &N);
    int d[N], a;
 
    a=0;
    for(a=0;a<N;a++)
    {
      fscanf(ARCH,"%i", &d[a]);
    }
 
    ARCHI = fopen("quick_dec.txt","w");
 
  int length;
  length=N;
 
  int i;
  for(i=0;i<length;i++)
    {
      quicksort(d, 0, length);
      fprintf(ARCHI,"%i \n",d[i]);
    }
 
 
  final=clock();
  total=(final-inicio)/(double) CLOCKS_PER_SEC;
  printf("Tiempo de ejecucion : %f [s]\n",total);
 
  fclose(ARCH);  
  fclose(ARCHI);
return 0;
}
 

[sam90]

Lo primero de todo esa implementacion del Quicksort funciona?

Lo segundo no exiiste un teorema que diga que simpre y para todos los casos el tiempo de de quicksort va ser menor que el de Bubble sort.

Lo que si se pueden asegurar cotas para cada uno de ellos. Y ahi si resulta menor la cota de quicksort que la del bubblesort.

Pero cual es el problema, uno de los peores casos para el quicksort, tener la lista ordenada, para el bubble sort es el mejor ya que esta ordenado. Entonces la cantidad de intercambios que realizan es muy diferente.
Fiajte que el peor caso del quicksort es de orden n cuadrado. Osea lo mismo que un Bubblesort

Por eso te digo que te fijes bien como estan ordenados esos elementos. y que realices muchos intentos con distintos elementos para ver si anda que resultados optenes. Posiblemente tu array esta muy ordenado.

[extremoo]

Si la implementacion compila y arroja la lista tanto ordenada, el archivo que leo es un archivo aleatorio por ende esta desordenado quiza ese es el problema esta mas ordenado que desordenado por eso se demora tanto, pero de ser asi mergesort que tambien tengo implementado su orden es nlogn para ambos casos y aun asi tambien se demora mucho mas que bubblesort

[sam90]

Tambien depende mucho de las implementaciones. En la complejidad del merge-sort no se tiene en cuenta la creacion de dos array mas para poder ordenar de forma mas comodo.

Ponele una variable global que cuenta los intercambios y las comparaciones que hace el programa. En mi facu me dieron ese ejercicio para ver las diferencias.

[CalgaryCorpus]

Yo creo que la linea 56 de tu codigo, puesta al interior de un ciclo, hace que quicksort, en vez de ser n log n, sea n^2 log n. mucho peor que bubblesort y que el mismo quicksort, si estuviera fuera del ciclo.

[sam90]

No vi eso..... perdon eso hace desastre en el codigo....

en el primer caso sopungamos que es n log n.....para el proximo el array ya esta ordenado asi que desde la segunda hasta el fin siempre va a tarde n^2...asi que debera quedar en algo asi como un: n^3 log n

que realmente es malo.
quicksort(d, 0, length);

Código C++:

for(i=0;i<length;i++)
      fprintf(ARCHI,"%i \n",d[i]);
 

A demas por las dudas yo solo tomaria el tiempo que tarda en correr el algoritmo, no en leer y escribit los archivos...uno nunca sabe puede ocurrir y que se demore mas justo en uno...se que son micro segundo pero todo puede pasar.

[extremoo]

toda la razon ahora si pude ejecutar el programa con normalidad gracias a ambos por la ayuda.

[CalgaryCorpus]

Iniciado por sam90

en el primer caso sopungamos que es n log n.....para el proximo el array ya esta ordenado asi que desde la segunda hasta el fin siempre va a tarde n^2...asi que debera quedar en algo asi como un: n^3 log n

Si consideramos lo que indicas, lo que es en mi opinion correcto, es decir que la primera vez deja el arreglo ordenado y luego es el peor de los casos, entonces queda

n log n + (n-1)*n^2, i.e. esta acotado por n^3. No es tan grande como n^3 log n.

[sam90]

De todas formas en grande!