Geekly Articles each Day

非実用的なソート-無意味で容赦ない

画像

そして、スマートで効率的なアルゴリズムとは何ですか？ そして、この退屈な秋の金曜日を非生産的なもので追い払おう！？

これまでで最も型破りなソーティングのトップ5をご紹介します。

これは、若いプログラマーが教訓的な目的で示すのに役立ちます。 残りはすべて面白くなります。


スワンプソート（BogoSort）


画像
このソートでは、非常に注意する必要があります。 泥沼に不注意で上陸すると、永遠に滅びる危険があります。

原理は金型のように単純です。 突然ソートされるまでアレイを振ってください。 このプロセスはすぐに終了することも、宇宙の熱死まで続くこともあります。 それはとても幸運です。



平均時間の複雑さ：O（nxn！）。 より良いものもあります：Ω（n）。 興味深いことに、このアルゴリズムの最悪の時間的複雑さは科学には知られていません。

きちんと。 立ち往生するコード。
import java.util.Random; public class BogoSortAlgorithm extends SortAlgorithm { //  ,     public void sort(int data[]) throws Exception { if (data.length > 0) runBogoSort(data); } //     private void runBogoSort(int data[]) throws Exception { Random generator; int tempVariable; int randomPosition; do { generator = new Random(); for (int i = 0; i < data.length; i++) { randomPosition = generator.nextInt(data.length); tempVariable = data[i]; data[i] = data[randomPosition]; data[randomPosition] = tempVariable; pause(i,randomPosition); } } while(!isSorted(data)); //   } //,    private boolean isSorted(int data[]) { for (int i = 1; i < data.length; i++) if (data[i] < data[i - 1]) return false; return true; } }



ボゾピエロソート（BozoSort）


画像
BogoSortには、BozoSortがあります。 Bozoのベビーピエロの選別方法は、3歳の子供でも簡単に説明できます。 2つの要素をランダムに選択して交換し、これが成功につながったかどうかを確認します。 そうでない場合は、最後まで同じアクションを繰り返します。



BozoSortはBogoSortと同じように見えるかもしれませんが、一見しただけです。 Clown BozoはOの平均時間複雑度でソートします（nxn！）そして、これも上限時間です。

UPD。 burdakovdとSkidanovAlexがコメントとプライベートメッセージで正しく指摘したように、BogoSortのようなBozoの道化師の分類には、最悪の時間の複雑さに対する上限はありません。 実際、最悪の場合、並べ替えられていない配列の場合、それはどこから来ますか？ランダムは同じ2つの要素を永遠に交換します！？

それにも関わらず、BozoSortは平均してBogoSortよりも高速にソートされます。 交換のたびに配列の順序がチェックされるためです。 BogoSortでは、配列が順序付けられた状態になる場合がよくありますが、この時点で確認せずにさらに混ぜると、ソートの目的の状態がしばらく失われます。


Clown Bozoもきらきらとプログラミングしています。
 import java.util.Random; class BozoSortAlgorithm extends SortAlgorithm { void sort(int a[]) throws Exception { boolean sorted = false; //    while (!sorted) { //    ... int index1 = Randomize(a.length); int index2 = Randomize(a.length); //...     int temp = a[index2]; a[index2] = a[index1]; a[index1] = temp; pause(index1, index2); //? sorted = true; for (int i = 1; i < a.length; i++) { if (a[i-1] > a[i]) { pause(i, i-1); sorted = false; break; } } } } //     private int Randomize( int range ) { double rawResult; rawResult = Math.random(); return (int) (rawResult * range); } }



順列ソート（PermSort）


画像
組み合わせ論のプリズムをソートするタスクを見てみましょう。 任意の配列は、n！個の要素の通常の有限集合です。 順列。 それらのいくつかは、順序付けられた状態の配列です。 すべての順列を列挙するアルゴリズムをコンパイルすると、必然的に同じものが見つかります。



Bozoピエロのような最悪の時間の難易度はO（n x n！）です。 しかし、最高のものが優れている-O（n）。

配列のすべての順列のエレガントな列挙。
 class PermSortAlgorithm extends SortAlgorithm { // ? boolean issorted(int a[], int i) throws Exception { for (int j = a.length-1; j > 0; j--) { //    -  compex(j, j - 1); if(a[j] < a[j - 1]) { return false; } } return true; } // PermSort boolean sort(int a[], int i) throws Exception { int j; //     if (issorted(a, i)) { return true; } //   . //    . for(j = i+1; j < a.length; j++) { compex(i, j); //-  int T = a[i]; a[i] = a[j]; a[j] = T; //    if(sort(a, i + 1)) { return true; } //    T = a[i]; a[i] = a[j]; a[j] = T; } return false; } //      PermSort. void sort(int a[]) throws Exception { sort(a, 0); } }



愚かな並べ替え（Stooge sort）


画像
並べ替えの名前は、1930年代初頭から1960年代後半まで、前世紀にアメリカ国民を楽しませた漫画劇団Three Stoogesにちなんで名付けられました。 ちなみに、合計6つの「ばか」がありました; 40年以上の創造的な活動で、トリオの構成は時々変わりました。

陽気な三位一体は、茶番とピエロに特化しています。 並べ替えも動作します。似顔絵のキャラクターのように、彼女は狂ったように配列を駆け回っています。 主人公とのばかげた冒険の後、すべてが大丈夫です。 配列がソートされ、ハッピーエンド。

アルゴリズムは機知に富んだ再帰的です。
 class StoogeSortAlgorithm extends SortAlgorithm { void sort(int a[], int lo, int hi) throws Exception { ///     if(a[lo] > a[hi]) { int T = a[lo]; a[lo] = a[hi]; a[hi] = T; } // ? if(lo + 1 >= hi) return; //   ? int third = (hi - lo + 1) / 3; sort(a, lo, hi - third); //  2/3  sort(a, lo + third, hi); //  2/3  sort(a, lo, hi - third); //  2/3  } //     void sort(int a[]) throws Exception { sort(a, 0, a.length-1); } }





配列のセグメント（最初は配列全体）を取得し、セグメントの両端の要素を比較します。 左が右よりも大きい場合、もちろん、場所を入れ替えます。
次に、セグメントに少なくとも3つの要素がある場合、次のようになります。
1）セグメントの最初の2/3に対してStooge sortを呼び出します。
2）セグメントの最後の2/3でStooge sortを呼び出します。
3）セグメントの最初の2/3に対してStooge sortを再度呼び出します。

アルゴリズムの複雑さは印象的に計算されます ：O（n log 3 / log 1.5 ）。 これらは泥だらけのO（n）ではありません。

Babushkinaの並べ替え（Babushkin sort）


画像
Babushkin自身は直接メソッドの作成者ではありませんが、アルゴリズムの基礎を形成したのはAlexeyの深いアイデアでした。

おばあちゃんに関する簡単な情報
起業家、イノベーター、バルナウル出身のプログラマー、Alexey Babushkin。 アルタイ州立工科大学の4年生。

才能のある学童と若者のための地域教育プログラム「アルタイの未来」への参加者。 Start in Scienceコンテストの優勝者。

科学技術分野における中小企業の発展を促進するために基金が実施したプログラム「U.M.N.I.K.」の助成金。

特許取得済みのウイルス対策イミュニティの開発者。 オリジナルのFlashマーカーガジェットの作成者。 ファイルをアーカイブするための根本的に新しいアルゴリズムの作成者。

Microsoftの招待で、彼はWindows 8のベータ版のテストに直接関与していました。

Babushkinによって提案された根本的に新しいファイルアーカイブアルゴリズム
アーカイブアルゴリズムは次のとおりです。任意のファイルは16進数の文字列であり、この16進数をDECに変換し、致命的ではない大きな数値を取得し、その前に数値0を追加します。ちょうど-このような整数を2つ選択します。その商は、最後の文字との一致の精度で、0〜1の範囲の目的の数値を提供します。 問題は、最大2時間、最大2週間かかる可能性のある数字の選択にあります。 プロトタイプと動作するプログラムがあり、すべて機能します。

アレクセイ・バブッシュキン

n個の要素の配列が与えられます。 その場所での要素の変位のシーケンスは、一連のn-ric 1桁の数字として表すことができます。 このシーケンスは、複数桁のn-ric番号と考えることもできます（これをBabushkinの番号と呼びます）。 この数値の各ビットは、次の要素を挿入する配列の位置のインデックスです。 そのような番号を取得する方法は？ 祖母の番号を10進数形式で表す場合、大きな（または配列のサイズに依存しない）数値を取得し、この前に数値0を追加し、0から1の範囲の小数部を特定の小数点以下の桁数で取得し、簡単です-そのような整数を2つ選択します。その商は、0から1の範囲で、最後の文字と一致する精度で必要な数を与えます。 Babushkinの数を与える2つの商数を見つけます-配列を順序付ける順列のシーケンスを自動的に取得します。



誰かに何かはっきりしないことがありますか？ Babushkinaをステップごとに並べ替える：

1）n個の要素の配列をソートするとします（インデックス付けは0から始まり、最後の要素のインデックスはn-1です）。
2）2つの相互に単純な10進数xとy（x <y）を選択します。
3）xをyで割ります。 0から1の小数を取得します。ゼロをドロップし、小数部分を残します。 実際、特定の10進整数を取得します。
4）ステップ3で得られた数値のDEC表現は、n-decimal数値システムに変換されます。
5）配列の0番目の要素を取得し、手順4で取得した数値のn進表記の最初の桁にインデックスが等しい位置にある追加の配列に配置します。
6）配列の最初の要素を取得し、手順4で取得した数値のn進表記の2桁目にインデックスが等しい位置にある追加の配列に配置します。
7）配列の2番目の要素を取得し、手順4で取得した数値のn進表現の3桁目にインデックスが等しい位置にある追加の配列に配置します。
...
n + 3）配列内の（n-2）番目の要素を取得し、ステップ4で得られた数値のn 10進数表現の最後から2桁のインデックスを持つ位置にある追加の配列に配置します。
n + 4）配列内の（n-1）番目の要素を取得し、手順4で取得した数値のn 10進表現の最後の桁にインデックスが等しい位置にある追加の配列に配置します。
n + 5）すべての要素を追加の配列からメインの配列に転送します。
n + 6）利益!!!

Babushkinを他の方法よりもソートすることの利点は明らかです。順序付けは最小限のコストで実行され、要素はすぐに挿入されます。 すべては、一連のnリッチな数字の使用に基づいています。これらの数字は、最初は正しい動きのシーケンスであり、目的の結果につながります。 これにより、Babushkinの並べ替えは、時間の複雑さにおいて議論の余地のないリーダーになります。最悪、平均、および最高の結果はO（n）です。 必要なのは、2つの数字をピックアップすることだけです。これらの数字は、1つずつ割ると、すぐに目的のシーケンスになります。

プロトタイプと動作するプログラムがあり、すべて動作します。


おばあちゃんのJavaでの並べ替え。
残念ながら、おばあちゃんの並べ替えのJava実装は見つかりませんでした。 ごめんなさい

以上で、代替ソートの世界への急行は終わりました。ご清聴ありがとうございました。 難しくない場合は、講義の配布資料に添付されている投票カードに記入します。

親切に提供されたjavaの例をパトリック・モリンに感謝します。

Source: https://habr.com/ru/post/J198114/

More articles:


All Articles