選択ソート Selection Sort【可視化GIFでソートアルゴリズムを解説 その２】

2、選択ソート（Selection Sort）

最も安定したソートアルゴリズムの1つ。どのデータが入力されても、O（n2）時間計算量であるため、使用する場合は、データサイズが小さいほど良いです。 唯一の利点は、追加のメモリスペースを使用しないことです。 理論的には、選択的ソートは、ほとんどの人が考えるソート方法でもあります。

Selection-sortは、シンプルで直感的なソートアルゴリズムです。 それは機能します：最初にソートされていないシーケンスで最小（大きい）要素を見つけ、それをソートされたシーケンスの最初に保存し、次に残りのソートされていない要素から最小（大きい）要素を見つけて、それをソートされたものに入れますシーケンス最後に。 など、すべての要素が並べ替えられるまで続きます。

2.1 アルゴリズムの説明

レコードn件の直接選択と並べ替えを直接選択し、n〜1回並べ替えて、順序付けられた結果を取得できます。 具体的なアルゴリズムは次のとおりです。

• 初期状態：無秩序な領域はR [1..n]であり、順序付けられた領域は空です。

• i番目のソート（i = 1,2,3 ... n-1）の開始時、現在の順序付けられた領域と無秩序な領域はR [1..i-1]とR（i..n ）それぞれ。 このソートトリップは、現在の無秩序領域から最小のキーを持つレコードR [k]を選択し、それを無秩序領域の最初のレコードRと交換して、R [1..i]とR [i +1を作成します。 .n）レコード数が1増加した新しい順序付けられた領域と、レコード数が1つ減少した新しい無秩序領域になります。

• n-1パスが終了し、配列が順序付けられます。

2.2 可視化デモ

2.3 実装

    /**
     * Selection Sort
     * @param array
     * @return
     */
    public static int[] selectionSort(int[] array) {
        if (array.length == 0)
            return array;
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i; j < array.length; j++) {
                if (array[j] < array[minIndex]) //find the minest number
                    minIndex = j; //hold the index of the min number
            }
            int temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;
        }
        return array;
    }

2.4 性能評価

最も安定したソートアルゴリズムの1つ。どのデータが入力されても、時間計算量はO（n2）であるため、使用する場合は、データサイズが小さいほど良いです。 唯一の利点は、追加のメモリスペースを使用しないことです。 理論的には、選択的ソートは、ほとんどの人が考えるソート方法でもあります。

• 最良時間計算量 ：T(n) = O(n2)
• 最悪時間計算量 ：T(n) = O(n2)
• 平均時間計算量 ：T(n) = O(n2)

---