Why my countsort cannot put element in dst[0]?

Question

This is a function of count sort, I write it according to text book and there is something wrong dst[0] comes a random number while it should have be 0; However, the 0 appears in dst[1] and 2 in dst[2]... finally 8 in dst[9]; Seem like there is a bias, but I donnot know where it is.

#include<stdio.h>
#include<malloc.h>

//count sort;
/*arr: pointer to array, ifas: index of start, ifae: index of end, nfs: number of start, nfe: number     of end*/ 
int* countsort(int* arr, int ifas, int ifae, int nfs, int nfe){
    int * ap = (int*)malloc(sizeof(int) * (nfe - nfs + 1)), tmp;
    int * dst = (int*)malloc(sizeof(int) * (ifae - ifas + 1));
    for(tmp = 0; tmp <= nfe - nfs; tmp++){
        ap[tmp] = 0;
    }
    for(tmp = ifas; tmp <= ifae; tmp++){
        ap[arr[tmp] - nfs]++;
    }
    
    for(tmp = 1; tmp <= nfe - nfs; tmp++){
        ap[tmp] += ap[tmp-1];
    }
    for(tmp = 0; tmp <= 9; tmp++){
        printf("%d ", ap[tmp]);
    }
    printf("\n");
    for(tmp = 0; tmp <= 9; tmp++){
        printf("%d ", arr[tmp]);
    }
    printf("\n");
    for(tmp = ifae - ifas; tmp >= 0; tmp--){
        dst[ap[arr[tmp] - nfs]] = arr[tmp];
        ap[arr[tmp]-nfs] = ap[arr[tmp]-nfs] - 1;
    }
    for(tmp = 0; tmp <= 9; tmp++){
        printf("%d ", dst[tmp]);
    }
    printf("\n");
    free(ap);
    return dst;
}

int main(){
    int arr[10] = {9,5,3,8,0,1,6,4,7,2};
    int* res = countsort(arr,0,9,0,9);
}

I would appreciate if someone can find the location of the bug.

Answer 1

In this loop:

    for(tmp = ifae - ifas; tmp >= 0; tmp--){
        dst[ap[arr[tmp] - nfs]] = arr[tmp];
        ap[arr[tmp]-nfs] = ap[arr[tmp]-nfs] - 1;
    }

the assignments to dst and ap are in the wrong order. Compare with the algorithm in Wikipedia, it has:

    for i = length(input) - 1 down to 0 do
        j = key(input[i])
        count[j] = count[j] - 1
        output[count[j]] = input[i]

Your ap array corresponds to count in the pseudo-code, and you need to decrement the count before assigning to the output, not after. That's why everything is off by 1 in the result.