Segmentation fault in using recursive selection sort in C language

Question

I have i have wrote a C program. It should use recursive selection sort but segmentation fault occurs for big input (10000 or more). Debugger says that the segfault happens in findim function, but it's almost impossible to me to find out why it happens, because the findmin function too is recursive and I can't imagine all the operations made by computer on an input of 10000 numbers.

If you're wondering what inputType is, it's to decide the order of values in the array. The values respectevely means ORDERLY, ALMOST ORDERLY, INVERSELY ORDERED, RANDOM.

That's all the program I wrote.

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

#define DIM_VEC 6
#define MAX_RAND 100

typedef enum {
    ORDINATO, QUASI_ORDINATO, INV_ORDINATO, CASUALE
} inputType;

//Funzione genera_array(…)
int *generaArray(int dimensione, inputType tipo_schema);

void swap(int *a, int *b);

//E2_1: Selection Sort ricorsivo con interi
void selectionSortRec(int A[], int dimA, int start);
int findmin(int A[], int minpos, int start, int dim);



int main() {
    setvbuf(stdout, NULL, _IONBF, 0);
    int ord, dim;
    int *array = NULL;
    int N[DIM_VEC] = {100, 1000, 10000, 100000, 200000, 500000};
    double tempo;
    srand(time(NULL));

    printf("\nScegli l'ordine dell'array "
           "\n0 - ORDINATO, 1 - QUASI_ORDINATO, 2 - INV_ORDINATO, 3 - CASUALE");
    scanf("%d", &ord);
    if(ord < 0 || ord > 3)
        ord = 0;

    printf("\nScegliere la dimensione dell'array ");
    for(int i = 0; i < DIM_VEC; i++) {
        printf("\n%d -- %d", i, N[i]);
    }
    scanf("%d", &dim);
    if(dim < 0 || dim > 5)
        dim = 0;

    array = generaArray(N[dim], ord);

    tempo = clock();
    selectionSortRec(array, N[dim], 0);
    tempo = (clock() - tempo) / CLOCKS_PER_SEC;
    printf("\nTempo impiegato: %lf", tempo);

    free(array);

    return 0;
}

//Funzione genera_array(…)
int *generaArray(int dimensione, inputType tipo_schema) {
    int *a = calloc(dimensione, sizeof(int));
    int j;

    switch (tipo_schema) {
        case ORDINATO:
            for(int i = 0; i < dimensione; i++)
                a[i] = i;
            break;
        case QUASI_ORDINATO:
            for(int i = 0; i < dimensione / 2; i++) {
                a[i] = i;
            }
            for(int i = dimensione /2; i < dimensione; i++) {
                a[i] = rand() % MAX_RAND;
            }
            break;
        case INV_ORDINATO:
            j = dimensione;
            for(int i = 0; i < dimensione; i++) {
                a[i] = j;
                j--;
            }
            break;
        case CASUALE:
            for(int i = 0; i < dimensione; i++) {
                a[i] = rand() % MAX_RAND;
            }
            break;
    }

    return a;

}


//E2_1: Selection Sort ricorsivo con interi
void selectionSortRec(int A[], int dimA, int start) {
    int minIndex;

    if (start >= dimA - 1)
        return;

    minIndex = findmin(A, start, start +1, dimA);


    swap(&A[minIndex], &A[start]);
    selectionSortRec(A, dimA, start+1);
}
int findmin(int A[], int minpos, int start, int dim) {

    if (start == dim)
        return minpos;

    if (A[start] < A[minpos])
        minpos = start;
    return findmin(A, minpos, start + 1, dim);

}

void swap(int *a, int *b) {
    int aux = *a;
    *a = *b;
    *b = aux;
}

I tried to not use swap function and to verify if array generation function worked, but both of them seems to be ok, because on smaller input they work and i tried to print all of the elements of array and it was ok, but maybe I'm forgetting some aspect.

Welcome to Stack Overflow, what you have there is a stack overflow. For an input of size 10000 both findmin and selectionSortRec will recurse 10000 deep. Stack space is limited and each nested call eats a bit of it, you can't really do that for arbitrarily large inputs. — teapot418
– teapot418, Commented Jun 1, 2024 at 13:02
Oh I didn't know that, thank you very much I was going crazy — Giuseppe Guerrini
– Giuseppe Guerrini, Commented Jun 1, 2024 at 13:04
Incidentally, any tail-recursive function, like the one you have here, can trivially be converted into a loop. — 500 - Internal Server Error
– 500 - Internal Server Error, Commented Jun 1, 2024 at 21:22

ticktalk · Accepted Answer · 2024-06-01 18:35:59Z

You could try changing the stack size and see if you can get any further with your recursion, but as others have warned ... ultimately you'll run out of it at some point.

altering stack size example below (on linux mint 20.x, gcc 9.4.0)

#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <sys/resource.h>

int main (int argc, char **argv)
{
    struct rlimit stackSz;

    if ( 0 == getrlimit(RLIMIT_STACK, &stackSz) )
    {
        fprintf(stderr, "current: rl.rlim_cur == %lu rl.rlim_max == %lu\n", stackSz.rlim_cur, stackSz.rlim_max );

        stackSz.rlim_cur *= 2; // double stack size - for example ....
        setrlimit(RLIMIT_STACK, &stackSz);
        if (0 != setrlimit(RLIMIT_STACK, &stackSz) )
           fprintf(stderr, "ERROR: setrlimit error = %s\n", strerror(errno) );
        else
           fprintf(stderr, "updated: rl.rlim_cur == %lu rl.rlim_max == %lu\n", stackSz.rlim_cur, stackSz.rlim_max );
    }
    else
       fprintf(stderr, "ERROR: getrlimit error = %s\n", strerror(errno) );

    return 0;
}

./rlimit 
current: rl.rlim_cur == 8388608 rl.rlim_max == 18446744073709551615
updated: rl.rlim_cur == 16777216 rl.rlim_max == 18446744073709551615

Collectives™ on Stack Overflow

Segmentation fault in using recursive selection sort in C language

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related