How to pass an integer file to a C vector?

Question

I have a problem when passing data from my file (integer numbers) to the vector.

The purpose of the program below is to check the performance of the sorting algorithms (Mergesort, Bubble Sort, Quicksort) but whenever I put a number of data above 42, the locking program gives crash.

Below are the algorithms to generate the.txt file and the other to sort the vector respectively.

PS: The code is a bit messy, sorry.

TXT Generator Code:

    #include <stdio.h>
    #include <time.h>
    #include <conio.h>
    #include <stdlib.h>
    int main (void)
    {
        FILE *x;
        x = fopen("ex.txt","wt");
        if(x == NULL)
        {
            printf("Erro");
            return(-1);
        }
        int i,n,y;
        printf("Quantos nums serao gerados? ");
        scanf("%d",&n);
        system("cls");
        clock_t inicio = clock(); 
        for(i=0; i<n; ++i){
            y= (rand()%100);    
            fprintf(x,"%d\n", y);
            //printf("%d\n",y);
        }    
        fclose(x);
        clock_t fim = clock();
        double gasto = difftime(fim,inicio)/CLOCKS_PER_SEC;  
        printf("\ntempo gasto: %f segundos\n", gasto);
        return(0);
    }

Vector ordering code:

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

int qtd;                    
void quicksort(int *P, int tam);
void mergesort(int p1[],int i,int j);
void merge(int p2[],int i1,int j1,int i2,int j2);

void mergesort(int p1[],int i,int j)
{
    clock_t inicio = clock();
    int meio;     
    if(i<j)
    {
        meio=(i+j)/2;
        mergesort(p1,i,meio);       
        mergesort(p1,meio+1,j);    
        merge(p1,i,meio,meio+1,j);
    }
    clock_t fim = clock();
    double gasto = difftime(fim,inicio)/CLOCKS_PER_SEC;  
    printf("\ntempo gasto: %f segundos\n", gasto);
}

void merge(int p2[],int i1,int j1,int i2,int j2)
{
    int aux[qtd];
    int i,j,k;
    i=i1; 
    j=i2; 
    k=0;   
    while(i<=j1 && j<=j2)
    {
        if(p2[i]<p2[j])
            aux[k++]=p2[i++];
        else
            aux[k++]=p2[j++];
    }  
    while(i<=j1)
        aux[k++]=p2[i++];        
    while(j<=j2) 
        aux[k++]=p2[j++];
    for(i=i1,j=0;i<=j2;i++,j++)
        p2[i]=aux[j];
}

void quicksort(int *P, int tam) {
    clock_t inicio = clock(); 
    if (tam < 2) {
        return;
    }
    int pivo = P[tam/2];
    int i3, j3;
    for (i3 = 0, j3 = tam - 1; ; i3++, j3--) {
        while (P[i3] < pivo){
            i3++;
        }
        while (P[j3] > pivo){
            j3--;
        }
        if (i3 >= j3) {
            break;
        }
        int aux2 = P[i3];
        P[i3] = P[j3];
        P[j3] = aux2;
    }
    quicksort(P, i3);
    quicksort(P + i3, tam - i3);
    clock_t fim = clock();
    double gasto = difftime(fim,inicio)/CLOCKS_PER_SEC;  
    printf("\ntempo gasto: %f segundos\n", gasto);
}

