Matrix Sorting mergesort C

Question

我有这个问题，必须对矩阵进行排序：

至：

因此，行保持不变，如示例所示，每列从小到大。矩阵将始终具有3列和x行。

我已经尝试了插入排序，尽管可以工作，但效率不高，并且在实际应用程序中，鉴于给定的行数，它需要大量运行。

我将提供一个假装的小代码：

#include <stdio.h>
int main()
{
    int abc[6][3] ={
        {0,0,4},
        {1,0,3},
        {0,1,4},
        {1,1,5},
        {0,2,3},
        {1,2,4},
    };

    //
    //sort 
    //

    for (int i = 0; i < 6; ++i)
    {
        printf("%d %d %d\n", abc[i][0], abc[i][1], abc[i][2]);
    }
    return 0;
}

我想同时尝试mergesort和quicksort，但可以得到任何帮助。

先谢谢您。

Answer 1

您可以采用以下四种方式之一来编写比较函数（两种形式上正确，但都等同于¹）。令人恐惧的qsort原型int compare (const void *a, const void *b)只是C将指针传递到要排序的数组元素的方式。您的工作仅仅是在函数比较之前先回退到正确的类型。

真正的问题是“正在传递什么类型的指针？

当您回答时，这很容易。您正在按行对2D数组排序。 2D数组实际上是1D数组的数组。传递给进行比较的每个指针将是指向一维数组（行）的指针]

因此，每个a和b将是int [3]的指向数组的指针。在您的compare函数中，您将需要强制转换为int [3]数组的指针，然后取消引用一次以将类型保留为int [3]，然后根据第三个元素进行比较。（但是当您访问现在的类型int [3]数组时，指针转换也适用于该数组，因此您只需要在指针值中添加2并取消引用，即可与第三个元素进行比较）。

[您可以使用两个条件测试的结果来避免潜在的溢出，这可能是由于简单返回b - a而引起的，如果b是一个较大的负数而a是较大的（或b是一个较大的正数）如果结果超出a的存储容量，则会出现int较大的负数）。因此，对于升序排序，可以使用：

    return (a > b) - (a < b);

（对于降序排序，只需将比较转过来，例如(a < b) - (a > b)。尝试一下。为a和b选择任意两个值并计算结果。在升序情况下，a小于b，您return 0 - 1;（或-1），例如，表示a在b之前排序）

那么，比较功能是什么样子？由于int [3]的指向数组的指针的形式类型为int (*)[3]，因此可以执行以下操作：

int comp (const void *a, const void *b)
{
    int *pa2 = *(int (*)[3])a + 2,
        *pb2 = *(int (*)[3])b + 2;

    return (*pa2 > *pb2) - (*pa2 < *pb2);
}

或者如果您只是想简单地使int pa2而不必担心在比较中必须取消引用指针，那么对于第二个形式强制转换，您可以将a的完整强制转换括在括号中，然后只使用(stuff a)[2]直接访问第三个整数值-只会使看起来更混乱，例如

int comp (const void *a, const void *b)
{
    int pa2 = (*(int (*)[3])a)[2],
        pb2 = (*(int (*)[3])b)[2];

    return (pa2 > pb2) - (pa2 < pb2);
}

（对您而言最有意义的事物）

然后按2D数组中的每一行的第三个元素进行排序确实很简单，例如

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

int comp (const void *a, const void *b)
{
    int *pa2 = *(int (*)[3])a + 2,
        *pb2 = *(int (*)[3])b + 2;

    return (*pa2 > *pb2) - (*pa2 < *pb2);
}

int main() {

    int abc[6][3] ={{0,0,4},
                    {1,0,3},
                    {0,1,4},
                    {1,1,5},
                    {0,2,3},
                    {1,2,4}};

    qsort (abc, 6, sizeof *abc, comp);

    for (int i = 0; i < 6; ++i)
        printf(" %2d %2d %2d\n", abc[i][0], abc[i][1], abc[i][2]);

}

示例使用/输出

$ ./bin/qsort2d+2
  1  0  3
  0  2  3
  0  0  4
  0  1  4
  1  2  4
  1  1  5

现在，编写比较函数强制转换的最后两种等效方法依赖于数组/指针转换的连续应用，并理解指向数组的指针和数组本身都将指向相同的地址（但形式上是不同的类型）形式上您有int (*)[3]，但由于您知道只需要该地址之后的第二个整数，因此可以将比较指针a和b强制转换为int *并加两个。这是等效的，但不反映形式转换。（您也可以将整个类型转换括在括号中，也可以使用[2]。）>

在这种情况下，强制转换看起来要简单得多，但是实际发生的事情可能不太明显。我将留给您尝试用*(int (*)[3])替换整个程序中的(int *)。（这将避免在评论中进行冗长的讨论）

仔细研究并仔细考虑“传递的是哪种类型的指针？”

为什么在比较函数中使用两次比较的结果而不是仅仅使用减法来避免溢出。如果您还有其他问题，请告诉我。

脚注：

1。]

C11 Standard - 6.3.2.1 Other Operands - Lvalues, arrays, and function designators(p3)除非它是sizeof运算符，_Alignof运算符或一元'&'运算符的操作数，或者是用于初始化数组，将类型为[[“ type of array”的表达式转换为类型为[[“ pointer to type”的表达式，该表达式指向数组对象的初始元素，而不是左值。

Matrix Sorting mergesort C

问题描述投票：0回答：1

1个回答

最新问题

Matrix Sorting mergesort C

问题描述 投票：0回答：1

1个回答

最新问题

问题描述投票：0回答：1