선택정렬 (Selection sort)

선택정렬 (Selection sort)은 데이터 전체에서 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환하는 방식으로 정렬한다. 버블정렬은 인덱스를 이동하면서 교환이 필요하면 즉시 교환했다. 하지만 선택정렬은 두항을 비교하고 작은 값이 저장된 요소값이 아닌 그 배열의 인덱스를 따로 저장한다. 그리고 단계가 끝마칠때 단 한번만 교환한다.

 

5,1,3,4,2 선택정렬 (오름차순)으로 정렬하기!

 

1단계  

5 [0]

1 [1]

3 [2]

4 [3]

2 [4]

선택된 항 = 0번째 인덱스 (현재 기준점 [0] )

0번째 1번째항 비교, 값은 그대로 두고 기준점만 변경

현재 기준점이 ( [1] )로 변경됨

이후 기준점 [1] 을 기준으로 나머지 2,3,4번째 항을 비교함

 

이후 마지막으로 최초 기준인덱스였던 0번째 인덱스와 최솟값으로 확인된 1번째 인덱스를 교환해줌으로

가장 작은 값을 0번 인덱스로 위치시킬수 있다.

 

이러한 방법으로 계속해 정렬해 나간다.

 

소스코드

#include<stdio.h>

int main(void)
{
	int alist[5] = { 5,1,3,4,2 };
	int i = 0, j = 0, tmp = 0, Minindex = 0;

	for (i = 0; i < 4; i++)
	{ 
		Minindex = i;
		for (j = i + 1; j < 5; j++)
			if (alist[Minindex] > alist[j])
				Minindex = j;
		if(Minindex != i)
			{
				tmp = alist[Minindex];
				alist[Minindex] = alist[i];
				alist[i] = tmp;
			}
	}

	for (i = 0; i < 5; ++i)
		printf("%d\t", alist[i]);
	printf('\n');
	return 0;
}

 

 

 

*즉시 값을 교환하는 것이 아니라 최솟값이 저장된 배열요소의 인덱스를 갱신한다는것을 생각하자!