Clever Geek Handbook

デビッドモーガンマールによる難解な並べ替え









彼は、ブッチャーのマージによる奇偶ソートについてではなく、最悪の場合はデカルトツリーによるソートについて、そのような非常にクレイジーなものについて書くことを計画していました。 しかし、その後、一連のお祝いが来ていることを思い出しました。つまり、お祝いの何かを提供する価値があることを意味します-軽薄です。







デビッド・モーガン・マー













オーストラリアの面白いオタク、天体物理学者、数学者、プログラマー、発明家。 現在はキヤノンの従業員であるIBMで働くことができました。 漫画、スターウォーズ、旅行、異常なコーディング、GURPSの世界が好きです。 いくつかの難解なプログラミング言語（ Chef 、ZOMBIE、 Pietなど）の著者。



David Morgan-Maraの個人Webサイトには、「難解な選別」の小さなセレクションがありますが、それについては言うまでもありません。




そろばんソート

（そろばんソート）





自然数のセットをソートするとします。 それらを適切な量の小石の水平列の形で互いの下にレイアウトします。 停止するまで垂直に移動します。



実際にはそれだけです。



各水平列の小石を数えると、順序付けられた状態で最初の数字のセットを取得します。



この並べ替えについてはすでに詳細に書いているので、すぐに次の並べ替えに進みます。







沼地のグレーディング（Bogobogosort）



伝統的に、いわゆる沼ソート（Bogosort）は最も遅いソートと見なされます。







要素が並べられるまで配列をシャッフルします。 時間の複雑さはO（nxn！）です。



もちろん、非常に遅いアルゴリズムは生産性をさらに低下させる可能性があります。 順序付けのためにサブアレイをチェックするときに末尾再帰がBogosortに追加されると、最も大きな沼地でさえ、さらに大きな泥沼にdrれかねません。 確認済みのサブアレイを再帰的に複製し、元のサブアレイと一致するまで並べ替える場合、メモリから複雑さを大幅に改善できます。



基本的な手順は、Bogosortの場合と同じです。



  1. 配列がソートされているかどうかを確認してください。
  2. そうでない場合は、混合してポイント1に戻ります。


ただし、配列の順序の確認は次のとおりです。



  1. 配列のコピーが作成されます。
  2. コピーの最初のn-1個の要素は、Bogobogosortを使用してソートされます。
  3. コピーに最初のn-1要素よりもn番目の要素があるかどうかを確認します。
  4. そうでない場合は、配列のコピーをシャッフルし、手順2に戻ります。
  5. はいの場合、コピーがオリジナルと一致するかどうかを確認する必要があります。 一致する場合、配列は何に関係なくソートされ、そうでない場合は、配列のコピーをシャッフルし、ステップ2に進みます。


データのそのような洗練されたock笑は、プロセスが非常に長い間続くことを実際に保証します。



アルゴリズムを理解していなかった人、ここに実装があります 
import java.util.ArrayList; import java.util.Collections; import java.util.List; public class Bogobogosort { public static <T extends Comparable<T>> void sort(List<T> list) { if (list.size() <= 1) return; while (!isSorted(list)) Collections.shuffle(list); } public static <T extends Comparable<T>> boolean isSorted(List<T> list) { List<T> copy = new ArrayList<>(list); List<T> subList; do { Collections.shuffle(copy); subList = copy.subList(0, copy.size() - 1); sort(subList); } while (copy.get(copy.size() - 1).compareTo(subList.get(subList.size() - 1)) < 0); return copy.equals(list); } } /*  : https://github.com/lucaswerkmeister/Miscellaneous/blob/master/Sorting/src/Bogobogosort.java */




時間の複雑さに関して、DavidはどこかがO（n！ N！ ）のオーダーであると信じています。 7つの要素の配列で最終結果をテストするとき、彼は待ちませんでした。




マクスウェルの悪魔の並べ替え



分類方法は、19世紀のジェームズ・クラーク・マクスウェルの偉大な英国の物理学者の有名な思考実験に基づいています。 科学技術の現在の成果に基づくこのハードウェア実装方法は、非常に問題があります。



ガス容器は、不浸透性の壁によって2つの半分に分割されています。 壁には穴があり、そこにはマクスウェルの悪魔と呼ばれる特別な装置が装備されています。 悪魔は、穴を左から右へは高速（高温）の分子のみを通過させ、右から左へは低速（低温）の分子のみを通過させるように設計されています。



