3

I can sort a array of pointers to words so that they are ordered alphabetically, the problem is that I need to ALSO sort an integer array (the number of times that specific word is used) so that the integers are in the same place as their respective words:

my code: 

for (i = 0; i < numWords; i++) {
    // prints out the words and their frequency respectively
    printf("%s - %d\n", dictionary[i], frequency[i]); 
}

//sorts the dictionary so that the words are 'alphabetical'
qsort(dictionary, numWords, sizeof(char *), rstrcmp);  
printf("\nafter qsort\n");  //checkmark

for (i = 0; i < numWords; i++) {
    // prints the word list alphabetically, but the frequencies are no longer matched
    printf("%s - %d\n", dictionary[i], frequency[i]); 
}

...comparison function V

int rstrcmp(const void *p1, const void *p2) {
    return strcmp(*(char * const *)p1, *(char * const *)p2);
}
Improve this question
4
  • 1
    Ideally you could use a hash table/map where the words are the key and the frequency is the value and just sort based on the key.. Commented Nov 19, 2014 at 4:00
  • 2
    A simple thing to do would be to use a struct to store word/frequency pairs and then sort an array of these structs. Commented Nov 19, 2014 at 4:02
  • @Turix i might be having a bit of trouble, i'm no good with pointers and when to use them; i barely get by, care to show an example of how to initialize the array of structs? Commented Nov 19, 2014 at 4:26
  • @nobodyImportant Ok, I added some sample code as an answer below. Commented Nov 19, 2014 at 4:45

3 Answers 3

Reset to default
9

A simple thing to do would be to use a struct to store word/frequency pairs and then sort an array of these structs.

For example:

struct WordFrequency
{
    const char * word;
    int frequency;
} wordFreqs[numWords];        // Assumes numWords is static/global and constant...

Then:

for (i = 0; i < numWords; i++) {
    printf("%s - %d\n", dictionary[i], frequency[i]);
    wordFreqs[i].word = dictionary[i];
    wordFreqs[i].frequency = frequency[i];
}

//sorts the dictionary so that the words are 'alphabetical'
qsort(wordFreqs, numWords, sizeof(struct WordFrequency), wfcmp);  

for (i = 0; i < numWords; i++) {
    printf("%s - %d\n", wordFreqs[i].word, wordFreqs[i].frequency); 
}

And:

int wfcmp(const void *p1, const void *p2) {
     return strcmp(((const struct WordFrequency *)p1)->word, ((const struct WordFrequency *)p2)->word);
}
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

3

The standard qsort() function cannot do as you wish directly. All else apart, how does it know (or how do you tell it) which two arrays to sort in parallel?

You either have to change the data structure (use an array of a structure type), or you have to write your own sort function. Of the two, changing the data structure is probably the easier.

There is another option — but a somewhat contorted one. You could create an array of int with entries such that:

for (int i = 0; i < N; i++)
    index[i] = i;

You then pass this array to the sort function, along with a comparator that knows the base addresses of the two arrays. The qsort() function permutes the data in the array; the comparator looks at the data in the other arrays. The other two arrays have to be global (at least file scope) variables, or you need global variables that are pointers that can be initialized with the the base addresses of the two arrays.

After the sort, you can use array1[index[i]] and array2[index[i]] to access the ith element of the sorted arrays.

One other option if you're on BSD: you could use the qsort_r() function:

 void qsort_r(void *base, size_t nel, size_t width, void *thunk,
              int (*compar)(void *, const void *, const void *));

The 'thunk' is a pointer that's passed to the comparator as the first argument. You could use this with the index-array scheme to pass the pointers to the two arrays into the comparator, so you wouldn't need file scope variables at all. You still can't do two independent swaps, though, so you'd have to use the index-array scheme.

Improve this answer

5 Comments

For GNU systems, there is also void qsort_r(void *, size_t, size_t, int (*)(const void *, const void *, void *), void *arg); with a different prototype.
@mafso: interesting. Consistency — who needs consistency?
FYI (I had to look): Seems the GNU version was designed like that to only need to implement one function (cf. the glibc mailing list) and because of ..., well, some copyright reasons (??). Oh, and for sake of completeness, Microsofts CRT and C11 Annex K specify qsort_s, with the charming idea to have the context pointer be the first argument to the compare function in the former and the last one in the latter. You're right, no-one needs consistency!
@mafso: Good research. I'm already on record as not being enthusiastic about what was TR 24731-1 and is now Annex K. You're right. The Microsoft specification of qsort_s() follows the BSD variant of qsort_r(). The 'standard' version follows the GNU variant of qsort_r(). Just another reason to be leery of the well-intentioned but inconsistently defined functions from the extensions to C.
Thanks for the pointers! Just for the record: The MS and the BSD version take a compare function of the same type, but are otherwise incompatible (compared to your example, thunk and compar need to be switched for MS), and GNU and Annex K seem compatible.
2

One approach that you might find useful for sorting parallel arrays: create an array of integers (size_ts to be strictly correct) and initialize it with the values 0 through numWords-1. Then qsort that array using a comparison function that does strcmp(dictionary[*(int *)p1], dictionary[*(int *)p2], then use the sorted array of indices to permute both dictionary and frequency at the same time (this is very easily done by copying, or a little less easily done in-place with swaps: here is an example of the latter).

Turix probably has the better solution though — using an array of structs instead of two arrays avoids the whole problem.

Improve this answer

2 Comments

+1 for the xref to the in-place swapping algorithms.
@hobbs Could you show the function definition used in qsort that will access the local array of strings?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.