qsortで並べ替える
並べ替えは自分で書かなくてよい
点数順に並べたいたびにバブルソートを書くのは無駄です。標準ライブラリには qsort があり、stdlib.h を読み込めばそのまま使えます。
c
qsort(list, n, sizeof(Student), cmp_by_score);引数は順に、先頭の番地、要素の個数、要素 1 個のバイト数、比較関数です。qsort は要素が何の型かを知りません。先頭の番地と 1 個の大きさが分かれば、i 番目の位置は計算できますし、入れ替えもバイト単位でできるからです。だから 3 番目の sizeof(Student) を間違えると、構造体の途中で切った変な入れ替えが起きます。
比較関数は const void * で受け取る
型を知らない qsort から呼ばれるので、比較関数の引数もどんな型でも受けられる const void * になります。中で自分の型に戻してから使います。
c
int cmp_by_score(const void *a, const void *b) {
const Student *x = (const Student *)a;
const Student *y = (const Student *)b;
if (x->score != y->score) {
return y->score - x->score;
}
return strcmp(x->name, y->name);
}戻り値で見られているのは符号だけです。負なら前の引数が先、正なら後ろの引数が先、0 なら順序を決めないという意味になります。-1 0 1 を返す必要はありません。
昇順にしたいなら x - y、降順にしたいなら y - x です。ここでは点数の高い順に出したいので y->score - x->score にしています。なお引き算で符号を作れるのは、値の幅が小さくて桁あふれしないと分かっている場合だけです。点数のように 0 から 100 なら安全ですが、int の全域を取りうる値では if で大小を比べて -1 と 1 を返す形にします。
同点があるなら、第 2 のキーまで決める
qsort は安定ではありません。安定とは「比較で 0 になった要素どうしの元の並びが保たれること」で、qsort はこれを保証しません。同点の学生が 2 人いるとき、どちらが先に出るかは処理系の都合で変わります。手元で動かして出た並びが、別の環境でも同じとはかぎりません。
これを避けるには、並びが一意に決まるところまで比較を書き足します。上の関数が、点数が等しいときに strcmp で名前を比べているのがそれです。点数が同じで名前も同じ学生がいないかぎり、どの環境でも同じ並びになります。
strcmp はバイトの並びを前から比べて符号を返す関数なので、そのまま比較関数の戻り値として使えます。名前を半角英字にしておくと、この比較がそのまま辞書順になります。
何が並び替えられるか
qsort は渡された領域の中身を直接入れ替えます。今回のように malloc で借りた構造体の配列でも、普通の配列でも、どちらでも同じように使えます。並べ替えたあとで元の順序に戻したいなら、自分で控えを取っておくしかありません。
要件
- 比較関数は const void * を2つ受け取り、中で const Student * にキャストする
- 点数が違うときは高い順になる符号を返す
- 点数が同じときは strcmp で名前を比べた結果を返す
- qsort に先頭の番地、人数、sizeof(Student)、比較関数を渡す
ヒント
