アルゴリズム選択ソート(選択ソート)(C++)

4241 ワード
アルゴリズム#アルゴリズム# ソートの選択 データ構造 テキストリンク
📌≪ソートの選択｜Select Sort｜Planning≫:「≪選択｜Select｜Planning≫」の最小値でソートするアルゴリズム
▼▼ソートアルゴリズムを選択
  • 昇順
  • この順序の要素の位置が決定されました.配置する要素を選択してください.
    1.最初の順序で最小の要素を選択し、最初のidxに入れます.
    2.2番目の順序で、残りの値の最小要素を選択し、2番目のidxに入れます.
  • 詳細手順
    1.最初のインデックスに基づいて、指定された配列内のすべての要素を比較し、最適な値を探します.
    最大値
  • を最初の値に置き換えます.
  • は、2番目のインデックスを残りの値に同じ方法で置き換えます.
  • 要素が残るまで、1～3つのプロセスを繰り返します.(最後の要素を自動ソート)
    • 💻 選択ソート(selection sort)C++実装コード
    
#include<iostream>
#include<vector>

void selectionSort(vector<int> &v){         #vector의 주소를 매개변수로 넘겨 받아야 원본이 변경됨
	for(int i=0; i<v.size()-1; i++){    #마지막 원소는 자동 정렬이므로 vector의 크기 -1
   	int key = i;
       for(int j = i+1; j<v.size(); j++){
       	if(v[j]<v[key]){
           	key = j;
           }
       if( i != key){			     #자기자신이 최솟값이면 교체X
       	swap(v[i], v[key])
           }
       }
    }
}
    ▼▼並べ替えを選ぶ時間の複雑さ
  • 比較回数
    • 2つのfor文
  • を実行
    外部for文:(n-1)回
    内部for文:n-1、n-2、...、2、1号
  • 交換
  • 外部ループの実行回数と同じです.
  • を交換するには3回の移動(swap)が必要であるため、3(n-1)回の
    • が必要である.
  • T(n) = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)
    • Scoop入門
    溝広告:ウェブサイトの貨幣化の未来