search
LoginSignup
1

More than 1 year has passed since last update.

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

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 可視化デモ

SelectionSort.gif

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)

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
1