[C/C++] 선택 정렬(selection sort) 알고리즘을 활용한 오름차순정렬

선택 정렬이란?

선택 정렬(seleciton sort)은 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 정렬 방식입니다.

 

예를 들어 다음과 같이 1부터 10까지의 수를 무작위로 섞어놓은 배열이 있습니다.

값	5	6	10	4	3	8	7	1	2	9
위치	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]

 

5부터 9까지 훑어보면서 가장 작은 값을 찾아야 합니다.

 

5와 비교할 숫자는 다음에 오는 숫자 6부터 마지막 숫자까지 비교한다.

선택 정렬은 가장 작은 숫자와 가장 작은 숫자의 위치를 기억했다가 마지막 수까지 비교가 끝나면 마지막에 교환을 해줍니다.

이제 위치[0]의 정렬은 끝났습니다. 위 과정을 반복해 주면 됩니다.

 

#include <stdio.h>

int main(){
	//1~10 무작위 배열
	int arr[10] = {5, 6, 10, 4, 3, 8, 7, 1, 2, 9};
	int i, j, temp, index, min;
	
	for(i=0;i<10;++i){
		//가장 작은 수와 가장 작은수 위치 
		min = arr[i];
		index = i;
		//비교하여 가장 작은 수와 위치기록 
		for(j=i+1;j<10;++j){
			if(min>arr[j]){
				min = arr[j];
				index = j;
			}
		}
		//비교가 끝나면 교환 
		temp = arr[i];
		arr[i] = arr[index];
		arr[index] = temp;
	}
	
	//출력 
	for(i=0;i<10;++i){
		printf("%d ", arr[i]);
	}
	
	return 0;
}

 

결과값:

1 2 3 4 5 6 7 8 9 10

 

이렇게 선택 정렬을 통해 오름차순으로 정렬된 것을 확인할 수 있습니다.

내림차순으로 구현하려면 어떻게 해야 할까요?

 

비교할 때 min> arr [j]의 부호를 반대로 min <arr [j]로 해주면 내림차순으로 정렬됩니다.

 

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