このシステムの機能の結果、パラドックスは熱力学の第二法則に違反すると言われています：容器では、内部エネルギーのみにより、追加のエネルギーを引き付けることなく、左側が冷却され、右側が加熱されます。











ガスの入った容器を取り、すべての分子を未分類の数字のセットとみなします（それぞれは分子のエネルギーの一種の反射です）。 マックスウェルの悪魔が組み込まれた壁で船をブロックしましょう。 しばらくすると、分子が容器の右側に集まり、そのエネルギーは特定の所定の値を超える（または等しい）ようになり、左側の分子はエネルギーがこの値より小さくなる。



マックスウェルデーモンが組み込まれた壁（他の帯域幅が設定されている）を使用して、容器の各半分を半分に分割します。 したがって、分子をさらに「熱い」ものと「冷たい」ものに分配します。 そして、制限された部分のそれぞれに同じエネルギーを持つ分子ができるまで、マックスウェルの悪魔が組み込まれた追加の壁で容器内の空間を分割します。 この時点で、すべてのパーティクルが「ソート」されます。



ジャレッド・ダイアモンドの種類




Jared Diamondの銃、細菌、鋼鉄に基づくアルゴリズム：人間の文明の運命（銃、細菌、鋼鉄：人間社会の運命）。



ピューリッツァー賞を受賞したこの作品は、過去10年半にわたる地理人類学の最も重要な作品です。 この本は、社会学者、歴史家、人口統計学者から高く評価されていました。 感銘を受けたのはビル・ゲイツであり、グローバルなプロセスを理解した最後の人ではありません。「この本は人類の歴史を理解するための基礎を築きます。」



関係する側面が広大であるため、この短い記事の狭い枠組みの中で、本で提示されたアイデアを簡単に言い直すことさえできません。 2005年にWorld Wide WebのNational Geographicチャンネルで撮影された3エピソードのドキュメンタリーだけでなく、興味のある人は本自体を簡単に見つけることができます。



これでアルゴリズム。



ソートされたリストの各番号について、狩猟採集民の原始文明を定義し、それらの展開地域には野生動物（その後の飼いならしのため）と植物（農業の発展のため）が生息します。 各地元の人間の人口のサイズ、動植物の種の多様性-対応する数に正比例して選択する。



農業、産業、科学、文化を発展させてください。 銃器を発明し、最初に大量に使用し始めた社会は、リスト内の最大の要素に対応し、それに関して他のすべての要素が時間の経過とともに整理されます。



実行時間は最大数の値のみに依存するため、時間の複雑さO（1）を正式に述べることができます。 現時点では、このソートを使用する信頼できるケースは1つしか知られていないため、費やされる時間は約13,000年です。 配列の最大要素が大きい場合、この値は小さくなります。



ドロップソート



安くて陽気です：配列を調べ、途中で並べ替えられていない要素を削除（破棄）します。







ちなみに、時間の複雑さO（n）のハッキングは非常に便利です。 感謝できません。



ハノイの塔ソート




フランスの数学者エドワード・ルークの有名なパズルに基づいた分類アルゴリズム。



入力値を変更するだけです。最初のシャフトのディスクは「大きいよりも小さい」順序である必要はありません。 残りのルールはクラシックのように残します-一度に転送できるのは一度に1つのディスクのみで、小さなサイズのディスクには大きな直径の「パンケーキ」を置くことはできません。 ディスクをあるロッドから別のロッドに移動して、最終的にそれらを規則正しいサイズの順序で収集することが必要です。



退化するケースは...完全に順序付けられた配列であるため、このソートは興味深いものです。 次に、2 n -1の移動を実行する必要がある参照「ハノイ」を扱います。 時間の最良の場合は逆です;この場合、要素はすぐに次々とその場所にジャンプします。 そして一般的に、配列がソートされた状態に近ければ近いほど悪くなり、逆もまた同じです！



インテリジェントデザインソート




サイズnの配列の場合、n！ 要素の順列、その中の要素がそれらが従う順序で正確に従う確率は1 / nに等しい！ それは非常に小さいです。 このような配列状態が偶然に発生したと主張するのはばかげています。



配列を作成し、その中の要素を特定の順序で配置する特定のより高い合理的な力があると仮定することは、はるかに論理的です。 この順序が最適ではないと主張する理由はありません。 最も可能性が高いのは、構造に関する要素が既に必要な順序で正確に構築されていることです。たとえこれが、順序に関する世俗的で不完全なアイデアと矛盾していてもです。



さらに、配列を並べ替えようとすると、元々配列されていた完全性に違反することになります。


More articles:


All Articles