Clever Geek Handbook

選択ソート

こんにちは。この記事は、OTUSのコース「アルゴリズムとデータ構造」の立ち上げのために特別に作成しました。







前書き



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



問題の定式化



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



選択ソート



最も単純なソートの1つは選択ソートです。



アルゴリズムの説明



選択による配列のソートは次のように実行されます。配列は2つの部分に分かれています。一方はソート済みと呼ばれ、もう一方は未ソートと呼ばれます。このアルゴリズムは、配列全体を走査することを前提としているため、ソートされた部分の長さが配列全体の長さと等しくなります。各反復内で、配列のソートされていない部分の最小値を見つけ、この最小値を配列のソートされていない部分の最初の要素と交換します。次に、配列のソートされた部分の長さを1つ増やします。一回の反復の例を以下に示す：

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



実装



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



void choiseSortFunction(double A[], size_t N)
{
    for(size_t tmp_min_index = 0; tmp_min_index < N;
                                  tmp_min_index++) {
        // 
        for(size_t k = tmp_min_index + 1; k < N; k++) {
            if (A[k] < A[tmp_min_index]) {
                double min_value = A[k];
                A[k] = A[tmp_min_index];
                A[tmp_min_index] = min_value;
            }
        }
    }
}


分析



このアルゴリズムを分析することを提案します。内部ループ自体の本体はO（1）をとります。つまり、ソートされる配列のサイズには依存しません。つまり、アルゴリズムの漸近性を理解するには、この本体が実行された回数をカウントする必要があります。外側のループの最初の反復では、内側のループが（n-1）回反復されます。外側のループの2番目の反復-内側のループの（n-2）反復。この推論をさらに続けると、次のようになります。

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





計算のプロセスでは、最初にO-表記のプロパティを使用し、次に数式を使用して算術的な進行の合計を計算しました。



順序については、アルゴリズムの実行に必要な追加のメモリを見積もる必要もあります。ここではすべてがはるかに単純です。ループカウンターと変数（2つの配列要素を交換できるバッファ）にのみメモリを割り当てました。したがって：

M(n)=O(1)





分析の結果、アルゴリズムの時間の複雑さは入力配列のサイズに2次的に依存するという結論に達しました。したがって、この並べ替えは2次並べ替えのクラスに属します。分析の結果は配列の内容に依存しません。それは、せいぜい、最悪、そして平均で正しいです。



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



両面選択ソート



上記で実装されたアルゴリズムの最適化は、興味深いかもしれません。配列のソートされていない部分をウォークスルーしているときに、最小要素と並行して最大値を検索できます。したがって、反復後、配列のソートされていない部分を1つではなく2つ減らすことができます。アルゴリズムは漸近的には改善されませんが、それでも、その実行速度はわずかに増加する場合があり、比較の数も2倍になります。



再帰的選択ソート



演習として、ループではなく再帰を使用してアルゴリズムを作成することができます。Javaでは次のようになります。 



public static int findMin(int[] array, int index){
    int min = index - 1;
    if(index < array.length - 1) min = findMin(array, index + 1);
    if(array[index] < array[min]) min = index;
    return min;
}
  
public static void selectionSort(int[] array){
    selectionSort(array, 0);
}
  
public static void selectionSort(int[] array, int left){
    if (left < array.length - 1) {
        swap(array, left, findMin(array, left));
        selectionSort(array, left+1);
    }
}
  
public static void swap(int[] array, int index1, int index2) {
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
}


概要



私たちは二次ソートの1つを見ました：選択ソート、ループを使用した安定した実装、再帰、アレイのソートされていない部分の双方向削減によるアルゴリズム最適化について説明しました。並べ替えは純粋に教育的なものであり、実際に幅広い用途を見つけることはできませんでした。





コースの詳細については、7月10日に開催される無料のウェビナーにぜひご参加ください。





More articles:


All Articles