선택정렬 (Selection Sort)

- 선택정렬(Selection Sort) -

 

기준 위치(i)에서 나머지 원소들을 탐색(j)하여
가장 작은 값의 위치(idx)를 선택하고 맞바꾸는 정렬

 

---

 

문제인식)

다음 그림과 같은 수(數)의 배열이 있다.

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

 

이 배열을 오름차순 정렬, 즉 가장 작은 수부터 차례대로 정렬하기 위해선 어떻게 프로그래밍 해야할까?

 

---

 

해결과정)

1) 기준 위치를 배열의 가장 왼쪽부터 차례대로 잡아나갈 것이고,

2) 기준위치를 잡았으면 그 나머지 원소들을 탐색하여 그들 중 가장 작은 값(최솟값)의 위치를 찾을 것이다.

(값 자체가 아닌 위치를 찾는 이유는 곧 나온다.)

3) 그리고는 기준 위치의 원소랑 최솟값 위치의 원소랑 맞바꾸는 것이다.

 

(※ [더보기]를 클릭하면 C/C++ 소스코드를 참조할 수 있습니다.)

int n, i, j, idx, tmp;
int a[10] = {2, 10, 1, 9, 7, 4, 5, 8, 3, 6};

n=10; //배열의 크기

for(i=0; i<n-1; i++) {
    idx=i;
    for(j=i+1; j<n; j++) {
        if(a[j]<a[idx]) idx=j;
    }
    tmp=a[i];
    a[i]=a[idx];
    a[idx]=tmp;
}

 

이렇게 하면

첫번째 자리에는 가장 작은 값이 위치하게 되고

두번째 자리에는 그 다음으로 작은 값이 위치하게 되어

결국에는 오름차순 정렬이 될 것이다.

 

메인 함수와 출력까지 나타낸 최종 코드는 다음과 같다.(C/C++)

#include <stdio.h>

int main() {
	int n, i, j, idx, tmp;
	int a[10] = {2, 10, 1, 9, 7, 4, 5, 8, 3, 6};
	
	n=10; //배열의 크기
	
	for(i=0; i<n-1; i++) {
	    idx=i;
	    for(j=i+1; j<n; j++) {
	        if(a[j]<a[idx]) idx=j;
	    }
	    tmp=a[i];
	    a[i]=a[idx];
	    a[idx]=tmp;
	}
	
	for(i=0; i<n; i++) {
		printf("%d ", a[i]);
	}
	
	return 0;
}

 

---

 

번외) 값 자체가 아닌 위치를 찾는 이유

맞바꾸기(swap) 작업을 할 때 문제가 생긴다.

idx가 아닌 값 자체를 저장하는 'min'이라는 변수를 두고 코드를 짰다고 가정했을때

swap을 하려고 한다면,,,

tmp=a[i];
a[i]=min;
min=tmp; //???

 

배열 a에다가 집어넣어야 할 값을 min에 다시 집어넣는 꼴이 되기 때문에

a의 원소끼리 맞바꾸는 과정이 없어지게 된다.

따라서 간접적으로 위치(idx)를 파악해서 맞바꿔야 한다.

 

응용)

내림차순 정렬해보기,

 

기준위치를 우측부터 잡고 진행해보기

 

등