Push swapアルゴリズム実装メモ：座標圧縮の活用

はじめに

42の課題「Push swap」に取り組んだ際の実装メモをまとめました。この記事では、特に座標圧縮テクニックを活用した効率的なソートアルゴリズムの実装方法について解説します。

Push swapとは

Push swapは、2つのスタック（AとB）と限られた操作命令（push, swap, rotate等）を使って、スタックAの要素をソートする課題です。目標は、もともとAにランダムで入っていた整数（int型）を最小限の操作回数でAに昇順にソートすることです。

座標圧縮の必要性

大きな値や範囲の広い値を扱う場合、実際の値ではなく「相対的な大小関係」だけが重要になります。座標圧縮を使うことで数字をindexのように扱えるになります。これはビット演算を使用する基数ソート（Radix Sort）では必須です！！

実装の概要

// 座標圧縮を行う関数
void coordinate_compression(int tab[],  int n)
{
    // 各要素について、自分より大きい要素の数を数える
    for (int i = 0; i < n; i++)
    {
        int rank = 0;
        for (int j = 0; j < n; j++) 
        {
            if (tab[j] < tab[i]) {
                rank++;
            }
        }
        // 自分より小さい要素の数がそのままランク（圧縮後の値）になる
        tab[i] = rank;
    }
}

座標圧縮の考え方：

• 前からランクを付けていく
• ランクは、自分より小さい数字が何個あるかを数える
• 自分より小さい要素が見つかれば、その数をカウント
• 結果、最小値は0、2番目に小さい値は1...と変換される

Push swapでの応用

Push swapでは、入力値を座標圧縮することで、以下の利点があります：

1. 比較の簡素化: 圧縮後の値は0からn-1の連続した整数になるため、比較操作が高速化
2. アルゴリズムの単純化: 大きな数字や負の数を気にせず、インデックスのように扱える
3. メモリ効率: ビット演算やバケットソートなどの最適化が容易になる

実装上の注意点

• 座標圧縮は入力の前処理として一度だけ行う
• 同じ値は同じランクに圧縮される点に注意←扱う前に同じ値があるかCheck！

まとめ

Push swap課題において座標圧縮は非常に強力なテクニックです。入力値の範囲に関係なく、常に0からn-1の整数でアルゴリズムを構築できるため、最適化が容易になります。特に大規模データセットや幅広い値を扱う場合に効果を発揮します。

この手法はPush swapに限らず、競技プログラミングやアルゴリズム実装の様々な場面で活用できる便利なテクニックだと思います！是非ご活用ください！