忍耐の選別

コンピュータサイエンスにおいて、ペイシェント ソートは、カードゲームのペイシェントにヒントを得てその名が付けられたソート アルゴリズムです。このアルゴリズムのバリエーションは、指定された配列内の最長の増加部分列の長さを効率的に計算します。

このアルゴリズムの名前は、忍耐カードゲームの簡略版に由来しています。ゲームはシャッフルされたカードのデッキから始まります。カードは、以下のルールに従って、テーブル上の一連の山に 1 枚ずつ配られます。^[2]

1. 最初は山札はありません。最初に配られたカードは、1 枚のカードからなる新しい山札を形成します。
2. 後続の各カードは、一番上のカードの値が新しいカードの値以上である既存の山札の一番左に置かれるか、既存の山札すべての右側に置かれ、新しい山札が形成されます。
3. 配るカードがなくなるとゲームは終了します。

このカード ゲームは、次のように 2 段階のソート アルゴリズムに変換されます。完全に順序付けられたドメインからのn要素の配列が与えられたら、この配列をカードのコレクションと見なし、忍耐ソート ゲームをシミュレートします。ゲームが終了したら、最小の可視カードを繰り返し選択してソートされたシーケンスを復元します。つまり、それぞれが内部的にソートされている p個の山のk方向マージを実行します。

ペイシェントソートの最初のフェーズであるカードゲームのシミュレーションは、n要素の入力配列に対して最悪の場合でもO(nlogn)回の比較を行うように実装できます。つまり、最大でn個の山があり、その構造上、山の一番上のカードは左から右に向かって増加するシーケンスを形成するため、バイナリ検索によって目的の山を見つけることができます。^{[1] 2番目のフェーズである山のマージも、}優先キューを使用して時間内に実行できます。^[1]${\displaystyle O(n\log n)}$

入力データに自然な「連続」、つまり非減少サブ配列が含まれている場合、パフォーマンスは確実に向上します。実際、入力配列がすでにソートされている場合、すべての値が 1 つの山を形成し、両方のフェーズがO ( n )時間で実行されます。平均的なケースの複雑さは依然としてO ( n log n )です。つまり、均一にランダムな値のシーケンスは、予想される数の山を生成します^[3]。これは、生成とマージに時間がかかります。^[1]${\displaystyle O({\sqrt {n}})}$${\displaystyle O(n\log {\sqrt {n}})=O(n\log n)}$

チャンドラムーリとゴールドスタインは、ペイシエントソートの実際のパフォーマンスの評価を行っており、ベンチマーク問題では、ナイーブバージョンは最先端のクイックソートよりも約 10 ～ 20 倍遅いことを示しています。彼らは、この原因をペイシエントソートに関する研究が比較的少ないことと見なし、そのパフォーマンスをクイックソートの 2 倍以内に抑えるいくつかの最適化を開発しました。^[1]

カードの値が1, . . . , nの範囲にある場合、ファン・エムデ・ボアズ木に依存して、カードを山に積むための最悪の実行時間で効率的な実装があります。^[3]${\displaystyle O(n\log n)}$

忍耐ソートはフロイドのゲームと呼ばれるカードゲームと密接に関係しています。このゲームは、前に描いたゲームと非常によく似ています: ^[2]

1. 最初に配られたカードは、1 枚のカードで構成される新しい山を形成します。
2. 後続の各カードは、新しいカードの値以上の値を持つ最上位カードを持つ既存の山札の上に置かれるか、既存のすべての山札の右側に置かれ、新しい山札が形成されます。
3. 配るカードがなくなるとゲームは終了します。

ゲームの目的は、できるだけ少ない山でゲームを終了することです。忍耐ソート アルゴリズムとの違いは、新しいカードを左端の山に置くことが許可されている場合はそこに置かなくてもよいことです。忍耐ソートは、このゲームをプレイするための 貪欲な戦略です。

アルダスとディアコニスは、 n = 52の場合、9個以下の山を勝利結果と定義することを提案しており、これは約5%の確率で発生します。^[4]

まず、上記のようにソート アルゴリズムを実行します。山の数は、最長の部分列の長さです。カードが山の一番上に置かれるたびに、前の山の一番上のカード (新しいカードよりも低い値を持つと想定) へのバック ポインタを配置します。最後に、最後の山の一番上のカードからのバック ポインタをたどって、最長の長さの減少する部分列を復元します。その逆は、最長の増加部分列アルゴリズムの答えです。

S. BespamyatnikhとM. Segal ^[3]は、ソートアルゴリズムに比べて追加の漸近コストが発生しないアルゴリズムの効率的な実装について説明しています（バックポインタの保存、作成、および走査には線形の時間と空間が必要です）。彼らはさらに、同じ結果のデータ構造からすべての最長増加サブシーケンスを報告する方法を示しています。

ペイシェンス・ソーティングはCLマローズによって命名され、1960年代初頭にASCロスが発明したとされています。^[1] アルダスとディアコニスによると、^[4]ペイシェンス・ソーティングは、最長の増加部分列の長さを計算するアルゴリズムとして最初にハマーズリーによって認識されました。^[5] ASCロスと独立してロバート・W・フロイドは、それをソートアルゴリズムとして認識しました。最初の分析はマローズによって行われました。^{[6]フロイドのゲームは、}ドナルド・クヌースとのやり取りの中でフロイドによって開発されました。^[2]

忍耐ソートアルゴリズムはプロセス制御に適用できます。一連の測定において、長い増加部分列の存在はトレンドマーカーとして使用できます。2002 年の SQL Server マガジンの記事には、このコンテキストで、最長の増加部分列の長さに対する忍耐ソートアルゴリズムの SQL 実装が含まれています。^[7]

Wikibookアルゴリズム実装には、Patience Sortingに関するページがあります。