前回の記事では、いわゆる愚かな並べ替えをやめ、単純な変身を通じて、よく知られたバブル並べ替えを取得しました。 後者を変換すると、配列を順序付ける交換方法の山になりました。 ちなみに、そのうちの1つは、数千要素までの構造で、 クイックソートよりも高速に動作します。
今日は再びバカなソートを基本として、小さな、しかし重要な変更を加えます。 その結果、ソートアルゴリズムのまったく異なる進化シリーズを取得します。
画像：進化
愚かな並べ替え
最初のシリーズを見るのが面倒すぎて、私はそれが馬鹿げた種であることを思い出します。 配列を順番に見て回り、並べ替えられていない2つの隣人に会って、それらを交換します。 その後、最初に戻り、「私たちの歌は良いです、最初からやり直してください」 このソートで、戻るのではなく、さらに先に進むと、「バブル」が得られます。これは、判明した
さもなければ、そうします。 2つの要素を交換した後、配列の順序を変更し、新しい場所が以前にチェックした要素と不一致になるかどうかを何らかの方法で確認する必要があります。 配列の先頭にジャンプせず、先に進みませんが、一歩戻ります。 ここでもソートされていない場合は、厳密な優先順位を確立して、さらに一歩戻ります。 そして、配列のソートされた部分に到達するまで後退します。 その後、再び先に進むことができます。
さて、この方法を知らなかった人たちにおめでとう。 名前が...のメソッドに出会いました。
ドワーフソート
画像：オランダの庭のノーム
ドワーフは何世紀にもわたってこの方法を知っていましたが、人類は最近この方法について学びました。 すでに55年前、人類はマージソートを使用していましたが、 クイックソートが知られるようになってから40年が経過し、35年後にピラミッド型ソートが開発されました-そして2000年になって、この独創的でほとんど子供っぽいテクニックがDick Grunによって検討されました
ドワーフのソートは、通常のオランダの庭のノーム（オランダのtuinkabouter）で使用される手法に基づいています。 これは、庭のノームが植木鉢の列を並べ替える方法です。 基本的に、彼は次と前の植木鉢を見ます。それらが正しい順序にある場合、彼は1つの植木鉢を進めます。 境界条件：前のポットがない場合、彼は前進します。 次のポットがない場合、彼は終了です。
もちろん、人々は、保守的な小人が考えなかった改善方法を提案しました。 分類されていない誤解が発生した場所を覚えて、何度か修正を繰り返した場合、後から整理して、すぐに中断した場所にジャンプして、さらにアレイをたどることができます。
少し速くなりますが、この時間的な複雑さは根本的には改善しませんが、 O （ n 2 ）のままであり続けています。 しかし一方で、これにより、新しい並べ替えメソッドだけでなく、まったく新しい並べ替えクラスにもつながります。 このアルゴリズムのグループの名前は「 Insertion Sorts 」です。
簡単な挿入ソート
ここで、配列のセグメントは、最初の要素から開始してサブアレイを展開して、次の未ソート要素をその場所に挿入します。
挿入するには、メモリのバッファ領域が使用されます。この領域には、まだその場所にない要素（いわゆるキー要素 ）が格納されます 。 サブアレイでは、右端から開始して、要素がスキャンされ、キーと比較されます。 キーよりも大きい場合、次の要素は1つ右にシフトされ、後続の要素のためにスペースが解放されます。 この列挙の結果、キー以下の要素が見つかった場合、現在の空きセルにキー要素を挿入できることを意味します。
同じ最適化された「gnome」ですが、交換のみにバッファーが使用されます。
この種の時間の複雑さはO （ n 2 ）ですが、これは主なものではありません。 挿入ソートは、ほとんどソートされた配列にとって最も効率的なオプションのようです。 この事実は、いくつかの複雑なソートアルゴリズムで使用されます。 FlashSortについて話したことがあることを覚えています。 確率分布を使用すると、ほとんどソートされた配列がすばやく作成され、挿入をソートすることで並べ替えられます。 挿入ソートはJSortの最後の部分で使用されます 。ここでは、 不完全なヒープを構築することにより、配列がほとんどすぐにソートされます。 Timsortは、配列内でほぼ順序付けられたセグメントを見つけることで配列のソートを開始します。それらはinsertメソッドによってもソートされ、その後、変更されたマージソートによってマージされます 。
ご覧のとおり、挿入によるソート自体は低速ですが、その範囲は非常に広いです。
さて、 挿入ソートについて非常に多くの文字が書かれているため、話は完全ではありませんが、アルゴリズムに関するいくつかの優しい言葉ではありません...
シェルソート
Habréでのシェルのソートに関する記事はすでにありますので、簡単に説明します。
昨日、私はすでに、非常に遅い「バブル」から非常に迅速な「くし」を作る方法をすでに書きました 。 これを行うには、最初に隣人ではなく、印象的な距離で十分な要素を比較する必要があります。 これにより、初期段階では配列の先頭に近い小さな値、末尾に近い大きな値をスローできます。 次に、ギャップを減らして、アレイ内のローカルオーダーを既に誘導します。
シェルソートは同じ戦略を使用します。 要素のサブグループを挿入してソートしますが、サブグループ内でのみ行に並ぶのではなく、インデックスによるデルタを使用して均等に選択されます。 これらの切断されたサブセットの要素間の距離を系統的に減らすことにより、すでにはるかに高速にソートします。
「シェル」の時間の複雑さは、かなり複雑な問題です。 事実は、サブグループ内の要素間のさまざまな距離の最適な数列を構築する厳密な公式がまだないということです。 シーケンスは、さまざまな入力データを使用した多数のテストに基づいて経験的に構築され、前述の「デルタ」の最後の最適な改良は2001年に決定されました。
1、4、10、23、57、132、301、701。
奇妙なことに、奇妙なことに、1959年にドナルドシェルによってシェルが発明されました。 ちなみに、著者は、ちなみに、90歳になりましたが、今も生き続けていますが、最近3度目の結婚をしました。 だから、アルゴリズムを発明し、あなたの脳を良い状態に保ちましょ
参照資料
ウィキペディアでソートされたアルゴリズム
ウィキペディアのソートアルゴリズム
バブルソートとすべてすべて
並べ替えについても、最適なアルゴリズムを選択します
Rosetta Sortの実装