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);
}
Anton K
  • 4,658
  • 2
  • 47
  • 60
  • 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.. – bwegs Nov 19 '14 at 04: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. – Turix Nov 19 '14 at 04: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? – nobodyImportant Nov 19 '14 at 04:26
  • @nobodyImportant Ok, I added some sample code as an answer below. – Turix Nov 19 '14 at 04:45

3 Answers3

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);
}
Turix
  • 4,470
  • 2
  • 19
  • 27
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.

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
  • 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 Nov 19 '14 at 14:40
  • 1
    @mafso: interesting. Consistency — who needs consistency? – Jonathan Leffler Nov 19 '14 at 14:45
  • 2
    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](https://sourceware.org/ml/libc-alpha/2008-12/msg00007.html)) and because of ..., well, [some copyright reasons](https://sourceware.org/ml/libc-alpha/2008-12/msg00006.html) (??). 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 Nov 19 '14 at 15:11
  • 1
    @mafso: Good research. I'm already on [record](http://stackoverflow.com/questions/372980/do-you-use-the-tr-24731-safe-functions) as not being enthusiastic about what was [TR 24731-1](http://www.open-std.org/jtc1/sc22/wg14/www/projects#24731-1) and is now Annex K. You're right. The Microsoft specification of [`qsort_s()`](http://msdn.microsoft.com/en-us/library/4xc60xas.aspx) 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. – Jonathan Leffler Nov 19 '14 at 15:32
  • 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. – mafso Nov 19 '14 at 16:53
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.

Community
  • 1
  • 1
hobbs
  • 223,387
  • 19
  • 210
  • 288