交換ソートのクラスから、最速の方法がいわゆるクイックソートであることは誰もがよく知っています 。 学位論文は彼女について書かれており、Habréに関する多くの記事が彼女に捧げられており、彼女の根拠に基づいて複雑なハイブリッドアルゴリズムを思いついています。 しかし、今日はクイックソートについてではなく、別の交換方法-古き良きバブルソートとその改善、修正、突然変異、品種について話しています。
これらの方法からの実用的な排気はそれほど暑くはなく、多くのhabrappolzovはすべてこれがファーストクラスで行われました。 したがって、この記事は、アルゴリズムの理論に興味を持ち始めたばかりで、この方向への第一歩を踏み出している人々を対象としています。
画像：泡
今日は最も簡単なソーティング交換についてお話します。
興味がある人は、 選択 による並べ替え、挿入 による並べ替え、マージ による並べ替え、配布による 並べ替え 、 ハイブリッド並べ替え 、 並列並べ 替えなど、他のクラスがあると言います。 ところで、 難解な並べ替えもあります。 これらは、さまざまな偽の、基本的に実現不可能な、コミックおよびその他の疑似アルゴリズムであり、ITユーモアハブでいくつかの記事を作成します。
しかし、これは今日の講義とは何の関係もありません;今は交換の単純なソートにのみ興味があります。 交換のソートもたくさんあります（私は12個以上知っています）ので、いわゆるバブルソートとそれに密接に関連する他のいくつかを検討します。
上記の方法のほとんどすべてが非常に遅く、それらの時間の複雑さについての詳細な分析がないことを事前に警告します。 速いものも遅いものもありますが、大まかに言えば、平均O （ n 2 ）と言えます。 また、プログラミング言語での実装で記事を雑然とする理由はありません。 興味のある方は、 Rosetta 、 Wikipedia、または他の場所で簡単にコード例を見つけることができます。
ただし、交換の並べ替えに戻ります。 配列は、配列の複数の順次列挙および要素のペアの相互比較の結果として発生します。 比較されたアイテムが相互にソートされていない場合、それらを交換します。 唯一の問題は、アレイを正確にバイパスする方法と、比較のためにペアを選択する原則です。
参照バブルソートではなく、...というアルゴリズムから始めましょう。
愚かな並べ替え
ソートは本当に愚かです。 配列を左から右に見て、途中で隣人を比較します。 相互に並べ替えられていない要素のペアに出会った場合、それらを交換して、正方形の要素、つまり最初に戻ります。 もう一度調べて配列を確認し、隣接する要素の「間違った」ペアに再び出会った場合は、場所を入れ替えて、最初からやり直します。 配列がゆっくりと整理されるまで続けます。
「だからどんなバカもソートの方法を知っている」-あなたは言う、そしてあなたは絶対に正しいだろう。 これが、ソートが「バカ」と呼ばれた理由です。 この講義では、この方法を一貫して改善および修正します。 今、彼は時間の複雑さO （ n 3 ）を持ち、1つの修正を行ったので、それをO （ n 2 ）に持っていき、それからもう少し高速化し、再び、そして最終的にO （ n log n ）を取得します-そしてこれは「クイックソート」ではありません！
愚かな並べ替えに1つの改善を追加します。 通過中に2つの隣接する未ソート要素を発見し、交換した後、アレイの先頭にロールバックせず、最後まで静かにバイパスし続けます。
この場合、私たちの前に誰もが知られている...
バブルソート
または、単純な交換によるソート 。 ジャンルの不滅の古典。 アクションの原理は単純です。配列を最初から最後まで回り、同時に並べ替えられていない隣接要素を交換します。 最初のパスの結果、最大要素が最後の場所に「ポップアップ」します。 ここでも、配列の未ソート部分（最初の要素から最後から2番目の要素）を巡回し、未ソートの近傍のパスを変更します。 2番目に大きい要素は、最後から2番目の場所にあります。 同じように続けて、配列の増え続ける未ソート部分をバイパスし、見つかった最大値を最後まで押します。
最高値を最後までプッシュするだけでなく、最低値を最初に転送する場合、次のようになります...
シェーカーソート
彼女は混合によって選別しています 、彼女はカクテル選別です。 このプロセスは「バブル」のように始まります。裏庭まで最大限に絞り込みます。 その後、180 0を回して反対方向に進みますが、すでに最初にローリングしているのは最大値ではなく最小値です。 配列の最初と最後の要素をソートしたら、再び宙返りをします。 何度か行ったり来たりして、最終的にリストの中央にいるプロセスを終了します。
シェーカーのソートはバブルのソートよりも少し速く動作します。最大値と最小値が配列に沿って交互に正しい方向に移動するためです。 彼らが言うように、改善は明らかです。
ご覧のように、検索プロセスに創造的に取り組むと、重い（軽い）要素を配列の最後に押し込む方が速くなります。 そのため、職人たちはリストから別の非標準の「ロードマップ」をバイパスすることを提案しました。
奇数偶数ソート
今回は、アレイを行き来しませんが、再度、左から右への計画された往復のアイデアに戻りますが、より広いステップを踏むだけです。 最初のパスでは、奇数のキーを持つ要素と偶数の場所にある隣人とを比較します（1番目の要素は2番目と比較され、3番目は4番目、5番目は6番目などと比較されます）。 次に、逆に、「偶数カウント」要素と「奇数」要素を比較/変更します。 それから再び「奇数偶数」、そして再び「奇数偶数」。 配列を2回連続して通過した後（「奇数-偶数」および「偶数-奇数」）、交換が発生しなくなると、プロセスは停止します。 それで、ソートされました。
各パス中の通常の「バブル」では、配列の最後に現在の最大値を体系的に絞り込みます。 偶数インデックスと奇数インデックスをスキップすると、すぐに配列の多かれ少なかれすべての要素が1回の実行で1ポジション分だけ右に同時にプッシュされます。 速くなりました。
Sortuvannya bulbashka ** の最後の略語を分析し ます **- Sortuvannyaロウイング ***。 この方法は非常に賢く順序付けられ、 O （ n 2 ）はその最悪の複雑さです。 平均して、時間内にO （ n log n ）があります。信じられないでしょうが、最良のものはO （ n ）です。 つまり、あらゆる種類の「クイックソート」に対する非常に価値のある競争相手であり、これは、再帰を使用せずに気になります。 しかし、今日は巡航速度に入らず、黙ってアルゴリズムに直接行くと約束しました。
亀が非難する
少しの背景。 1980年、Vlodzimezh Dobosievichは、バブルとその派生物のソートが非常に遅い理由を説明しました。 これはすべてカメのせいです 。 カメは、リストの最後にある小さなアイテムです。 お気づきかもしれませんが、バブルの並べ替えは、リストの先頭にある大きな要素である「ウサギ」（バブーシュキンの「祖母」と混同しないように）に向けられています。 彼らは非常に勢いよくフィニッシュラインに向かっています。 しかし、開始時の遅い爬虫類はしぶしぶ忍び寄る。 くしでトルティーヤをカスタマイズできます。
画像：有罪のカメ
ヘアブラシを並べ替える
「バブル」、「シェーカー」、および「奇偶」では、配列を反復処理するときに、隣接する要素が比較されます。 「櫛」の主なアイデアは、最初に比較対象の要素間で十分に長い距離を取り、配列の順序に従って距離を最小に狭めることです。 したがって、アレイをそのままコーミングし、徐々にスムージングしてさらにきれいなストランドにします。
比較される要素間の最初のギャップをとにかく取る方がよいのですが、最適化された値が約1.247である縮小係数と呼ばれる特別な値を考慮に入れてください。 まず、要素間の距離は、配列のサイズを縮小係数で割ったものに等しくなります（もちろん、結果は最も近い整数に丸められます）。 次に、このステップで配列を渡した後、再びステップを縮小係数で除算し、リストをもう一度調べます。 これは、インデックスの差が一致するまで続きます。 この場合、配列は通常のバブルでソートされます。
実験的および理論的に、削減係数の最適値が確立されました。
この方法が発明されたとき、70年代と80年代の交差点で注意を払った人はほとんどいませんでした。 10年後、プログラミングがIBMの科学者やエンジニアの関心事ではなくなり、すでに大量のキャラクターの雪崩が起きていたときに、1991年にスティーブンレイシーとリチャードボックスによってこの方法が再発見、研究、普及しました。
実際に、バブルソートとその同類について説明したかったのはこれだけです。
-メモ
*略語（ ウクライナ語 ）-改善
** Sortuvannya Bulbashka（ ウクライナ語 ）-バブルで並べ替え
***コンバイナーによるSortuvannya（ ウクライナ語 ）-櫛によるソート