仕分け方法のレビューとテスト。パート I

先日、VKontakte のコメントで、プロジェクトの他の学生の 1 人と口論になりました。論争の本質は「誰が勝つか」、つまりsort()クラスからのメソッド、または簡単なアルゴリズム ( bubble、insert、selection、shell (シェル アルゴリズム) java.util.Arraysの自己記述実装)でした。一部の人にとって、この質問に対する答えは明白かもしれませんが、論争が起こって以来、双方が自分たちの観点を支持する「尊重された情報源」を持っていたという事実にもかかわらず、灰色の部分を拡張して調査を実施することが決定されました。さまざまなアルゴリズムを実装するプロセス。 TL;DR: 100,000 要素以上の配列では無条件でリーダーですが、サイズが小さい場合は、Shell メソッドが競合することがあります。考慮されている残りのアルゴリズムは完全に空であり、特殊な条件下でのみ役立ちます。 次に、シリコン uber-devices で配列がどのようにソートされるかを見てみましょう。 java.util.Arrays.sort()

選択の並べ替え。選択による並べ替え

最も単純で明白な方法から始めましょう。その本質は、ロバート・セジウィック氏がcoursera のビデオ講義で完璧に示しています(そこからアニメーションを引用しますが、私が下手に gif に圧縮したものです): 最初の要素から配列を実行 し、各ステップで右側で最小の要素を探し、現在の要素と交換します。その結果、配列の最終バージョンをソートされた形式で予約します。このアルゴリズムを Java で実装するコードは次のとおりです。

public void sort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n; i ++) {
            int minIndex = min(array, i, n - 1);
            swap(array, i, minIndex);
        }
    }

