文字列メソッド・配列なしでJavaScriptの整数の桁を並べ替える方法

問題の概要

数値を引数として受け取り、その桁を並べ替えて作れる「最小の数」を返すJavaScript関数を作成します。

たとえば、入力が次の数値だった場合：

const num = 614532;

出力は次のようになります：

const output = 123456;

制約条件

この問題には重要な条件があります。Stringオブジェクトのメソッドは一切使えず、データの格納に配列も使用できないという点です。つまり、純粋な数値演算だけで各桁を並べ替える必要があります。

実装コード

const num = 614532;
const sortDigits = num => {
    const getDigit = e => Math.floor(num / 10 ** e) % 10;
    const l = Math.ceil(Math.log10(num)) − 1;
    let e = l;
    while (e−−) {
        const left = getDigit(e + 1);
        const right = getDigit(e);
        if (left <= right){
            continue;
        };
        num += (right − left) * 9 * 10 ** e;
        e = l;
    };
    return num;
}
console.log(sortDigits(num));

出力結果

コンソールには次のように表示されます：

123456

コードの解説

このアルゴリズムのポイントは以下の通りです。

1. 桁の取り出し（getDigit関数）

Math.floorと剰余演算（%）を組み合わせることで、指定した位の桁を数値のまま取り出しています。Math.floor(num / 10 ** e) % 10により、10のe乗の位の数字だけを抽出でき、文字列への変換は一切不要です。

2. 桁数の算出

Math.log10で常用対数を求め、Math.ceilして1を引くことで、最上位の桁の指数を導き出しています。これによりループの開始位置が決まります。

3. 隣接桁の交換

より上位の桁（left）が下位の桁（right）より大きい場合、num += (right − left) * 9 * 10 ** eという式で2つの桁を入れ替えます。この式は、2桁の差分を一括して補正することでスワップと同じ効果を実現する巧妙なテクニックです。考え方としてはバブルソートと同じです。

4. 繰り返し処理

交換が発生した場合は、最上位から再度チェックを行うためeを初期化してやり直します。すべての桁が昇順に並ぶまで処理を繰り返すことで、結果的に最小の数が完成します。

なお、この手法の計算量はバブルソートと同様に最悪ケースでO(n²)となりますが、桁数は高々10桁程度であるため、実用上は十分高速に動作します。