Namaran

Code daily. Without assist.

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 を使わなくてよければ、左隣の長さが自分より真に大きいときだけ入れ替える挿入ソートでも、作業用のメモリなしで同じ結果になります。

  1. 規格の qsort の節には、2つの要素が等しいと比較された場合、並べ替えたあとの配列での順は未規定(unspecified)である、という一文があります。