2026-10-17
sort_by_len.c
#include <stdbool.h>
#include <stddef.h>
bool sort_by_len(const char *words[], size_t n) {
}
文字列の配列 words の先頭 n 個を、文字列の短い順に並べ替える sort_by_len を、標準ライブラリの qsort を使って書いてください。長さが同じ文字列どうしは、並べ替える前の順を保ちます。n が1以下なら何もせずに true を返し、作業用のメモリを確保できなかったときは words を変えずに false を返します。下の例は、呼び出す前と後の words の中身で、どれも戻り値は true です。
入力例 1
{"pear", "fig", "kiwi", "ox", "yam"}
出力例 1
{"ox", "fig", "yam", "pear", "kiwi"}
入力例 2
{"bb", "a", "cc", "d"}
出力例 2
{"a", "d", "bb", "cc"}
入力例 3
{"solo"}
出力例 3
{"solo"}
Reference
#include <stdbool.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
struct item {
const char *s;
size_t pos;
};
static int by_len(const void *a, const void *b) {
const struct item *x = a;
const struct item *y = b;
size_t lx = strlen(x->s);
size_t ly = strlen(y->s);
if (lx != ly) {
return lx < ly ? -1 : 1;
}
return (x->pos > y->pos) - (x->pos < y->pos);
}
bool sort_by_len(const char *words[], size_t n) {
if (n < 2) {
return true;
}
struct item *tmp = calloc(n, sizeof *tmp);
if (tmp == NULL) {
return false;
}
for (size_t i = 0; i < n; i++) {
tmp[i] = (struct item){words[i], i};
}
qsort(tmp, n, sizeof *tmp, by_len);
for (size_t i = 0; i < n; i++) {
words[i] = tmp[i].s;
}
free(tmp);
return true;
}
qsort は安定ソートではありません。C の規格は、比較関数が等しいと判定した2つの要素が結果の中でどの順になるかを定めておらず1、長さだけを比べる比較関数では、"pear" と "kiwi" がどちらの順で出てきても規格どおりです。元の順を保つには、長さが等しい要素どうしでも比較関数が 0 を返さず、元の位置で順を決める必要があります。
ところが、その元の位置は比較関数の引数からは分かりません。qsort は並べ替えの途中で要素を動かすので、比較関数が受け取るポインタのアドレスは、いまどこにあるかを表すだけで、最初にどこにあったかは表していません。そこで参考実装は、文字列と元の添字 pos を組にした struct item の配列を作業用に確保して並べ替え、最後に文字列だけを words へ書き戻します。calloc を使ったのは、n * sizeof *tmp の掛け算が溢れる場合も確保の失敗として扱ってくれるからです。
比較関数は lx - ly を返す形にしていません。長さは size_t なので、lx が小さいときの差は負にならずに大きな正の数になり、それを int に変換した値の符号は当てになりません。pos の比較も、差ではなく2つの比較の結果の差で -1、0、1 を作っています。
掲載したのは参考実装で、唯一の正解ではありません。qsort を使わなくてよければ、左隣の長さが自分より真に大きいときだけ入れ替える挿入ソートでも、作業用のメモリなしで同じ結果になります。
- 規格の
qsortの節には、2つの要素が等しいと比較された場合、並べ替えたあとの配列での順は未規定(unspecified)である、という一文があります。