6. 선택 정렬 (Selection Sort)

선택 정렬은 가장 작은 요소부터 선택해서 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘이다.

 

6

4

8

3

1

9

7

여기서 제일 작은 원소 값은 1이며. 1을 선택해서 맨 앞에 위치한 값과 바꾼다.

1

4

8

3

6

9

7

 

이제 1 다음으로 작은 원소 3을 선택해서 1 다음에 위치한 값의 원소 값과 교환을 한다.

1

3

4

8

6

9

7

앞의 세 칸은 정렬을 완료했고 , 뒤의 4개 값에 대해서 계속 정렬을 해주면 되는 것이다.

 

 

위의 선택정렬 과정을 정리하면 아래와 같다.

1) 정렬하지 않은 부분에서 가장 작은 키 값의 (a[min]) 을 선택

2) a[min] 과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환

 

이제 이를 코드로 구현해보자.

void selection(int a[],int n)
{
	int i,j
    for(i=0;i<n-1;i++)
    {	
    	int min = i;
    	for(j=i;j<n;j++)
        {
        	if(a[min]>a[j])
            	min = j;
        }
        swap(int, a[i],a[min]);
    }

}