-1

I'm trying to implement the merge sort in c, but I have a segmentation fault 11, and I don't get why.

void trieFusion(int *t, int d, int f){
    if (f==d)
        return;
    
    int m=(f-d)/2+d;
    trieFusion(t, d, m);
    trieFusion(t, m+1, f);
    
    int tmp[(f-d+1)];
    int pg = d;    
    int pd = m + 1; 

    for(int i = d; i <= f; i++) {
        if(pg == m + 1) { 
            tmp[i] = t[pd];
            pd++;
        }
        else if (pd == f + 1) { 
            tmp[i] = t[pg];
            pg++;
        }
        else if (t[pg] < t[pd]) { 
            tmp[i] = t[pg];
            pg++;
        }
        else{  
            tmp[i] = t[pd];
            pd++;
        }
    }
    for(int i = d; i <= f; i++) { 
        t[i] = tmp[i];
    }
}

The main

int main(){
    int t[] = {2,4,2,4,6,7,2,3,5,4};
    int n=10;
    afficheTableau(t, n);

    majoritaireNLogN(t, n);

    afficheTableau(t,n);
    return EXIT_SUCCESS;
}

The function that calls my merge sort

int majoritaireNLogN(int* t, int n){
        n--;
        trieFusion(t, 0, n);
        return t[0];
}

If I run my code, I can sort the first half of a table without a problem, but the segmentation fault is coming from the second half of a table.

I don't find where this problem is coming from.

Ken White
  • 123,280
  • 14
  • 225
  • 444
lysander051
  • 1
  • 3
  • Begin by using a [*debugger*](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) to catch the crash when it happens, and locate where it happens in *your* code. Then also inspect the values of all involved variables. For example, will `f - d + 1` be positive? Are there any indexing out of bounds? – Some programmer dude Oct 08 '22 at 17:25
  • I haven't looked at your calculations in detail, but if it happened to be the case that the condition `(f == d)` is never true in some branch of the subdivided recursion space, then the recursion would run away and crash. – Kaz Oct 08 '22 at 18:00
  • Your `tmp` array goes from `[0]` to `[f-d]`. But your loop is indexing it from `[d]` to `[f]`. You want a `for (i = 0; ...`. – Kaz Oct 08 '22 at 18:03
  • If the second call is causing a segfault, we'll need to see the code that initially invokes `trieFusion` (e.g. `main`). And, the definition of the array that is passed (e.g. it may be of insufficient length). Please _edit_ your _question_ and post this in a code block. – Craig Estey Oct 08 '22 at 18:19
  • If I remove every statement in my first loop I don't have the problem anymore and my recursive is going through my table – lysander051 Oct 08 '22 at 18:22
  • I edit my post with the main and the calling to merge sort function – lysander051 Oct 08 '22 at 18:28

1 Answers1

0

Problem most likely lies in this loop (and the same loop below).

for(int i = d; i <= f; i++)

to fix it, replace all instances of that with this:

for(int i = d; i < f; i++)

In C and most languages, arrays are 0 indexed, meaning the first element is in the array[0] index and the last element, let's say our array has 10 elements, is on the array[9] index. So, in your case, you pass in an array with 10 elements, and probably try to index a value in the array that isn't defined; i.e. look for an 11th element, which is not allocated in memory.

When you say <= it means that the loop will stop only when d is greater than f, and if f is greater than 9 (which it is since it'll be 10), the index of the last element, your code will try to access areas in memory that are not allocated, so your code doesn't have access to it. This will cause a segmentation fault. Here is a quick guide to iterating through loops.

ProgrammerPerson123
  • 61
  • 5