algorithms

挿入ソート、マージソート

挿入並べ替え

挿入並べ替え –各要素はリスト内の前の要素と比較され、大きい方の要素があればその要素と交換されます。それ以外の場合は内部比較ループが実行されます。止まります。要素は最初から最後までソートされるため、各要素はすでにソートされたリストと比較され、*おそらく* 全体の実行時間が短縮されます。アルゴリズムの時間計算量は O(n^2)、つまりバブルの種類と同じです。

並べ替えを結合

並べ替えを結合–リストは 1 つの要素のグループに分割され、その後、それらのグループがペアで「マージ」され、同時に比較されます。私の実装では、ペアをマージするときに、左側の要素が右側の要素と比較され、左側の要素がなくなった場合は、右側のすべての要素が結果のリストに追加されます。 list (グループ内のすべての要素が繰り返しソートされるため、追加の比較は不要です)< br />このアルゴリズムの作業は並列化するのが非常に簡単です。ペアを結合する段階は、ディスパッチャーでの反復の終了を待ってスレッドで実行できます。
シングルスレッド実行のアルゴリズムの出力:

["John", "Alice", "Mike", "#1", "Артем", "20", "60", "60", "DoubleTrouble"]
[["John"], ["Alice"], ["Mike"], ["#1"], ["Артем"], ["20"], ["60"], ["60"], ["DoubleTrouble"]]
[["Alice", "John"], ["#1", "Mike"], ["20", "Артем"], ["60", "60"], ["DoubleTrouble"]]
[["#1", "Alice", "John", "Mike"], ["20", "60", "60", "Артем"], ["DoubleTrouble"]]
[["#1", "20", "60", "60", "Alice", "John", "Mike", "Артем"], ["DoubleTrouble"]]
["#1", "20", "60", "60", "Alice", "DoubleTrouble", "John", "Mike", "Артем"]

マルチスレッド実行のアルゴリズムの出力:

["John", "Alice", "Mike", "#1", "Артем", "20", "60", "60", "DoubleTrouble"]
[["John"], ["Alice"], ["Mike"], ["#1"], ["Артем"], ["20"], ["60"], ["60"], ["DoubleTrouble"]]
[["20", "Артем"], ["Alice", "John"], ["60", "60"], ["#1", "Mike"], ["DoubleTrouble"]]
[["#1", "60", "60", "Mike"], ["20", "Alice", "John", "Артем"], ["DoubleTrouble"]]
[["DoubleTrouble"], ["#1", "20", "60", "60", "Alice", "John", "Mike", "Артем"]]
["#1", "20", "60", "60", "Alice", "DoubleTrouble", "John", "Mike", "Артем"]

アルゴリズムの時間計算量は O(n*log(n)) で、O(n^2) よりわずかに優れています

ソース

https://en.wikipedia.org/wiki/Insertion_sort
https://en.wikipedia.org/wiki/Merge_sort

ソースコード

https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/insertionSort
https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/mergeSort

Erlang のバブルソート

バブルソートは非常に退屈ですが、通信用の関数型言語で実装してみるとさらに面白くなります。アーラン。

数値のリストがあるので、それを並べ替える必要があります。バブルソートアルゴリズムは、リスト全体を調べて、数値をペアごとに反復して比較します。チェック中に次の処理が行われます。出力リストに小さい番号が追加されるか、現在のリスト内の番号が交換されます。右側の番号が小さい場合は、反復内の次の番号で検索が続行されます。この走査は、リストに置換がなくなるまで繰り返されます。

実際には、アルゴリズムの時間の複雑さのため、使用する価値はありません – O(n^2);私は Erlang で命令型スタイルで実装しましたが、興味がある場合は、より良いオプションを探すことができます。

-module(bubbleSort).
-export([main/1]).

startBubbleSort([CurrentHead|Tail]) ->
    compareHeads(CurrentHead, Tail, [], [CurrentHead|Tail]).

compareHeads(CurrentHead, [NextHead|Tail], [], OriginalList) ->   
    if
        CurrentHead < NextHead ->
            compareHeads(NextHead, Tail, [CurrentHead], OriginalList);
        true ->
            compareHeads(CurrentHead, Tail, [NextHead], OriginalList)
    end;
    
compareHeads(CurrentHead, [NextHead|Tail], OriginalOutputList, OriginalList) ->
    if
        CurrentHead < NextHead ->
            OutputList = OriginalOutputList ++ [CurrentHead],
            compareHeads(NextHead, Tail, OutputList, OriginalList);
        true ->
            OutputList = OriginalOutputList ++ [NextHead],
            compareHeads(CurrentHead, Tail, OutputList, OriginalList)
    end;
  
compareHeads(CurrentHead, [], OriginalOutputList, OriginalList) ->
    OutputList = OriginalOutputList ++ [CurrentHead],
    if
        OriginalList == OutputList ->
            io:format("OutputList: ~w~n", [OutputList]);
        true ->
            startBubbleSort(OutputList)
    end.
  
main(_) ->
    UnsortedList = [69,7,4,44,2,9,10,6,26,1],
    startBubbleSort(UnsortedList).

インストールと起動

