読者です 読者をやめる 読者になる 読者になる

トランプの並び替え

programming

大富豪をやれば、その人が好きな
ソートアルゴリズムが分かる


よく「ソート」の例にトランプ(手札)の並び替えとかが出てきますが、
実際のところ、手札の並び替えにはどんなアルゴリズムを使うのが良いんでしょうか。
とりあえず、手札の枚数を N とします。

バブルソート

概要 :「隣との大小関係を比較して、おかしければ入れ替える」を繰り返す。
計算量:O(N^2)
考察 :実際にやっている人はほぼいないと思う

挿入ソート

概要 :「カードを取り出して、そのカードを正しい位置に挿入する」を繰り返す
計算量:O(N^2)
(トランプなら二分探索も挿入も一瞬で出来るので、O(N log N)?)
考察 :だいたいの人はこれ。時間もかなり短いはず。

クイックソート

概要 :最強最速のアルゴリズム!?
計算量:O(N log N)
考察 :やってる人はまあいないでしょう。
手札の枚数が多くなると実力を発揮する。逆に少ないと、定数項の不利を挽回できない。

マージソート

概要 :半分、半分の半分・・・に分割していき、合体させていく。
計算量:O(N log N)
考察 :リフトシャッフルならやるけど・・・

ヒープソート

概要 :ヒープに入れていき、取り出していく。
計算量:O(N log N)
考察 :やってる人がいたらシュールw ・・・今度やってみようw

バケットソート

概要 :"A"の山、"2"の山、"3"の山・・・"K"の山、のように仕分けをして最後に合体
計算量:O(N)
考察 :挿入ソートと並んで実際にやってる人が多いソート。
カードの種類が少ないので可能で、手札の枚数が多くなったときにはこのアルゴリズムがbestだろう。

ボゴソート

概要 :正しくなるまで、シャッフル
計算量:O(運次第さ!) (平均計算時間はO(n*n!)らしい)
考察 :やってたら殺されそうw