I have to measure execution time of quicksort on arrays in ascending, descending and random order of 10.000, 20.000, ...., 100.000 integers. With random arrays it works perfectly for all sizes, however with descending and ascending arrays it doesn't work for sizes bigger than a certain number, in my case it works with 30.590 but it doesn't with 30.591 (my friend has the same issue but it's a different number, between 30.000 and 40.000 too). The arrays are read from a file, but I'm quite sure the code for getting the arrays works well (I've also tried creating the arrays myself and I have the same issue). I've also used those files for bubblesort and mergesort and I didn't have any issues.

Here's my code (sorry for the code formatting hehe, it's my first post)

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


void get_array(FILE *fp, int len, int vector[]);
void write_array(FILE *fp, int vector[],int len);
void quicksort(int v[], int i, int d);
int pivote(int primero, int ultimo, int v[]);

int main(void)
{
    FILE *fp;
    int *pv, len, i, j;
    clock_t start;
    
    for (i=1;i<11;i  )
    {   len = i*10000;
        //len = 30590; //this works, 30591 doesn't
        int vector[len];
        clock_t start;
        

    //random
        fp = fopen("aleatorio.txt","r");
        get_array(fp,len,vector);
        start = clock();
        quicksort(0, len-1,vector);
        printf("\nRandom n=%d secs: %f\n", len, (float)(clock() - start)/CLOCKS_PER_SEC);
        fclose(fp);
        fp = fopen("aleatorio_output.txt","w");
        write_array(fp, vector, len);
        fclose(fp);
        

        //descendente
        fp = fopen("descendente.txt","r");
        get_array(fp,len,vector);
        start = clock();
        quicksort(vector,0,len-1);  
        printf("Descendente n=%d secs: %f\n", len, (float)(clock() - start)/CLOCKS_PER_SEC);
        fclose(fp);
        fp = fopen("descendente_output.txt","w");
        write_array(fp, vector, len);
        fclose(fp);



        //ascendente
        fp = fopen("ascendente.txt","r");
    get_array(fp,len,vector);
        fclose(fp);
        start = clock();
        printf("Ascendente n=%d secs: %f\n", len, (float)(clock() - start)/CLOCKS_PER_SEC);
        fp = fopen("ascendente_output.txt","w");
        write_array(fp, vector,  len);
        fclose(fp);
    }
}


void quicksort(int v[], int izquierda, int derecha)
{
    int p;
    if (derecha>izquierda)
    {
        p = pivote(izquierda,derecha,v);
        quicksort(v,izquierda, p-1);
        quicksort(v,p 1, derecha);
    }
}


int pivote (int primero, int ultimo, int v[])
{
    int pivote = v[primero], i = primero, j = ultimo 1, aux;
    while (i<j) //hasta que se crucen los indices
    {
        do{
        i  ;}while (v[i]<pivote && i<ultimo); 

        do{
        j--;}while (v[j]>pivote);
            
        if(i<j)
        {
            aux = v[i];
            v[i] = v[j];
            v[j] = aux;
        }
    }
    v[primero] = v[j];
    v[j] = pivote;
    return j;
}

//devuelve un vector de enteros extraido de un fichero
void get_array(FILE *fp,int len, int vector[]) 
{
    int i=0;
    while (!feof(fp) && i<len)
    {
        fscanf(fp,"%d",&vector[i]);
        i  ;
    }
}

//escribe los numeros de un vector de enteros en un fichero
void write_array(FILE *fp, int vector[],int len)
{
    int i;
    for (i=0; i<len; i  )
        fprintf(fp,"%d\n",vector[i]);
}

CodePudding user response：

Picking a random pivot (as ggorlen has suggested) has solved the issue