并行排序两个数组 [英] Parallel sort two arrays

问题描述

假设我有两个数组：

char **words = (char**) malloc(MAX * sizeof(char*));
int *count = malloc(MAX * sizeof(int));

第一个存储的话在给定的列表：

The first one stores the words in a given list:

words[0] = "myword0" / words[1] = "myword1" / words[2] = "myword3" ...

和第二个存储列表中的每个单词的出现的次数：

and the second one stores the number of occurences of each word in the list:

count[0] = 4 //means that "myword0" appears 4 times in the list

我要打印的最频繁的词，它的出现次数。 如果有出现的次数相同的话，打印按字母顺序排列的第一个

要做到这一点，我想到了按字母顺序排序的字

To do that, I thought about alphabetically sorting words:

int sortWordsAlph(const void* a, const void* b)
{
    char **x = (char**)a;
    char **y = (char**)b;

    return (strcmp(*x,*y));
}

和 INT的main（）：

qsort(words, MAX, sizeof(char*), sortWordsAlph);

现在的问题是是计数。它应该仍然指向每个词的出现，因而这意味着我必须得排序。我怎样才能做到这一点？

Now, the problem is with count. It should still point to the occurrences of each word, thus meaning I have to sort it too. How can I do this?

也许我应该使用交换算法代替的qsort？

Maybe I should use a swapping algorithm instead of qsort?

推荐答案

如果你想使用的qsort（），你应该使用同时包含结构的数组字和计数。然后，您可以通过您的数组的qsort（）使用自定义比较函数：

If you want to use qsort(), you should use an array of structs that contain both the word and the count. You can then pass your array to qsort() with a custom comparison function:

struct wc_s {
  char *word;
  int count;
};

int cmp_words (const void *p1, const void *p2)
{
   const struct wc_s *s1 = p1;
   const struct wc_s *s2 = p2;
   return strcmp (s1->word, s2->word);
}

int cmp_counts (const void *p1, const void *p2)
{
   const struct wc_s *s1 = p1;
   const struct wc_s *s2 = p2;
   return s2->count - s1->count;
}

...
struct wc_s *wc_list = malloc (MAX * sizeof *wc_list);
...
qsort (wc_list, MAX, sizeof *wc_list, cmp_counts);

如果的qsort（）能保证执行（即比较相同保留其原来的顺序，即两个元素）一个稳定的排序，你可以通过首先分拣解决您的问题一句话，再由数排序。不幸的是，产生的两个相等的元素的顺序是的未指定的

If qsort() was guaranteed to perform a stable sort (i.e. two elements that compare the same retain their original order), you could solve your problem by first sorting by word, and then sorting by count. Unfortunately, the resulting order of two equal elements is unspecified.

你可以做什么样的是阵列由计数，然后通过数组寻子阵列具有相同计数和排序的个别：

What you could do is sort the array by count, and then go through the array to find sub-arrays with the same counts, and sort those individually:

int start = 0;
int length;
while (start < MAX) {
  for (length = 1; start+length < MAX; length++) {
    if (wc_list[start].count != wc_list[start+length].count)
      break;
  }
  qsort (wc_list+start, length, sizeof *wc_list, cmp_words);
  start += length;
}

这篇关于并行排序两个数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！