［アルゴリズム］Sortの選択

5078 ワード
アルゴリズム#アルゴリズム# テキストリンク

Abstract


Selection Sortは해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘です.

Process(Ascending)

  • で指定された配列で最小値を探します.
    • 値
  • を一番前の値に置き換えます.
  • の最初の位置を除いて、残りの配列を同じ方法で置き換えます.

    • C++ Code(Ascending)

    #include <iostream>
#include <vector>
using namespace std;

void SelectionSort(vector<int> arr){
  int indexMin, temp = 0;
  for(int i=0; i<arr.size()-1; i++){    // 1
    indexMin = i;
    for (int j=i+1; j<arr.size(); j++){ // 2
      if(arr[j] < arr[indexMin]){       // 3
        indexMin = j;
      }
    }
    swap(arr[indexMin], arr[i]);        // 4
  }
}

    コメントの説明

  • の範囲で、最小値の位置を選択します.
  • i+1インデックスから検証値の終了まで.
  • の範囲で最小値が見つかり、indexminにインデックスが格納されます.
  • indexmin位置の値と最小値の位置の値を交換します.

    • GIFとしての選択Sort



    時間の複雑さ


    時間複雑度はO(n^2)であり,(n-1) + (n-2) + (n-3) + ... + 2 + 1 ➡ n(n-1)/2であるためである.
    並べ替えの有無にかかわらず比較するので,最適,平均,最悪の場合はO(n^2)である.

    くうかんふくざつさ


    O(n)は、所与の配列において交換によって並べ替えられるからである.

    長所

  • の実装は非常に簡単で、ソースコードは直感的です.
  • は、ソートするアレイ内で交換されるその場ソート(その場ソート)方式であり、他のメモリ領域は必要ありません.
    • 比較
  • ソートの回数は多いが、実際の交換回数はBubble Sortより少ないため、大量の交換が必要な資料状態では比較的効率的である.

    • 短所

  • 時間の複雑さが最も悪く,最も良く,平均はO(n^2)であり,効率がない.
  • 不安定なソート(Unstable Sort)は、同じ値に対して既存の順序を保持しません.

    • コメントサイト


    ソートの選択
    安定ソートと不安定ソート
    Map
    [Chapter 5-3]Rustメソッド(method)