Ubuntu では、Erlang のインストールは非常に簡単です。ターミナルに sudo apt install erlang と入力するだけです。この言語では、各ファイルは外部で使用できる関数のリストを含むモジュールである必要があります。輸出。この言語の興味深い特徴には、変数がなく定数のみであること、OOP の標準構文がないこと (OOP テクニックの使用を妨げるものではありません)、そしてもちろんアクターモデルに基づくロックなしの並列計算が含まれます。

モジュールは、対話型 erl コンソールを使用してコマンドを次々に実行するか、あるいはもっと簡単に escript bubbleSort.erl を使用して実行できます。ケースが異なると、ファイルの外観も異なります。たとえば、escript の場合は、開始元となる main 関数を作成する必要があります。

ソース

https://www.erlang.org/
https://habr.com/ru/post/197364/

ソースコード

https://gitlab.com/ demensdeum/algorithms/blob/master/bubbleSort/bubbleSort.erl

辞書編集的比較アルゴリズム

辞書編集文字列比較アルゴリズムは非常に簡単に動作します。文字コードはループ内で比較され、文字が等しくない場合は結果が返されます。

C 言語の例は次の場所にあります。
https://github.com/gcc-mirror/gcc/blob/master/libiberty/memcmp.c

単一の静的エンコーディングで文字を比較する必要があることを考慮する必要があります。たとえば、Swift では UTF-32 で文字ごとの比較を使用しました。 memcmp を使用した配列ソートオプションは、シングルバイト文字に対しては正確に機能しますが、その他の場合 (可変長エンコーディング)、順序が正しくない可能性があります。可変長エンコーディングに基づいた実装の可能性は排除しませんが、おそらく桁違いに複雑になるでしょう。

アルゴリズムの時間計算量は、最良の場合は O(1)、平均および最悪の場合は O(n) です

ソース

https://ru.wikipedia.org/wiki/Lexicographic_order

ソース

https://gitlab.com/demensdeum /algorithms/blob/master/lexiCompare/lexiCompare.swift

二分探索

電子メールアドレス「demensdeum@gmail.com」が、手紙の受信が許可されている電子メールアドレスのリストに含まれているかどうかを確認する必要があるとします。 .

最初の要素から最後の要素までリスト全体を調べて、その要素が指定されたアドレスと等しいかどうかを確認してみましょう –線形探索アルゴリズムを実装してみましょう。しかし、これには長い時間がかかりますか?

この質問に答えるには、「アルゴリズムの時間計算量」の「O」表記を使用します。最悪の場合の線形探索の動作時間は配列要素の n 番目の数に等しいので、これを「O」表記で書きましょう –の上）。次に、既知のアルゴリズムには 3 つのパフォーマンス指標があることを説明する必要があります。最良の場合、最悪の場合、および平均的な場合の実行時間。たとえば、メールアドレス「demensdeum@gmail.com」は配列の最初のインデックスにあり、次の最初のステップで見つかります。このアルゴリズムを使用すると、実行時間はせいぜい – ということになります。 O(1);そして、リストの最後にある場合、これは最悪のケースです。 O(n)

しかし、ソフトウェアの実装やハードウェアのパフォーマンスの詳細についてはどうなのでしょうか?それらは Big O に影響を与えるはずです。ここで一呼吸置いて、時間計算量の計算が、このアルゴリズムのみが存在し、他には何も存在しない、抽象的な理想的なマシンに対して計算されると想像してください。

アルゴリズム

OK、線形探索はかなり遅いことがわかりました。二分探索を使ってみましょう。まず、バイナリデータを処理しないことを明確にしておきます。この名前は、その動作の特殊性のためにこのメソッドに付けられました。最初に配列を辞書編集順の場合、アルゴリズムは配列全体の範囲を取得し、範囲の中央の要素を取得し、それを比較します辞書順に基づいて、比較の結果に応じて、さらに検索するためにどの範囲を使用するかを決定します。現在の上半分または下半分。つまり、各検索ステップで、可能な 2 つの候補から決定が行われます。バイナリロジック。このステップは、単語が見つかるか見つからない (範囲の下位インデックスと上位インデックスの交差が発生する) まで繰り返されます。

このアルゴリズムのパフォーマンス –最良のケースは要素が配列 O(1) の中央ですぐに見つかった場合であり、列挙の最悪のケースは O(log n) です。

落とし穴

二分探索を実装する際、プログラミング言語ライブラリにおける辞書編集の比較の標準化が欠如という興味深い問題に遭遇しただけでなく、実装のための統一標準が存在しないことさえ発見しました。 localeJavaScript 内で比較します。 ECMAScript 標準では、この関数のさまざまな実装が許可されています。そのため、localeCompare を使用して並べ替える場合、異なる JavaScript エンジンではまったく異なる結果が観察される可能性があります。

したがって、アルゴリズムが正しく機能するには、同じ辞書編集比較アルゴリズムのみを並べ替えて使用する必要があり、そうでないと何も機能しません。しかし、たとえば、ある実装の独自のソート/ソートを実装せずに、Scala で配列をソートし、nodejs を使用して検索しようとすると、人間性への失望以外に何も待つことはありません。

ソース

辞書編集的比較とは何ですか?また、それは何を表しますか?
Почему для вычисления сложности алгоритмов используется log N вместо lb N?
Двоичный поиск
Знай сложности алгоритмов
https://stackoverflow.com/questions/52941016/sorting-in-localecompare-in-javascript

ソースコード

https://gitlab.com/demensdeum/algorithms