2次元配列をC++の1つの列でソートする

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行目によって並べ替えBOする必要があります。したがって、次のような出力が必要です。

{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 

であるように見えることができます必要なのは、バブルソートのコードを抽出することですメインから削除し、任意の2D配列と並べ替えの基準として使用されるすべての行に対して別の関数として書き換えます。

Answer 2

パラレルベクトルの代わりにパラレル値を含む構造体を使用すると、問題は解決しやすくなります。

このような構造に戻すのは簡単です。ソートキーとインデックスを含む中間ベクトルを作成してソートするだけです。

インデックスをソートした後、正しい順序ですべての個々のベクトルを並べ替える直接的な方法が得られます。

私は以下のようにします（私はBoost Unit Testに入れましたが、何が行われるかは明らかです）。

#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; 
    } 
}