[Algorithm] Sorting / Selection Sort

Selection Sort(선택 정렬)

• 가장 작은 것을 선택하여 제일 앞으로 보내는 알고리즘
• 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘

  • 첫 번째 순서에는 첫 번째 위치에 가장 최솟값을 넣는다.
  • 두 번째 순서에는 두 번째 위치에 남은 값 중에서 최솟값을 넣는다.
    ...

선택정렬의 코드는 다음과 같습니다.

#include <iostream>
using namespace std;

int main(){
   int a[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
   int n = 10;

   for(int i=0; i<n-1; i++){
       int idx = i; // idx: 매 사이클을 돌 때의 가장 작은 배열의 인덱스값을 기록
       for(int j=i+1; j<n; j++){
           if(a[j]<a[idx]) idx = j;
       }
       swap(a[i], a[idx]);
   }

   for(int i=0; i<n; i++) cout<<a[i]<<" ";
   return 0;
}

선택 정렬의 시간복잡도

• 선택 정렬의 시간 복잡도는 최선의 경우와 최악의 경우 모두 O(n^2)입니다.