複数条件によるソート

[keita]

ソートについて悩んでいるので、質問させていただきます。

Cにて、複数条件によるソートを行わせたいと思っています。

コード:

typedef struct {
	char	group;
	short	data;
} stcData;

①groupの昇順ごとにdataを昇順にソート
②groupの昇順、かつ、特定のgroupのdataだけを昇順にソート

dataだけのソートはできるのですが、group毎等の条件が複数あると、
どのように考えればよいのか分からないです。
上記①,②のソートについてお教えいただけないでしょうか？

よろしくお願い致します。

コード:

const int MAX_TARGET = 5;
stcData gTarget[MAX_TARGET];

//データ作成
void gCreateData(int index, char group, short data)
{
	//作成不可
	if((index < 0) | (index >= MAX_TARGET - 1))
		return;
	
	gTarget[index].group = group;
	gTarget[index].data = data;
	
	return;
} //gCreateData


main()
{
	//データ作成
	gCreateData(0, 0, 3);
	gCreateData(1, 1, 2);
	gCreateData(2, 0, 1);
	gCreateData(3, 0, 2);
	gCreateData(4, 1, 1);
	
	//ソート前
	//	index	group	data
	//	0		0		3
	//	1		1		2
	//	2		0		1
	//	3		0		2
	//	4		1		1
	
	//①groupの昇順ごとにdataを昇順にソート
	//ソート後
	//	index	group	data
	//	0		0		1
	//	1		0		2
	//	2		0		3
	//	3		1		1
	//	4		1		2
	
	
	//データリセット
	gCreateData(0, 0, 3);
	gCreateData(1, 1, 2);
	gCreateData(2, 0, 1);
	gCreateData(3, 0, 2);
	gCreateData(4, 1, 1);

	//ソート前
	//	index	group	data
	//	0		0		3
	//	1		1		2
	//	2		0		1
	//	3		0		2
	//	4		1		1

	//②groupの昇順、特定のgroupのdataだけを昇順にソート
	//ソート後
	//	index	group	data
	//	0		0		3
	//	1		0		1
	//	2		0		2
	//	3		1		1
	//	4		1		2
	
} //main

[h2so5]

①の場合は
　Ⅰ　groupの番号でソートしたあと、dataの番号で安定ソートをかける

　Ⅰ　dataの番号でソートしたあと、groupの番号で安定ソートをかける
　Ⅱ　groupの番号でソートしたあと、groupごとに個別にソートする
のどちらか

②の場合は
groupの番号でソートしたあと、groupごとに個別にソートする

という方法が基本的だと思います。

[YuO]

①も②も基本的に何もかわりません。
2つのstcData型のオブジェクトの大小関係をどう定義するかだけの話です。
# qsortにしろC++のstd::sortにしろ，オブジェクトの大小関係を基準としたソートなので。

①であれば，

コード:

int comparer (const void *x, const void *y)
{
  if (x == y) return 0; // 同一オブジェクトなら等しい
  if (x == 0) return -1; // xがヌルでyがヌルでないならyが大きい(逆も可)
  if (y == 0) return 1; // yがヌルでxがヌルでないならxが大きい(逆も可)，ただし上記と整合させること

  const stcData *x0 = (const stcData *)x, *y0 = (const stcData *)y;

  // groupの値が異なる→groupの昇順
  if (x0->group < y0->group) return -1;
  if (x0->group > y0->group) return 1;

  // groupの値が同じ→dataの昇順 ※
  if (x0->data < y0->data) return -1;
  if (x0->data > y0->data) return 1;
  return 0;
}

のような比較関数を用意してqsortに渡すだけになります。
①と②の違いは※部分が違うだけなのですから，※部分でx0->groupなりy0->groupを元にswitch文なりで，
条件によって比較式を決定すればよいです。

[keita]

回答ありがとうございます。
標準関数とYuOさんのコードを参考にすることで、やりたい事は行うことができました。


勉強のために、標準関数を使うのではなく、理解しやすかった挿入ソートを使い自分で作成してみたのですが、
これについてもご指導いただけないでしょうか？

①のgroupの昇順ごとにdataを昇順にソートを行いました。
ソートさせた後のデータを確認すると、期待した並びになっていましたが、
このコードに間違っているところはないでしょうか？

コード:

//データ作成
void gCreateData(int index, char group, short data)
{
	//作成不可
	if((index < 0) | (index > MAX_TARGET - 1))
		return;
	
	gTarget[index].group = group;
	gTarget[index].data = data;
	
	return;
} //gCreateData


void gCopyData(stcData *to, const stcData *from)
{
	to->group = from->group;
	to->data = from->data;
	
	return;
} //gCopyData


//データ出力
void gPrintData(void)
{
	s32 s32i;
	s32i = 0; do{
		printf("%d:(%d,%d)\n", s32i, gTarget[s32i].group, gTarget[s32i].data);
	}while(++s32i < MAX_TARGET);
	
	return;
} //gPrintData


main()
{
	int i, j;
	stcData temp;
	
	//データ作成
	gCreateData(0, 0, 3);
	gCreateData(1, 1, 2);
	gCreateData(2, 0, 1);
	gCreateData(3, 0, 2);
	gCreateData(4, 1, 1);
	
	//ソート前データ
	gPrintData();
	
	//group毎に昇順
	for(i=1; i<MAX_TARGET; i++)
	{
		//これから挿入を行う値を退避する
		gCopyData(&temp, &gTarget[i]);
		
		//左側の整列済み配列に対して、右側から temp との比較を行う
		for(j=i-1; j>=0 && gTarget[j].group>temp.group; j--)
			gCopyData(&gTarget[j + 1], &gTarget[j]);
		
		//挿入する値が比較した配列要素以上ならば、ループを抜けて、その要素の右側に退避した値を代入する
		gCopyData(&gTarget[j + 1], &temp);
	}
	
	//group毎に昇順後
	gPrintData();
	
	//group内のdata毎に昇順
	for(i=1; i<MAX_TARGET; i++)
	{
		//挿入を行う値を退避
		gCopyData(&temp, &gTarget[i]);
		
		//左側の整列済み配列に対して、右側から temp との比較を行う
		for(j=i-1; j>=0 && gTarget[j+1].group==gTarget[j].group && gTarget[j].data>temp.data; j--)
			gCopyData(&gTarget[j + 1], &gTarget[j]);
		
		//挿入する値が比較した配列要素以上ならば、ループを抜けて、その要素の右側に退避した値を代入する
		gCopyData(&gTarget[j + 1], &temp);
	}
	
	//group内のdata毎に昇順後
	gPrintData();
} //main