public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
public static int min(int[] array, int begin, int end) {
        int minVal = array[begin];
        int minIndex = begin;
        for (int i = begin + 1; i <= end; i++) {
            if (array[i] < minVal) {
                minVal = array[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

アルゴリズムを分析すると、各パスで配列の残りの部分をくまなく調べる必要があることがわかります。つまり、正確に N + (N-1) + (N-2) + ... + 1 = N^ が必要になります。 2/2の比較。したがって、アルゴリズムの複雑さは O(N^2) です。これはどういう意味ですか？これは、配列内の要素数 (N) を 2 倍に増やすと、アルゴリズムの実行時間が 2 倍ではなく、2^2 = 4 倍増加することを意味します。Nを10倍にすると動作時間は100倍などとなります。Ubuntu 14.4 を実行している Core i3 プロセッサを搭載した 2012 年のラップトップでは、次のような稼働率が得られました。

挿入ソート。挿入ソート

ここでは考え方が少し異なります。もう一度、セジウィック博士のアニメーションに目を向けてみましょう。 前にあるものはまだ私たちには見られていないのに、私たちが後に残したものはすべて常に整然としたままです。重要なのは、元の配列の各新しい要素を、より小さい要素に「置かれる」まで先頭に「戻す」ということです。したがって、ここでも (元の配列の各要素に対して) N 回のパスがありますが、各パスでは、ほとんどの場合、残り全体を見るのではなく、一部だけを調べます。つまり、次の各要素を先頭に戻す必要がある場合にのみ、オプション 1 + (N-1) + (N-2) + … + N = N^2/2 が得られます。 「逆に」ソートされた入力配列 (アンラッキー、アンラッキー)。すでにソート済みの配列の場合 (これは運が良いです)、完全な特典が提供されます。各パスで比較が 1 つだけ行われ、要素が所定の位置に残されます。つまり、アルゴリズムは N に比例した時間で動作します。アルゴリズムの値は理論上の最悪のケース、つまり O( N^2) によって決まります。平均すると、動作時間は N^2/4 に比例し、前のアルゴリズムの 2 倍になります。私の実装では、順列の使用が最適ではなかったため、実行時間は選択よりも長くなりました。近いうちに記事を修正して更新する予定です。以下は、同じマシン上でのコードとその操作の結果です。

public void sort(int[] array) {
        int length = array.length;
        for (int i = 1; i < length; i++) {
            for (int j = i; j >= 1; j--) {
                if (array[j] < array[j - 1])
                    swap(array, j, j - 1);
                else
                    break;
            }
        }
    }

シェルソート。シェルソート

賢い人、ドナルド シェルは 1959 年に、挿入アルゴリズムで最もコストがかかるケースは、要素が配列の先頭に非常に遠くに戻るときであることに気づきました。あるパスでは、要素を 2、3 位置分先頭に戻します。 、そして別のパスでは、配列全体をほぼ通過して先頭までが遠くて長いです。いくつかの要素を飛び越えてこれを一度に行うことは可能ですか? そして彼はそのような方法を見つけました。これは、一般に d ソート、または Sedgwick によれば h ソート (h はホップの意味だと思われます) と呼ばれる、特別な部分ソートを順番に実行することで構成されます。たとえば、3 ソートでは、問題の要素を前の要素と比較するのではなく、2 つスキップして 3 つ前の要素と比較します。変更された場合は、3 つ前の要素と再度比較されます。要するに、結果の配列は「3 ソート」されます。つまり、要素の誤った位置は 3 位置未満になります。この挿入アルゴリズムの使用は簡単で快適です。ちなみに、「1-sort」は単なる挿入アルゴリズムにすぎません =) h 値を減少させながら配列に h-sort を順次適用することで、大きな配列をより高速にソートできます。これは次のようになります: ビュー ここでの課題は、部分ソートの適切なシーケンスを選択する方法です。最終的に、アルゴリズムのパフォーマンスはこれに依存します。最も一般的なのは、Donald Knuth によって提案されたシーケンスです。h = h*3 + 1、つまり、1、4、13、40、... というように配列サイズの 1/3 まで続きます。このシーケンスは適切なパフォーマンスを提供し、実装も簡単です。アルゴリズムの分析には大量の言語が必要であり、私の能力を超えています。解析の幅は、h 配列の多様なバリエーションによっても決まります。経験的に、アルゴリズムの速度は非常に優れていると言えます。1 秒未満で 100 万個の要素が処理されることをご自身の目で確認してください。そして、これが Knut シーケンスを含む Java コードです。

public void sort(int[] array) {
        int h = 1;
        while (h*3 < array.length)
            h = h * 3 + 1;

        while(h >= 1) {
            hSort(array, h);
            h = h/3;
        }
    }

    private void hSort(int[] array, int h) {
        int length = array.length;
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h; j = j - h) {
                if (array[j] < array[j - h])
                    swap(array, j, j - h);
                else
                    break;
            }
        }
    }

バブルソート。バブル方式

これは古典です！ほぼすべての初心者プログラマがこのアルゴリズムを実装します。これは非常に古典的な作品なので、セジウィック博士にはアニメーションさえ用意されていなかったため、私が自分で作業を行う必要がありました。 ここ では、各パスで配列を最初から最後まで走査し、順序が狂っている隣接する要素を交換します。その結果、最大の要素は配列の末尾に「浮動」します (それが名前の由来です)。配列がすでにソートされていることを期待して、楽観的に各新しいパスを開始します ( sorted = true)。パッセージの終わりで、間違いを犯したことがわかった場合は、新しいパッセージを開始します。ここでの難しさは、繰り返しになりますが、各パスで配列全体を (ほぼ) 横断することになることです。比較はすべてのステップで発生し、交換はほぼすべてのステップで発生するため、このアルゴリズムは最も遅いアルゴリズムの 1 つになります (「シェーキング ソート」などではなく、合理的に実装されたものを考慮した場合)。興味深いことに、形式的にはここでの複雑さも O(N^2) に等しくなりますが、係数は挿入や選択の係数よりもはるかに高くなります。アルゴリズムコード:

public void sort(int[] array) {
        boolean isSorted;
        int nMinusOne = array.length - 1;
        for(int i = 0; i < nMinusOne; i++) {
            isSorted = true;
            for (int j = 0; j < nMinusOne - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    isSorted = false;
                }
            }
            if (isSorted)
                return;
        }
    }

操作時間: 違いを感じてください: 100 万個の要素を使用するのに 30 分以上かかります。結論:このアルゴリズムは決して使用しないでください。

前半部分の概要

そのため、これらのアルゴリズムの一般的な表を確認することをお勧めします。 組み込みメソッドの結果と比較することもできますjava.util.Arrays.sort()。それはある種の魔法のように見えます - Shell より速いものはあるでしょうか? これについては次のパートで書きます。そこでは、広く使用されているクイック ソート アルゴリズムとマージ ソートを見て、プリミティブと参照型から配列をソートする方法の違いについて学び、この問題に関する非常に重要なインターフェイスについても説明します ;)Comparable以下で学習できます。データ テーブルを使用して対数スケールで構築されたグラフ。線が平坦であればあるほど、アルゴリズムはより優れています =) プロジェクト全体をダウンロードして自分でテストを実行したい人は、リンクを保持してください: Java 次のパートでお会いしましょう! =)