Recursive selection sort outputting incorrect values in C

Question

I've been working on a recursive version of selection sort. MaxInd worked fine with one iteration of SelectionSort, but once I made SelectionSort recursive, MaxInd started to produce incorrect values after the first iteration of SelectionSort, which caused my code to swap incorrect values. I'm not sure why it's doing this.

#include <stdio.h>

int MaxInd(int arr[], int i, int len, int max, int index){
    if (arr[i]>max){
        max=arr[i];
        index=i;
    }
    if(i==len)
        return index;

    index = MaxInd(arr,i+1,len,max,index);
    return index;
}
void SelectionSort(int arr[], int len){
    int index=0; int max=0; int i=0; int temp=0; int num=0;
    if(len<0){
        for(int j=0; j<6; j++)
            printf("array=%d\n",arr[j]);
            return;
    }
    num = MaxInd(arr, i, len, max, index);
    if(len>0){
        temp=arr[len-1];
        arr[len-1]=arr[num];
        arr[num]=temp;
    for(int j=0; j<6; j++)
            printf("%d ",arr[j]);
        printf("\n");
    }
    return SelectionSort(arr,len-1);
}
int main(void){
    int arr[6] = {1,4,3,7,9,2};
    int len=sizeof(arr)/sizeof(arr[0]);
    SelectionSort(arr, len);
}

Answer 1

The correct way to handle the return statement would be to write it like this

return SelectionSort(arr,len-1);

You are supposed to return an int from the function - but you didn't put any return statement - and then again you tried to use it's value. This is undefined behavior.

That will make sure - after it hits the bottom of recursive calls it will return the value returned correctly so that successive parent functions get it. Don't forget that return just terminates the execution of a function and returns control to the calling function.

Also note that - sorting functions are generally made to not return anything (void return type)- but in this case after all that of work, you are returning something that is nothing other than 0. So it leaves us with the question - is it the correct value you are returning?

Also your maxInd function would return 6 in the first call - and it is wrong. It can't be a valid index in a length 6 array in c as array indexing is 0-based on c. Otherwise you are invoking Undefined Behavior on your code. Correct order would be to - first check whether it (the index) is out of bound, if it is, then on that case return the index otherwise go looking for it via making successive calls.

if(i == len)
    return index;

if (arr[i] > max){
    max = arr[i];
    index = i;
}

Just correcting the code - gives a correct result.(Removing undefined behavior from your code) (By correct result I mean it sorts the array but you are least concerned about it). Here.

Also as Jonathan Leffler mentioned, the indentation in your code was misleading. The compiler generated message is [-Werror=misleading-indentation] and you should treat it accordingly. You can see how proper indentation makes this error go away.