C++ 二次配列のソートの仕方について

Question

入力
2 2
2 3
3 1
出力
3 1
2 3
2 2

一行目の数値が優先され上に表示されます、同じ場合は二行目の数値が優先され上に表示されます。
このような処理をするときはどのようなコードを書けばいいでしょうか？
入力を受け付けるコードを打ち込んでから手が止まってしまいました。

追加文:やったことはsort()qsort()などの標準ライブラリの使用です。
しかし、一行目は入れ替えられるが、一行目をキーにして、二行目を呼び出し、入れ替えるにはどうしたらいいのか、アルゴリズムが思いつきません。

　　　　//参考にしたサイト
https://codezine.jp/article/detail/6020
http://stlalv.la.coocan.jp/sort.html

追加文：基礎を学ぶために、標準ライブラリを使って処理をしたいです。構造体の一次配列でもOkです。

ご回答おねがいします！

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void){
    int num[100][100];
    int n;
    cin >> n;
    for(int i = 0;i < n;i++){
            cin >> num[i][0] >> num[i][1]; 
        }
        /*
        int  num[3][2] = {{ 2, 2 }
                          { 2, 3 }
                          { 3, 1 }} 
                              */
         //sortやqsortを使ってみましたが、うまくいきませんでした
         //sort(num[0],num[0] + n,greater<int>());これだとうまく行かない
         //一行目を入れ替えて、同じになった数値をキーにして、二行目を比較して、入れ替える。
　　　　　//といった部分が思いつきません。

        for(int i = 0;i < n;i++){
            cout << num[i][0] << " " << num[i][1] << endl;
        }
        return 0;
}

Comments

[cateye]

未完であっても良いので、ソースを追記して下さい。

[kazuma-s]

行を降順(大きいものから小さいものへ)にソートするんですよね。
1列目の数値でソートし、同じ場合は 2列目でソートする。
1次元配列のソートはできますか？
ソートには何を使いますか？
選択ソート？　バブルソート？　挿入ソート？　クイックソート？
あるいはライブラリ関数の qsortを使う？
質問を編集して、ソートの条件を追加訂正してください。

[bjnes]

データの持ち方は２次元配列が本当に正しいのですか？
構造体X,yの１次元配列のほうが趣旨にあっていませんか？

[Usagi365m]

次の出題が二次配列のソートが必要のようで、この段階から学習しておきたいと思い質問いたしました。
構造体の一次配列のソートのほうも、時間がありましたらやり方をご教示いただければ幸いです。
まだ初心者で、明快な質問ができず申し訳ありません。ご理解のほど、ご回答をおねがいいたします。

[bboydaisuke]

> 次の出題が二次配列のソートが必要のようで、この段階から学習しておきたいと思い質問いたしました。

予習なんかしなくていいから復習をして、授業をしっかり聞いてわからないことは授業中に質問した方がいいと思う。

[Usagi365m]

アドバイスありがとうございます。今回の問題はweb上の出題（スキルチェック）であり、残念なことにこの問題に対する回答及び、解説がありません。C＋＋は完全独学です。
ソートに関するものはインターネットサーフィンで何かしらのヒントは得たものの、かゆいところに手が届かないものでした。
今回、自分ではわからないところをこの場を借りてを質問した経緯です。
まだ学習から一週間しか立っていないためC++を使い慣れるまではみなさまに多大なご迷惑をおかけすると思いますが、何卒よろしくおねがいします。

[bboydaisuke]

> みなさまに多大なご迷惑をおかけすると思います

いやいや、勘弁してよ（笑
実際はここは「コミュニティ」だから「多大な迷惑」を感じたら誰も回答とかくれなくなると思うけどね。

Answer 1

２次元配列で並んでいるということは、各要素の変化は他の要素に影響を与えずに、独立しているということ。

C++はしっかりとクラス定義を覚えて手続きっぽくならないように、
気をつけないといけないです。

目安としては２０行以上｛｝の中に書かないこと。

あとC++20だとコレぐらい楽に書けれます。

//注意：C++20 

#include <iostream>
#include <vector>
#include <compare>
#include <string>

class KeyValue
{
public:
    int FirstKey;
    int SecondKey;

    KeyValue(int key1 = 0, int key2 = 0) : FirstKey(key1), SecondKey(key2)
    {
    }
    auto operator<=>(const KeyValue &ather)
    {
        auto result = this->FirstKey <=> ather.FirstKey;
        if (result == std::strong_ordering::equal)
        {
            return this->SecondKey <=> ather.SecondKey;
        }
        else
        {
            return result;
        }
    }
};

int main()
{
    std::vector keys = {KeyValue(1, 3), KeyValue(1, 2), KeyValue(2, 3),
                        KeyValue(3, 2), KeyValue(1, 1), KeyValue(1, 2), KeyValue(1, 2),
                        KeyValue(3, 1)};

    std::sort(keys.begin(), keys.end());

    std::for_each(keys.begin(), keys.end(), [](KeyValue x) {
        std::cout << "key1:" << x.FirstKey << "key2:" << x.SecondKey << std::endl;
    });
}

