自分用のメモも兼ねて、C言語での、複数キーに基づくソートのqsort()を使ったシンプルな書き方についてまとめる。
問題設定
C言語を使って、構造体の複数の要素に基づいたソートを行う問題を考える。
例えば、AOJ-ITP2_5_B
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_5_B&lang=jp
Sorting Tuples
n個の品物が与えられます。各品物は{価値、重さ、型、日時、名前}の属性を持ち、これらはそれぞれ整数、整数、英大文字、整数、英小文字の文字列で表されます。 与えられた品物を以下の優先順で出力してください。価値が低い品物を先に出力する
価値が同じ場合は、重さが小さい品物を先に出力する
重さが同じ場合は、型がアルファベット順で小さい品物を先に出力する
型が同じ場合は、日時が早い品物を先に出力する
日時が同じ場合は、名前が辞書順で小さい品物を先に出力する
例
input
10
83 86 L 1524714636915 bm
92 49 H 1524025202362 arzo
40 26 K 1524303455736 iddq
30 62 D 1524145174067 jmowfrxs
11 42 B 1524653377373 befsar
70 13 Y 1524412776091 cdygg
81 5 P 1524937477084 orellnmp
82 45 Q 1524548233367 kho
87 8 M 1524889947178 qhnwn
32 60 E 1524843993368 sqmg
output
11 42 B 1524653377373 befsar
30 62 D 1524145174067 jmowfrxs
32 60 E 1524843993368 sqmg
40 26 K 1524303455736 iddq
70 13 Y 1524412776091 cdygg
81 5 P 1524937477084 orellnmp
82 45 Q 1524548233367 kho
83 86 L 1524714636915 bm
87 8 M 1524889947178 qhnwn
92 49 H 1524025202362 arzo
アプローチ
複数キーでのソートは基本的な話なので、もちろん色々とググれば出てくる。
http://cwnicol.hatenablog.com/entry/2016/04/10/115202
http://f4.aaacafe.ne.jp/~pointc/log241.html
https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1386165513
http://judge.u-aizu.ac.jp/onlinejudge/solution.jsp?pid=ITP2_5_B
しかし、どうにも泥臭かったり拡張性が悪いコードが紹介されているように見える。
キーの数が増えたときも体系的に拡張していけるようなスッキリした書き方はできないか？
さて、やりたいことは要するに、
struct goods{
int value;
int weight;
char type;
long long time;
char name[20];
};
のような構造体を、
value > weight > type > time > name
という優先度で昇順に並び替えること。
単純には、優先度の高いキーから処理してゆき、重複するものについては次の優先度のキーでソートし.....を繰り返せば良い。しかし、for文、if文を連発することなく、「拡張性」のある形で書きたい。
すなわち、構造体に新たに新たに製造場所IDのような属性が加わり
struct goods{
int value;
int weight;
char type;
long long time;
char name[20];
int makeplace; // 追加
};
となったときに、
value > weight > makeplace >type > time > name
というキーの優先度でのソートを実現するのに、既存のコードを変更するのが簡単であって欲しい。
この問題をシンプルに解くポイントは、優先度の高い順ではなく低い順に処理していくという発想。実際、安定なソート (https://ja.wikipedia.org/wiki/安定ソート)
であれば、優先度の低い順に処理していくだけで目的のソートが達成できる。
キーの種類の数はたかがしれているので、キーの種類ごとに全体をソートしても大勢に影響はないはずであり、そしてfor文とif文の山を築くよりも遥かに精神衛生上良い。
というわけで、(マージソートのような)安定なソートを使えばよいことになるが、キーごとにマージソートを書くのはすこぶる面倒。C言語には標準でクイックソートqsort()があるので、これを使って書ければ一番シンプル。
qsort()は安定ではないが、比較関数の部分を工夫すれば簡単に安定化できる。qsort()に突っ込む比較関数の戻り値が0になるような場合に自動で優先度の低いキーの比較関数に切り替えるようなコードを書けば良い。
そして、この優先度の低いキーの比較関数への切り替えは、キーごとの比較関数を持つことで階層的でシンプルな形に書くことができる。
コード
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define REP(i,c) for(int i = 0; i<c; i++)
struct goods{
int value;
int weight;
char type;
long long time;
char name[20];
};
////////// qsort()に渡すための各種比較関数////////////////////
int compareName(const void *a, const void *b){
return strcmp(((struct goods *)a)->name,((struct goods *)b)->name) ;
}
int compareTime(const void *a, const void *b){
long long i = ((struct goods *)a)->time-((struct goods *)b)->time;
if (i == 0){
return compareName(a,b);
}
if (i>0) return 1;
else return -1;
}
int compareType(const void *a, const void *b){
int i = ((struct goods *)a)->type-((struct goods *)b)->type;
if (i == 0){
return compareTime(a,b);
}
return i;
}
int compareWeight(const void *a, const void *b){
int i = ((struct goods *)a)->weight-((struct goods *)b)->weight;
if (i ==0){
return compareType(a,b);
}
return i;
}
int compareValue(const void *a, const void *b){
int i = ((struct goods *)a)->value-((struct goods *)b)->value;
if (i ==0){
return compareWeight(a,b);
}
return i;
}
///////////優先度の低い順に、安定化したqsort()をかける。////////////
void tuple_sort(struct goods *A,int n){
qsort(A,n,sizeof(struct goods),compareName);
qsort(A,n,sizeof(struct goods),compareTime);
qsort(A,n,sizeof(struct goods),compareType);
qsort(A,n,sizeof(struct goods),compareWeight);
qsort(A,n,sizeof(struct goods),compareValue);
}
//////////////////// main()////////////////////
int main(){
int n;
scanf("%d",&n); //入力データの読み込み
struct goods A[100000];
REP(i,n)
{
scanf(" %d %d %c %lld %s",&A[i].value,&A[i].weight, &A[i].type, &A[i].time, A[i].name); //入力データの読み込み
}
tuple_sort(A,n); // <- ソートの実行
REP(i,n)
{
printf("%d %d %c %lld %s\n",A[i].value,A[i].weight, A[i].type, A[i].time, A[i].name);
}
return 0;
}
拡張性
さて、先述の通りに新しい属性makeplaceが加わり、優先度が
value > weight > makeplace >type > time > name
に変わったとしよう。
この変更に伴うソート部分の上記のコードからの修正は実質的に、
int comparePlace(const void *a, const void *b){
int i = ((struct goods *)a)->makeplace-((struct goods *)b)->makeplace;
if (i == 0){
return compareType(a,b);
}
return i;
}
を新たに定義することと、compareWeight()を
int compareWeight(const void *a, const void *b){
int i = ((struct goods *)a)->weight-((struct goods *)b)->weight;
if (i == 0){
return comparePlace(a,b); // <- compareTypeから変更
}
return i;
}
に変更すること、そしてtuple_sort()を
void tuple_sort(struct goods *A,int n){
qsort(A,n,sizeof(struct goods),compareName);
qsort(A,n,sizeof(struct goods),compareTime);
qsort(A,n,sizeof(struct goods),compareType);
qsort(A,n,sizeof(struct goods),comparePlace); // <- NEW!
qsort(A,n,sizeof(struct goods),compareWeight);
qsort(A,n,sizeof(struct goods),compareValue);
}
に変えるだけである。
comparePlace()の定義はほぼcompareWeight()からのコピペで良いことを考えると、すべての変更は15秒もあれば終わってしまう。そして、コピペを除く既存のコードの変更はたったの5行(!)であり、変更に伴うバグの入り込む余地が非常に少ない。