基于C中4个索引的元组对数组进行排序

Question

我有一个有趣的问题,过去两天我一直在努力解决这个问题.我试图在C中编写一个程序,它接受以下输入数组:

               1,1,5,5,
               1,1,5,9,
               2,2,6,2,
               1,2,5,5,
               1,3,6,6,
               1,4,5,1,
               4,1,5,6,
               5,2,7,1,
               1,1,6,0,
               2,2,5,0,

step1:根据第3列对上面的数组进行分组(基于第3列的值,对4个元素(即每行)的元组进行桶排序:

               2,2,5,5
               1,1,5,9,
               1,2,5,5,
               1,4,5,1,
               4,1,5,6,
               2,2,5,0,
               2,2,6,2,
               1,3,6,6,
               1,1,6,0,
               5,2,7,1

第2步:最后根据每个桶中的第4列对元素进行排序,如下所示:

最终输出数组:

              2,2,5,0,
              1,4,5,1,
              2,2,5,5,
              1,2,5,5,
              4,1,5,6,
              1,1,5,9,
              1,1,6,0,
              2,2,6,2,
              1,3,6,6,
              5,2,7,1

第1列和第2列中的元素在上述排序过程中不起任何作用.

我尝试了各种技术,使用快速排序或桶排序,然后是后续的快速排序.没有什么事情做得很好.任何人都可以建议使用适当的数据结构在C中执行此操作的方法.

Answer 1

问题是,你真的不需要做多种事情; 你可以根据元组的两个字段进行单一排序.

只需使用现有的排序算法,但使用比较函数,如下所示:

if (val[2] != otherval[2])
    return val[2] < otherval[2];
else
    return val[3] < otherval[3];

这将使用第三列进行排序,除非值相等,在这种情况下它将使用第四列.

或者如果你想做两个单独的排序,FIRST按第四列排序,然后按第三列排序.