How to implement suffix array in C without using qsort?

Question

I searched for the implementation of suffix array in C, but all the programs I saw were in C++ which used sort. I am not sure how can I use the built-in function of C, qsort() in place of sort() function of C. Can we implement suffix arrays without using qsort()? or how to use qsort() to implement suffix arrays in C?

here is the code that I got from geeksforgeeks.com:

int cmp(struct suffix a, struct suffix b) 
{ 
return strcmp(a.suff, b.suff) < 0? 1 : 0; 
}

int *buildSuffixArray(char *txt, int n) 
{ 
// A structure to store suffixes and their indexes 
struct suffix suffixes[n]; 

// Store suffixes and their indexes in an array of structures. 
// The structure is needed to sort the suffixes alphabatically 
// and maintain their old indexes while sorting 
for (int i = 0; i < n; i++) 
{ 
    suffixes[i].index = i; 
    suffixes[i].suff = (txt+i); 
} 

// Sort the suffixes using the comparison function 
// defined above. 
sort(suffixes, suffixes+n, cmp); 

// Store indexes of all sorted suffixes in the suffix array 
int *suffixArr = new int[n]; 
for (int i = 0; i < n; i++) 
    suffixArr[i] = suffixes[i].index; 

// Return the suffix array 
return  suffixArr; 
} 

the cmp function is comparing structure data type while I am getting an error when using qsort(), which says that only void input is allowed.

Answer 1

The declaration of the qsort function is as follows:

void qsort(void *base, size_t nmemb, size_t size,
       int (*compar)(const void *, const void *));

You'll notice that the comparison function it accepts must be defined to take a const void * for each of its two parameters, but you're instead passing in a struct suffix for each one.

You need to change your comparison function to use the parameter types that qsort expects. Then you can convert those parameters inside of the function to the proper pointer type and use those.

int cmp(const void *p1, const void *p2) 
{ 
    const struct suffix *a = p1;
    const struct suffix *b = p2;
    return strcmp(a->suff, b->suff) < 0? 1 : 0; 
}