前の記事へのコメントで、時には非難があります-すでに世界で最速のクイックソートがある場合、なぜ他のソートを勉強するのでしょうか。 彼らは、この空想的なエキゾチックはすべて役に立たず、誰も必要としないと言っています。




ソリティアの並べ替えを研究したパーシーディアコニスは、カードのデッキを手動で整理する最も速い方法であると考えています。



そのため、尊敬される数学者（および経験豊富なカード魔術師）が嘘をつかなければ、アルゴリズムの実用的な価値があれば、すべてが整然としています。



手を見てください。

ステージ1.スタックでの敷設

だから、デッキからワームを取ります。 これらは、13個のランダム要素の配列を表します。







カードをいくつかの山に分解して、各山でカードが順序付けられた順序になるようにする必要があります。



つまり、この段階でのタスクは、既存の並べ替えられていない配列からいくつかの順序付けられたサブ配列をすばやく作成することです。 同時に、これらのサブアレイの数が少ないことが非常に望ましいため、サブアレイがより本物であることを保証するよう努力する必要があります。 これは次のように行われます。



最初のカードは最初の山の始まりです。







次のカードがパイルの一番上のカードより小さくなるまで、このパイルにカードを順番に移動します。



さらに、各スタックはスタックです。スタック全体ではなく、その中の一番上のカード（最後に配置されたカード）だけを処理します。







現在のカードがスタックの最小値よりも大きい場合、新しいパイルを作成する必要があり、現在のカードは新しいスタックを開きます。







スタックの順序は重要です！ それらの番号がすでに複数の場合、次のカードを最後の山ではなく、一番左の山に入れます。



今、女性の後、私はどこかに9を添付する必要があります。 機械的に、カードを2番目のパイルに入れたいのですが、最初のパイルでは一番上のカードが9個以上です。 したがって、順序に違反することなく最初のスタックを続行できます。 ちなみに、9つに続く次の3つは、最初の山に行きます。







最初のパイルに7と6を追加することはできません（それらは一番上のカードよりも大きい）が、2番目のパイルにはまだ場所があります。







エースは新しいパイルを開始します。 残りのトライフルは、スタックを挿入できる左端までの距離に応じて、異なるトレイに分類されます。







その結果、カードはいくつかの山に配置されます。 各パイルでは、カードは一番上にある降順で、最小のカードです。 パイルはスタックです。



最初に左側にあるスタックを埋めようとしたため、可能な限り最小の量を形成しました。 配列を調べて、そこから減少するサブ配列を抽出すると、ヒープは自然に大きくなります。

ステージ2.最下行

使用可能な一番上のカードを少し下に移動して、別の列に並ぶようにします。 スタックがスタックの場合、キューと同様に最下行で作業します。







重要なのは、山の中で利用可能な一番上のカードも順番に並んでいるということです。 最下行はすでに昇順でソートされています。 これは驚くことではありません-カードのスタックを形成するとき、小さなカードが左に送られました。



将来的には、ソートが終了するまで、テーブルに配置されているすべてのカードに興味はありません。 これらのみが必要です。

• キューの一番下の行の一番左のカード（現在のカードと呼びましょう）。
• スタックでは、利用可能な一番上のカードでのみ動作します。 この場合、現在のマップの左上に直接配置されているパイルのみが必要です。 この時点で右側にある杭は必要ありません。

下の行では、カードを左から右に並べ替えます。 左端は現在の最小値であり、元の最上行に戻します。 同時に、ベースに別のカードを戻すたびに、別のカードをその場所に置く必要があります。 どこから入手できますか？ 現在のマップの上でその左にあるパイルのうち、使用可能なカードの中で、一番下の行の現在の左のカードの空いている位置に移動し、そこからメインアレイに移動する最小値が選択されます。



配列内の2つはすぐに戻ります。 空いた場所はトリプルによって取得され（最初のパイルから一番下の行に移動します）、現在の最小値がメインアレイに移動するときに一番下の行からトリプルが取得されます。 最初の2つのパイルでは、最小値が再度検索されます-これは4つで、これも帰宅します。 現在の最小値は5などです。







昇順の順序と降順の順序で積み重ねられた順序で作業を組み合わせると、すべての要素が最小から最大に非常に迅速に取得されます。 一般的にそのようなもの。



このプロセスのアニメーション。







上記のすべてをPythonに変換すると、次のようになります。

from functools import total_ordering from bisect import bisect_left from heapq import merge @total_ordering class Pile(list): def __lt__(self, other): return self[-1] < other[-1] def __eq__(self, other): return self[-1] == other[-1] def patience_sort(n): piles = [] # sort into piles for x in n: new_pile = Pile([x]) i = bisect_left(piles, new_pile) if i != len(piles): piles[i].append(x) else: piles.append(new_pile) # use a heap-based merge to merge piles efficiently n[:] = merge(*[reversed(pile) for pile in piles])
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

参照資料

忍耐強いソート （ Google-translate ）



忍耐ソートソース



プリンストンCS：最長増加部分列



忍耐ソートパイルの組み合わせ （ Google-translate ）



Wikiノート：患者のソート



Word Aligned （ Google-translate ）

シリーズ記事：

• ExcelアプリケーションAlgoLab.xlsm
• 交換ソート
• 挿入ソート
  • 司書の並べ替え
  • ソリティアソート
  • 「ハノイの塔」を並べ替える
  • 若いテーブルの並べ替え
  • ソートを反転
  • ソート比較の挿入
• 選択で並べ替え
• ソートのマージ
• 分布で並べ替え

AlgoLabアプリケーションでは、このソートがアクティブになりました。 同時に、マップの形式（デフォルトモード）と単純な数字の形式の2つのモードで視覚化が可能です。 ただし、カードスタイルの場合、配列の最大要素と最小要素の差が54（2つのジョーカーを含むデッキ内のカードの数）未満である必要があります。 この条件が満たされない場合、またはカードモードが完全にオフになっている場合（このため、セルのコメントにソート名を付けてcard = 0と記述する必要があります）、視覚化は鈍い数字の形式になります。







スーツは、年功序列の順に考慮されます： ピーク<クラブ<タンバリン<心。







つまり、タンバリンのタンバリンスーツのカードは、クラブスーツのカードよりも大きく、ハートスーツのカードは、ピークスーツのカードよりも大きくなります 。 数字で類推すると、ピークは0から9、クラブは10から19、ダイアモンドは20から29、ハートは30から39です（もちろん、スーツの中ではカードの数は正確には10ではありませんが、意味を理解します）。 スーツ内の年功に関しては、それは普通のことです：デュースからエースまで。 また、他のすべてのカードよりも古いジョーカーを取ることもできます。 この場合、赤いジョーカーは黒よりも重くなります。

この記事は、最近Web サイトを再設計したプロのWeb開発会社であるEDISON Softwareの支援を受けて作成されました。