002. 선택 정렬(Selection Sort)

1.알고리즘설명

가장 직관적인 정렬이다. 오름차순 정렬을 한다면,

 

- n개 수에 대해서 가장 작은 값을 찾아서(n-1번 비교) 그 값을 가장 왼편에 놓고(0번 째 자리에), - 나머지 수에 대해서 가장 작은 값을 찾아서 1번 째 자리에 놓고, - 이러한 과정을 수가 끝날 때까지 수행

 

선택정렬의 정렬 과정

 

아래 그림은 정렬되는 모습을 애니메이션으로 보여준다. (출처: wikipedia)

정렬과정 애니메이션(출처:wikipedia)

 

2. 알고리즘 Flow

1. i=0
2. i가 n-2가되면 종료
3. i항부터 (n-1)항까지에서 가장 작은 값을 tmp에 저장 tmp = min(data[i] ~ data[n-1])
4. i항과 tmp를 교환 swap(i, tmp)
5. i를 하나 중가시키고 2로 돌아간다.

 

3. 소스 코드

inline void swap(int& left, int& right) {
  int tmp;
  tmp = left;  left = right;  right = tmp;
}

void selectionSort(vector<int> &v){
  int size = v.size();
  for(int i=0;i<size-1;++i){
    int tmp=i;
    for(int j=i+1;j<size;++j)  if(v[tmp] > v[j]) tmp = j;	
	swap(v[i],v[tmp]);	
  }
}

 

4.시간복잡도:O(n²)

• 비교: n²/2
• 교환:(n-1)