int main () {

    FILE *x;   
    char c,arq[100];
    int i,y,op,co;
    int p[qtd]; 

    printf("Digite o nome do arquivo: ");
    gets(arq);
    system("cls");

    x = fopen(arq,"r");
    for (c = getc(x); c != EOF; c = getc(x))
        if (c == '\n') 
            qtd = qtd + 1;
    fclose(x);
    x = fopen(arq,"r");        

    fseek(x, 0, SEEK_SET);
    while(!feof(x)){
        for(i=0;i<qtd;i++){
            fscanf(x,"%d",&y);
            p[i]=y;
        }
    }

    fclose(x);  
    clock_t inicio = clock();

    do{
        printf("Menu\n");
        printf("1. Bubblesort\n");
        printf("2. Mergesort\n");
        printf("3. Quicksort\n");
        scanf("%d",&op);
        system("cls");
        clock_t fim = clock();
        double gasto = difftime(fim,inicio)/CLOCKS_PER_SEC;  

        switch(op){    
        case 1:
            int aux, k, j;          
            for(k=qtd-2;k>=0;k--){
              for(j=0;j<=k;j++){
                if(p[j]>p[j+1] ){
                   aux=p[j];
                   p[j]=p[j+1];
                   p[j+1]=aux;
                }
              }
            }       
            printf("Vetor ordenado: \n");
            for(k=0;k<qtd;k++){
                printf("%d\n",p[k]);
            } 
            printf("\ntempo gasto: %f segundos\n", gasto);       
            system("pause");
            system("cls");
            return 0;                         
            break;
        case 2:
            mergesort(p,0,qtd-1);   
            printf("\nVetor Ordenado: \n");
            for(i=0;i<qtd;i++){
                printf("%d\n",p[i]);
            }
            system("pause");
            system("cls");
            return 0;
            break;
        case 3:
            quicksort(p,qtd);
            printf("Vetor ordenado: \n");
            for (co = 0; co < qtd; co++) {
                printf("%d\n", p[co]);
            }                       
            system("pause");
            system("cls");
            return 0;
            break;
        default:
            printf("Entrada invalida!\n");
            printf("\ntempo gasto: %f segundos\n", gasto);     
            system("pause");
            system("cls");
            return 0;
            break;
        }

    }while(op != 4);
    return 0;
}

Answer 1

The problem of your question is caused by this line, within the main function:

int p[qtd]; 

The point is that C cannot dynamically calculate the size of vectors - you have to put a fixed size to compile the program. In case you still try to use the value of Qtd BEFORE to calculate its value, so even if it were a dynamic language like Javascript, the value of "Qtd" would not be defined in that statement. The fact is that the compiler simply creates an unknown-sized vector in that statement - and, by chance, when you exceed 42 numbers in the vector, the thing explodes. But it could be happening with 2 numbers, or 10000. Another answer here suggests changing the statement of p to a point where qtd is set - but this does not work in C - it just lucky the allocated vector is higher there. The value in declaration declarations of type int p[NUMERO] is used when the program is compiled, and is already fixed when it is executed.

The correct way to deal with this is with dynamic memory allocation: you declare your variable p only as an integer vector:

int p[];

(or int *p; - will be the same thing) After knowing the amount of elements in the vector, you allocate a region in memory calling malloc. Test if the malloc return is not NULL. (In general, answers here in the O.R. skip this test, but it is vital in systems that go into production and should be part of the way of thinking of anyone who programs in C).

malloc is defined as "stdlib. h", which has already been included, so after you go through the file and know the value of Qtd, you can add these lines to reserve space for your data:

...
int qtd;
int *p;
// parte do programa para saber o valor de qtd
...
p = malloc(sizeof(int) * qtd);
if (p == NULL) {
    printf("Falha ao alocar memória.\n");
    exit(1);
}
// Pode continuar a execução do seu codigo original aqui
...

This will eliminate your error - I have not checked other issues. A few tips however:

Modern Pcs run billions of operations per second - and the C language uses this potential at full speed. This means that sorting vectors with 100 numbers is something that will be done in a few milliseconds, maybe less than 1. So if the program works, it can increase the numbers used and file size for better valroe sbem - of the order of 100000 numbers - then maybe you’ll see some difference.

Another thing, avoid using the so-called "system": this runs ANOTHER WHOLE program outside of your program, and is not part of the C language. At some point college teachers in Brazil started using system("pause"); so that students who did not know how to use the terminal could look at the output of their programs, but this practice is horrible.
To wait a key, you can use the gets() same (but the key has to be ENTER) - and to delete the screen, print a series of " n"s - (that’s what CLS does - only it’s another whole program just to do it): for (int i=0; i< 80; i++) printf("\r\n"); .

Use the system for these things, in addition to the machine’s features (which will still seem instantaneous in code of this type, despite being on the order of 100,000 to 1 million times more memory and executed instructions), makes your program specific for windows - while without it, the same program can work on Mac, Linux, Unix servers on the internet, etc...

Answer 2

Follow your changed code with some suggestions:

void quicksort(int *P, int tam);
void mergesort(int p1[],int i, int j);
void merge(int p2[],int i1,int j1,int i2,int j2);

