선택 정렬(Selection Sort)

 

선택정렬은 가장 작은 값을 맨 앞으로 보내 정렬시키는 알고리즘입니다.

 

2, 5, 6, 4, 1, 10, 9, 8, 3, 7

위의 숫자 10개를 예로 들자면 

1. 0번째 인덱스부터 돌았더니 4번째 인덱스의 값이 제일 작다.

2. 0번째 인덱스의 값과 4번째 인덱스의 값을 서로 바꾼다.

3. 0번째 인덱스의 정렬은 끝났다.

 

1, 5, 6, 4, 2, 10, 9, 8, 3, 7

1. 1번째 인덱스부터 돌았더니 4번째 인덱스의 값이 제일 작다.

2. 1번째 인덱스의 값과 4번째 인덱스의 값을 서로 바꾼다.

3. 1번째 인덱스의 정렬은 끝났다.

 

1, 2, 6, 4, 5, 10, 9, 8, 3, 7

1. 2번째 인덱스부터 돌았더니 8번째 인덱스의 값이 제일 작다.

2. 2번째 인덱스의 값과 8번째 인덱스의 값을 서로 바꾼다.

3. 2번째 인덱스의 정렬은 끝났다.

 

1, 2, 3, 4, 5, 10, 9, 8, 6, 7

          .

          .

          .

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

 

이런식으로 진행한 다음에 마지막엔 배열을 처음부터 끝까지 다 출력하면 됩니다.

 

C언어로 작성한 소스는 다음과 같습니다.

#include<stdio.h>
int main()
{
	int min, index, temp;
	int array[10] = {2,5,6,4,1,10,9,8,3,7};
	
	for(int i=0; i<10; i++) //i번째부터 정렬시작 
	{
		min = 9999; //최솟값을 판별하기 위한 초기값 설정
		
		for(int j=i; j<10; j++) // 쭉 돌면서
		{
			if(min > array[j]) // 최솟값이 판별되면
			{
				min = array[j]; // 일단 해당 배열값을 최솟값으로 저장
				index = j; // 최솟값이 배열의 몇번째에 있는지도 저장
			}
		} // 이 for문을 나왔다 -> 최종적으로 최솟값이 정해졌다 
        
        // i번째랑 최솟값이 있는 곳이랑(index) 바꾸기
		temp = array[i]; 
		array[i] = array[index];
		array[index] = temp;
        // 여기까지 왔으면 i번째의 정렬이 끝남.
	}
	
	for(int i=0; i<10; i++){ //정렬된 배열 출력
		printf("%d ",array[i]);
	}
	
	return 0;
}

 

                                              선택 정렬의 시간 복잡도는 O(N^2)입니다.