Comments

[Usagi365m]

アドバイス非常に参考になりました、回答ありがとうございます！

Answer 2

#include <iostream>  // cin, cout
#include <vector>    // vector
#include <algorithm> // sort
using namespace std;

struct Comp {
	bool operator()(vector<int> &a, vector<int> &b) {
		return b[0] == a[0] ? b[1] < a[1] : b[0] < a[0];
	}
};

int main()
{
    int n;
    cin >> n;
	vector<vector<int>> num(n, vector<int>(2));

    for (int i = 0;i < n;i++)
        cin >> num[i][0] >> num[i][1]; 

	sort(num.begin(), num.end(), Comp());

    for (int i = 0; i < n; i++)
        cout << num[i][0] << " " << num[i][1] << endl;
}

関数オブジェクト Comp() が分かりにくければ、
比較関数 comp を定義しても構いません。

#include <iostream>  // cin, cout
#include <vector>    // vector
#include <algorithm> // sort
using namespace std;

bool comp(vector<int> &a, vector<int> &b)
{
	return b[0] == a[0] ? b[1] < a[1] : b[0] < a[0];
}

int main()
{
    int n;
    cin >> n;
	vector<vector<int>> num(n, vector<int>(2));

    for (int i = 0; i < n;i++)
        cin >> num[i][0] >> num[i][1]; 

	sort(num.begin(), num.end(), comp);

    for (int i = 0; i < n; i++)
        cout << num[i][0] << " " << num[i][1] << endl;
}

また、ラムダ式を使うやり方もあります。

#include <iostream>  // cin, cout
#include <vector>    // vector
#include <algorithm> // sort
using namespace std;

int main()
{
    int n;
    cin >> n;
	vector<vector<int>> num(n, vector<int>(2));

    for (int i = 0; i < n;i++)
        cin >> num[i][0] >> num[i][1]; 

	sort(num.begin(), num.end(), [](vector<int> &a, vector<int> &b) {
		return b[0] == a[0] ? b[1] < a[1] : b[0] < a[0];
	});

    for (int i = 0; i < n; i++)
        cout << num[i][0] << " " << num[i][1] << endl;
}

追記
vector ではなく、配列を使って、qsort でソートするなら、

#include <iostream>
#include <cstdlib>   // qsort
using namespace std;

int comp(const void *x, const void *y)
{
	int (*a)[2] = (int (*)[2])x, (*b)[2] = (int (*)[2])y;
	return b[0] == a[0] ? b[1] - a[1] : b[0] - a[0];
}

int main(void)
{
    int num[100][2];
    int n;
	cin >> n;

    for (int i = 0; i < n; i++)
		cin >> num[i][0] >> num[i][1];

	qsort(num, n, sizeof num[0], comp);

    for (int i = 0; i < n; i++)
		cout << num[i][0] << " " << num[i][1] << endl;
}

追記2

return b[0] == a[0] ? b[1] < a[1] : b[0] < a[0]; を 3項演算子を使わずに書くと、

	if (b[0] == a[0])
		return b[1] < a[1];
	else
		return b[0] < a[0];

となります。比較演算子 < による演算結果は true または false なので何の問題
もないのですが、比較演算の式はどうしても if文の中に書きたいというのなら、

	if (b[0] == a[0])
		if (b[1] < a[1])
			return true;
		else
			return false;
	else
		if (b[0] < a[0])
			return true;
		else
			return false;

Comments

[Usagi365m]

ご回答ありがとうございます！
sort(num.begin(), num.end(), [](vector<int> &a, vector<int> &b) {
return b[0] == a[0] ? b[1] < a[1] : b[0] < a[0];
ここの部分はどのような処理をしているのでしょうか？

[kazuma-s]

関数オブジェクト Comp() と 関数 comp は理解できたけど、[] で始まるラムダ式が理解できなかったということでしょうか？

[Usagi365m]

ご丁寧にありがとうざいます！
visualstudioで実際にステップインしながら確認しました、vector<int> &a, vector<int> &bで配列を取得して（今回の場合は最初a[2]{2,2},b[2]{2,3}....begin()で配列の最初、endで配列の終わりの数を指定、全ての要素を比較する全探査？を行い終わるまで処理？）
return b[0] == a[0] ? b[1] < a[1] : b[0] < a[0];
三項演算子じゃなくすと
if(b[0] == a[0]){
b[1]<a[1]
return true
}else{
b[0]<a[0];
return false;
}
こんな感じになって
tureかfalseか返して、同じだった場合二行目をひっくり返している、といった感じでしょうか？

[Usagi365m]

追加分ご丁寧にありがとうございます！
三項演算子はその様になっているのですね、非常に勉強になりました！

Answer 3

ソート関数に使う比較関数を、２番めの数値を対象にするように書けばそうできますね

Comments

[Usagi365m]

アドバイスありがとうございました！