在C ++中按一列排序2d数组

Question

我有一个真正指定的问题需要处理。我需要降序排序一个数组[4] [x]。从实例，如果我得到如下值：

{121,120,203,240}
{0.5,0.2,3.2,1.4}
{1.3,1.5,1.2,1.8}
{3  ,2  ,5  ,4  }

所有值都必须按第4行排序。因此，我需要这样的输出：

{203,240,121,120}
{3.2,1.4,0.5,0.2}
{1.2,1.8,1.3,1.5}
{5  ,4  ,3  ,2  }

我尝试过冒泡排序方法，但它无法正常工作。

Answer 1

使用冒泡排序对数组进行排序的简单方法可以采用以下方式

#include <iostream>
#include <iomanip>
#include <utility>

int main()
{
    const size_t N = 4;

    double a[][N] =
    {
        { 121, 120, 203, 240 },
        { 0.5, 0.2, 3.2, 1.4 },
        { 1.3, 1.5, 1.2, 1.8 },
        { 3, 2, 5, 4 }
    };

    for (const auto &row : a)
    {
        for (double x : row) std::cout << std::setw( 3 ) << x << ' ';
        std::cout << '\n';
    }
    std::cout << std::endl;

    //  The bubble sort
    for (size_t n = N, last = N; not (n < 2); n = last)
    {
        for (size_t i = last = 1; i < n; i++)
        {
            if (a[N - 1][i - 1] < a[N - 1][i])
            {
                for (size_t j = 0; j < N; j++)
                {
                    std::swap(a[j][i - 1], a[j][i]);
                }
                last = i;
            }
        }
    }

    for (const auto &row : a)
    {
        for (double x : row) std::cout << std::setw( 3 ) << x << ' ';
        std::cout << '\n';
    }
    std::cout << std::endl;

    return 0;
}

程序输出是

121 120 203 240
0.5 0.2 3.2 1.4
1.3 1.5 1.2 1.8
  3   2   5   4

203 240 121 120
3.2 1.4 0.5 0.2
1.2 1.8 1.3 1.5
  5   4   3   2

您所需要的只是从main中提取冒泡排序的代码，并将其重写为任何2D数组和用作排序标准的任何行的单独函数。

Answer 2

如果不是并行向量，我们有一个包含并行值的结构，问题就很容易解决。

回到这样的结构很容易：只需创建一些包含排序键和索引的中间向量并对其进行排序。

排序后，索引为我们提供了一种直接的方式来按正确的顺序重新排序所有单个向量。

我会做类似下面的事情（我把它放在一个Boost单元测试中，但是做的应该是显而易见的）。

#define BOOST_AUTO_TEST_MAIN
#define BOOST_TEST_MODULE TestPenta
#include <boost/test/auto_unit_test.hpp>

#include <iostream>
#include <vector>

std::vector<int> v1 = {121,120,203,240};
std::vector<float> v2 = {0.5,0.2,3.2,1.4};
std::vector<float> v3 = {1.3,1.5,1.2,1.8};
std::vector<int> v4 = {3  ,2  ,5  ,4  };

std::vector<int> expected_v1 = {203,240,121,120};
std::vector<float> expected_v2 = {3.2,1.4,0.5,0.2};
std::vector<float> expected_v3 = {1.2,1.8,1.3,1.5};
std::vector<int> expected_v4 = {5  ,4  ,3  ,2  };

BOOST_AUTO_TEST_CASE(TestFailing)
{
    // First create an index to sort containing sort key and initial position
    std::vector<std::pair<int,int>> vindex{};
    int i = 0;
    for (auto x: v4){
        vindex.push_back(std::pair<int,int>(x,i));
        ++i;
    }

    // Sort the index vector by key value
    struct CmpIndex {
        bool operator() (std::pair<int, int> & a, std::pair<int, int> & b) { 
            return a.first > b.first ;
        }
    } cmp;

    std::sort(vindex.begin(), vindex.end(), cmp);

    // Now reorder all the parallel vectors using index
    // (of course in actual code we would write some loop if several vector are of the same type).
   // I'm using parallel loops to avoid using too much memory for intermediate vectors

    {
        std::vector<int> r1;
        for (auto & p: vindex){
            r1.push_back(v1[p.second]);
        }
        v1 = r1;
    }
    {
        std::vector<float> r2;
        for (auto & p: vindex){
            r2.push_back(v2[p.second]);
        }
        v2 = r2;
    }
    {
        std::vector<float> r3;
        for (auto & p: vindex){
            r3.push_back(v3[p.second]);
        }
        v3 = r3;
    }
    {
        std::vector<int> r4;
        for (auto & p: vindex){
            r4.push_back(v4[p.second]);
        }
        v4 = r4;
    }

    // Et voila! The vectors are all sorted as expected
    i = 0;
    for (int i = 0 ; i < 4 ; ++i){
        BOOST_CHECK_EQUAL(expected_v1[i], v1[i]);
        BOOST_CHECK_EQUAL(expected_v2[i], v2[i]);
        BOOST_CHECK_EQUAL(expected_v3[i], v3[i]);
        BOOST_CHECK_EQUAL(expected_v4[i], v4[i]);
        ++i;
    }
}