使用qsort同时对两个数组进行排序?

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

V…比较函数

int rstrcmp(const void *p1, const void *p2) {
    return strcmp(*(char * const *)p1, *(char * const *)p2);
}

3 个解决方案

#1

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

一件简单的事情是使用一个struct来存储单词/频率对，然后对这些struct的数组进行排序。

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);
}

#2

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?

标准的qsort()函数不能直接执行您希望的操作。除此之外，它如何知道(或如何告诉它)两个数组要并行排序?

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:

还有另一种选择——但有点扭曲。您可以创建一个包含如下条目的int数组:

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.

然后将这个数组传递给sort函数，以及一个知道两个数组的基本地址的比较器。函数的作用是:传递数组中的数据;比较器查看其他数组中的数据。另外两个数组必须是全局变量(至少是文件范围)，或者需要全局变量，这些全局变量是指针，可以用两个数组的基本地址初始化。

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

排序之后，可以使用array1[index[i]]和array2[index[i]访问排序数组的第i个元素。

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

如果您在BSD上，还有一个选项:您可以使用qsort_r()函数:

 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.

“thunk”是作为第一个参数传递给比较器的指针。您可以使用这个与索引数组方案一起使用，将指向两个数组的指针传递到比较器中，这样您就根本不需要文件范围变量了。你仍然不能做两个独立的交换，所以你必须使用指数数组方案。

#3

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).

对于排序并行数组，您可能会发现一种有用的方法:创建一个整数数组(需要严格地正确使用size_ts)，并通过numWords-1初始化它的值0。然后qsort数组使用的比较函数strcmp(字典(*(int *)p1),字典(*(int *)p2),然后使用排序的索引数组排列字典和频率在同一时间(这很容易通过复制,或不那么容易做到就地互换:这里是后者的一个例子)。

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

Turix可能有更好的解决方案——使用一组结构而不是两个数组来避免整个问题。

#1