使用qsort函数以替代方式对整数数组进行排序。 [英] Sorting an array of integers in alternate fashion using qsort function.

问题描述

/ *我最近学习了qsort函数。此C代码给出了错误的输出。需要帮助。
问题-以替代方式对整数数组进行排序。 （偶数索引和奇数索引的元素分别排序）
OUTPUT-0 4 1 2 5 8 7 5 9 3
10 5
* /

/*I recently learnt qsort function. This c code is giving incorrect output. Need help with this. PROBLEM- Sorting an array of integers in alternate fashion. (the elements at even indices and those at odd indices are sorted separately) OUTPUT- 0 4 1 2 5 8 7 5 9 3 10 5 */

#include <stdio.h>
#include <stdlib.h>

// This function is used in qsort to decide the relative order
// of elements at addresses p and q.
int comparator(const void *p, const void *q)
{
    // Get the values at given addresses
    int l = *(const int *)p;
    int r = *(const int *)q;

    return (l-r);
}

// A utility function to print an array
void printArr(int arr[], int n)
{
    int i;
    for (i = 0; i < n; i = i+1)
        printf("%d ", arr[i]);
}

// Driver program to test above function
int main()
{
    int arr[] = {1,4,7,2,9,3,0,8,6,5};

    int size0 = sizeof(arr) / sizeof(arr[0]);
    int size1 = (int) ((float)sizeof(arr) / sizeof(arr[0]) / 2 + 0.5);
    int size2 = size0 - size1;

    qsort((void *)arr+1, size2, 2*sizeof(arr[0]), comparator);   
    //sort odd positions

    qsort((void *)arr, size1, 2*sizeof(arr[0]), comparator);
    //sort even positions

    printf("Output array is\n");
    printArr(arr, size0);
    printf("\n%d %d", size0, size1);

    return 0;
}

推荐答案

可以使用 qsort（）用于分别对偶数/奇数元素进行排序。
但是，必须稍微更改设置才能完成此操作。

It is possible to use qsort() for sorting of even/odd elements separately. However, the setup must be changed slightly to accomplish this.

正如Peter正确提到的那样（必须承认，我之前没有考虑过）。偶数元素会破坏奇数元素的结果，因为交换会考虑表示为偶数和奇数元素对的元素大小。

As Peter mentioned correctly (and I didn't consider before as I must admit) sorting for even elements will "destroy" the result for odd elements as swapping considers the element size which is denoted as pair of even and odd element.

考虑到这一点，如果在进行第二次排序之前先保存了第一次排序的结果，则可以解决所有问题。

This in mind, a solution can be done for all that if the result of first sorting is saved before second sorting is done.

在我的示例中，我复制了相关元素

In my sample, I copied the relevant elements after first sorting and merged them in after second sorting.

这是我的示例 testQSortEvenOdd.c ：

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

int compEven(const int *p1, const int *p2)
{
  return (p1[0] > p2[0]) - (p1[0] < p2[0]);
}

int compOdd(const int *p1, const int *p2)
{
  return (p1[1] > p2[1]) - (p1[1] < p2[1]);
}

void printArray(size_t n, int *arr, int step)
{
  for (; n--; arr += step) printf(" %d", *arr);
  putchar('\n');
}

int main()
{
  int arr[] = { 1, 4, 7, 2, 9, 3, 0, 8, 6, 5 };
  enum { size = sizeof arr / sizeof *arr };
  assert(!(size & 1));
  /* sort odd positions */
  qsort(arr, (size + 1) / 2, 2 * sizeof *arr,
    (int(*)(const void*, const void*))&compOdd);
  /* output of sorted array for odd positions */
  puts("Odd elements sorted:");
  printArray(size / 2, arr + 1, 2);
  int arrRes[(size + 1) / 2];
  for (size_t i = 1; i < size; i += 2) arrRes[i / 2] = arr[i];
  /* sort even positions */
  qsort(arr, (size + 1) / 2, 2 * sizeof *arr,
    (int(*)(const void*, const void*))&compEven);
  /* output of sorted array for even positions */
  puts("Even elements sorted:");
  printArray((size + 1) / 2, arr, 2);
  /* merge array with copy */
  for (size_t i = 1; i < size; i += 2) arr[i] = arrRes[i / 2];
  puts("Merged elements:");
  printArray(size, arr, 1);
  /* done */
  return 0;
}

在Windows 10（64位）的Cygwin中测试：

Tested in Cygwin on Windows 10 (64 bit):

$ gcc --version
gcc (GCC) 6.4.0

$ gcc -std=c11 -o testQSortEvenOdd testQSortEvenOdd.c 

$ ./testQSortEvenOdd
Odd elements sorted:
 2 3 4 5 8
Even elements sorted:
 0 1 6 7 9
Merged elements:
 0 2 1 3 6 4 7 5 9 8

$

一些附加说明：

1. 我的方式（和发问者）使用 qsort（），它一次处理两个连续的 int 值。因此，必须承认该数组具有适当数量的元素。 （否则， qsort（）要么进行越界访问，要么不考虑最后一个元素。）考虑到这一事实，我插入了

1. The way I (and the questioner) used qsort(), it handles two consecutive int values at once. Hence, it must be granted that the array has an appropriate number of elements. (Otherwise, qsort() either does out-of-bound access or cannot consider the last element.) To consider this fact, I inserted the

assert（！（size& 1））;

可以是读为确保数组具有偶数个元素。

which can be read as "Assure that the array has an even number of elements."

我决定制作单独的函数 compEven（）和 compOdd（）简化了事情。我根据自己的需要更改了两者的签名，并从gcc收到有关错误函数签名的投诉（警告）。因此，我将函数指针强制转换为期望的类型（使gcc保持沉默）。

I decided to make separate functions compEven() and compOdd() as IMHO it simplified things. I changed the signature of both to my needs and got complains (warnings) from gcc about wrong function signature. Therefore, I casted the function pointers to the expected type (to make gcc silent).

Jonathon给出了一个很好的提示，可以使比较函数对下溢问题具有鲁棒性。 。 返回p1 [0]-p2 [0]; 当差异大于 INT_MAX 时，可能导致错误的结果小于 INT_MIN 。相反，他建议使用：

Jonathon gave a nice hint to make the comparison functions robust against underflow issues. return p1[0] - p2[0]; can cause wrong results when the difference becomes greater than INT_MAX or smaller than INT_MIN. Instead he recommends to use:

返回（p1 [0]> p2 [0]）-（p1 [0]< p2 [ 0]）;

永远不会出现任何上溢/下溢问题。

which never can have any overflow/underflow issues.

工作原理：

如果 a< b ：（a> b）-（a< b）⇒ 0-1 ⇒ -1

In case a < b: (a > b) - (a < b) ⇒ 0 - 1 ⇒ -1

如果 a == b ： （a> b）-（a< b）⇒ 0-0 ⇒ 0

In case a == b: (a > b) - (a < b) ⇒ 0 - 0 ⇒ 0

如果 a> b ：（a> b）-（a< b）⇒ 1-0 ⇒ 1

In case a > b: (a > b) - (a < b) ⇒ 1 - 0 ⇒ 1

非常聪明的Jonathan Leffler–我印象深刻。

Very clever Jonathan Leffler – I'm impressed.

这篇关于使用qsort函数以替代方式对整数数组进行排序。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！