JavaScriptでスタックの要素を再帰的に並べ替える方法

はじめに

本記事では、整数の配列（スタックとして扱う）を受け取り、再帰処理とpush・popメソッドのみを使って、その配列をその場（in-place）で昇順に並べ替えるJavaScript関数を実装する方法を解説します。

このアルゴリズムのポイントは、以下の2つの再帰関数を組み合わせる点にあります。

• sortStack：スタックから要素を1つずつ取り出し（pop）、残りのスタックを再帰的に並べ替えてから、要素を適切な位置に挿し戻します。
• sortedInsert：指定した要素を、スタックが空になるか、スタック末尾の要素より大きくなるまで再帰的にpopし、正しい位置に挿入します。

サンプルコード

実際のコードは次のようになります。

const stack = [-3, 14, 18, -5, 30];

// スタック全体を並べ替える関数
const sortStack = (stack = []) => {
    if (stack.length > 0) {
        let t = stack.pop();       // 先頭の要素を取り出す
        sortStack(stack);          // 残りのスタックを再帰的にソート
        sortedInsert(stack, t);    // 取り出した要素を正しい位置に挿入
    };
}

// 要素をソート済みの位置へ再帰的に挿入する関数
const sortedInsert = (stack, e) => {
    if (stack.length == 0 || e > stack[stack.length - 1]) {
        stack.push(e);             // スタックが空、または挿入位置に達したら追加
    } else {
        let x = stack.pop();       // 条件を満たすまで要素を退避
        sortedInsert(stack, e);
        stack.push(x);             // 退避していた要素を元に戻す
    }
}

sortStack(stack);
console.log(stack);

実行結果

コンソールには次のように出力されます。

[ -5, -3, 14, 18, 30 ]

処理の流れと計算量

このアルゴリズムは「挿入ソート」を再帰で表現したものです。各要素を挿入するたびに最大でO(n)回のpop/pushが発生し得るため、全体的な時間計算量はO(n²)となります。一方で、補助的な配列や一時変数をほとんど使わずに済むため、空間効率に優れたin-placeなソートとして知られています。

再帰の仕組みを理解する練習問題としても非常に良い題材なので、ぜひ自分でも動きを追ってみてください。