Clever Geek Handbook

インサートで並べ替え

こんにちは。今日は、OTUSのコース「アルゴリズムとデータ構造」の立ち上げのために特別に書いた一連の記事を続けます。







前書き



配列のソートは、コンピュータサイエンス分野の古典的なコース「アルゴリズムとデータ構造」で研究された最初の深刻な問題の1つです。この点で、インターンやジュニア開発者としてのインタビューでは、並べ替えや対応する質問を書く作業が頻繁に発生します。



問題の定式化



伝統的に、その声明で問題の解決策の提示を始める価値があります。通常、並べ替えタスクでは、整数の配列を昇順に並べ替えます。しかし、実際には、これは多少単純化しすぎています。このセクションで説明するアルゴリズムは、順序関係が確立されているオブジェクトの配列を順序付けるために使用できます（つまり、2つの要素について、最初の要素が2番目の要素よりも大きい、2番目の要素が最初の要素よりも大きい、または等しい場合）。昇順と降順の両方でソートできます。標準の簡略化を使用します。



インサートで並べ替え



前回、最も単純な並べ替えの 1つである選択並べ替えについて説明しました。今日はもう少し複雑なアルゴリズムである挿入ソートに焦点を当てます。



アルゴリズムの説明



挿入による配列のソートは、次の方法で実行されます。選択ソートの場合と同様に、配列は2つの部分に分割されます。一方はソート済みと呼ばれ、もう一方は未ソートと呼ばれます。このアルゴリズムは、配列全体を走査することを前提としているため、ソートされた部分の長さが配列全体の長さと等しくなります。各反復内で、配列のソートされていない部分の最初の要素を取得し、それを使用して次の操作を実行します。要素が前の要素よりも厳密に小さい場合、それらを交換します。次に、配列のソートされた部分の長さを1つ増やします。したがって、調査中の要素を連続的に移動することにより、所定の位置に収まることを達成します。一回の反復の例を以下に示す：

1 3 5 | 2 9 6-> 1 3 2 5 9 6-> 1 2 3 5 9 6-> 1 2 3 5 | 9 6



実装



Cでのこのアルゴリズムの実装を確認することをお勧めします。 



void insertionSortFunction(double array[], int size) {
    int i, j, temp;
    // i     ,   1,         
    for (i = 1; i < size; i++) {
        temp = array[i];
        for (j = i - 1; j >= 0; j--) {
            if (array[j] < temp) {
                break;
            }
  
            array[j + 1] = array[j];
            array[j] = temp;
        }
    }
}




分析



このアルゴリズムを分析することを提案します。



分析を開始する最も簡単な方法は、メモリの漸近を取得することです。並べ替え用に提案された配列の長さと構造に関係なく、メモリは2つのループカウンターと2つの変数値の交換に使用される1つの補助変数にのみ割り当てられます。したがって、それは常に真です。

M(n)=O(1)

...



時間の経過とともに、すべてがやや興味深いものになります。内部ループ自体の本体はO（1）をとります。つまり、ソートされる配列のサイズには依存しません。つまり、アルゴリズムの漸近性を理解するには、この本体が実行された回数を数える必要があります。ただし、内部ループの反復回数は、並べ替えられる配列の要素の順序付け（または順序付けなし）に依存します。分析のためにいくつかのケースを調べる必要があります。



ソートする配列がすでにソートされている場合、最小反復回数に達しています。実際、外側のforループの反復ごとに、内側のループが1回だけ繰り返されます。これは、いわゆるベストケースです。

T(n)=(n−1)∗O(1)=O(n)

したがって、ソートは線形時間で行われます。



で、最悪の場合、反復回数は、決して火を破るされていないこと、最大であると仮定されます。外側のループの最初の反復で、内側のループの1回の反復が実行されます。外側のループの2回目の反復では、内側のループが2回反復されます。さらに推論を続けると、最後の（n-1）-th）で外側のループの反復（n-1）が実行されるという結論に達することができます。我々が得る：

T(n)=O(1)+2∗O(1)+3∗O(1)+...+(n−1)∗O(1)=O(1+2+3+...+(n−1))=O(n∗(n−1)/2)=O(n2)

計算を実行するために、O-表記のプロパティと算術的な進行の合計の式を使用しました。平均場合、外側のループの特定の反復のための内側ループの反復の回数は、数学的期待値であり、その平均値に等しいと仮定されます。内部ループの発火のすべての許可された数が等しく可能性があると仮定します。この場合、内部ループの平均反復回数はです。私は外側のループの反復数であると仮定されます。ここで、漸近を計算するには、を計算する必要があります。つまり、内部ループの本体が実行された回数を数えるだけです。したがって、が得られます。 要約すると、アルゴリズムのメモリの漸近は



画像画像画像



O(1)

せいぜい間に

O(n)

平均および最悪の場合

O(n2)

したがって、この並べ替えは2次並べ替えのクラスに属します。



この実装では、選択のソートが堅牢であることにも注意することが重要です。実行中に等しい要素の順序が変更されない場合、ソートは安定と呼ばれます。このプロパティは、数値の配列の並べ替えなどの教育的タスクにはそれほど重要ではありませんが、確立された順序関係を持ついくつかのより複雑なオブジェクトを並べ替える場合は、重要になる可能性があります。基数の並べ替えについて次回話すときに、同じような例を考えることができます。



結果



私たちは別の二次ソート、つまり挿入ソートを調べ、その堅牢な実装を調べました。並べ替えは、主に教育的ですが、実際には十分に漸近的であるため、実際に適用できます。すべてのデータが再度順序付けられるように、十分に大きい順序付けされたデータに新しいデータを追加する必要がある場合、内側のforループが役立ちます。だからそれはのためにサポートすることができます

O(n)

データ量の秩序性。





コースの詳細をご覧ください。





More articles:


All Articles