void mergesort(int p1[],int i, int j)
{
    clock_t inicio = clock();
    int meio;     
    if(i<j)
    {
        meio=(i+j)/2;
        mergesort(p1,i,meio);       
        mergesort(p1,meio+1,j);    
        merge(p1,i,meio,meio+1,j);
    }
    clock_t fim = clock();
    double gasto = difftime(fim,inicio)/CLOCKS_PER_SEC;  
    printf("\ntempo gasto: %f segundos\n", gasto);
}

void merge(int p2[],int i1,int j1,int i2,int j2)
{
    int aux[j2];
    int i,j,k;
    i=i1; 
    j=i2; 
    k=0;   
    while(i<=j1 && j<=j2)
    {
        if(p2[i]<p2[j])
            aux[k++]=p2[i++];
        else
            aux[k++]=p2[j++];
    }  
    while(i<=j1)
        aux[k++]=p2[i++];        
    while(j<=j2) 
        aux[k++]=p2[j++];
    for(i=i1,j=0;i<=j2;i++,j++)
        p2[i]=aux[j];
}

void quicksort(int *P, int tam) {
    clock_t inicio = clock(); 
    if (tam < 2) {
        return;
    }
    int pivo = P[tam/2];
    int i3, j3;
    for (i3 = 0, j3 = tam - 1; ; i3++, j3--) {
        while (P[i3] < pivo){
            i3++;
        }
        while (P[j3] > pivo){
            j3--;
        }
        if (i3 >= j3) {
            break;
        }
        int aux2 = P[i3];
        P[i3] = P[j3];
        P[j3] = aux2;
    }
    quicksort(P, i3);
    quicksort(P + i3, tam - i3);
    clock_t fim = clock();
    double gasto = difftime(fim,inicio)/CLOCKS_PER_SEC;  
    printf("\ntempo gasto: %f segundos\n", gasto);
}

int main () {

    FILE *x;   
    char c,arq[100];
    int i,op,co;    
    int qtd; //não é uma boa prática o uso de variáveis globais                    

    printf("Digite o nome do arquivo: ");
    scanf("%s", arq);//alterei para não usar fgets
    system("cls");

    x = fopen(arq,"r"); //deves sempre testar se não veio NULL o x
    for (c = getc(x); c != EOF; c = getc(x))
        if (c == '\n') 
            qtd = qtd + 1;
    fclose(x);

    int p[qtd]; 
    x = fopen(arq,"r"); //deveria testar se não é NULL o valor de x        
    rewind(x); //se o objetivo é apenas voltar ao início, usa o rewind

    while(x != NULL && !feof(x)){ //o for interno estava errado
          fscanf(x,"%d",&p[i]); //desta forma, ele irá ler todos
          i++;
    }

    fclose(x);  
    clock_t inicio = clock();

    do{
        printf("Menu\n");
        printf("1. Bubblesort\n");
        printf("2. Mergesort\n");
        printf("3. Quicksort\n");
        scanf("%d",&op);
        system("cls");
        clock_t fim = clock();
        double gasto = difftime(fim,inicio)/CLOCKS_PER_SEC;  
        int aux, k, j;    

        switch(op){    
        case 1:
            for(k=qtd-2;k>=0;k--){
              for(j=0;j<=k;j++){
                if(p[j]>p[j+1] ){
                   aux=p[j];
                   p[j]=p[j+1];
                   p[j+1]=aux;
                }
              }
            }       
            printf("Vetor ordenado: \n");
            for(k=0;k<qtd;k++){
                printf("%d\n",p[k]);
            } 
            printf("\ntempo gasto: %f segundos\n", gasto);       
            break;
        case 2:
            mergesort(p,0,qtd-1);   
            printf("\nVetor Ordenado: \n");
            for(i=0;i<qtd;i++){
                printf("%d\n",p[i]);
            }
            break;
        case 3:
            quicksort(p,qtd);
            printf("Vetor ordenado: \n");
            for (co = 0; co < qtd; co++) {
                printf("%d\n", p[co]);
            }                       
            break;
        default:
            printf("Entrada invalida!\n");
            printf("\ntempo gasto: %f segundos\n", gasto);                 
        } //retirei o return 0 de dentro do switch
        system("pause"); //aqui vão as instruções em comum dos cases
        system("cls");
    }while(op != 4);
    return 0;
}