선택정렬 : Selection Sort

복잡도가 인 가장 간단한 정렬 알고리즘

 

 

선택정렬의 동작 순서는 다음과 같다.

 

1. 가장 큰 값을 찾는다.

 

2. 1에서 찾은 가장 큰 값과 배열의 마지막 원소를 바꾼다.

 

3. 배열의 마지막원소는 정렬이 되었다고 가정하고 이를 제외한 나머지 원소들로 1과2를 반복한다.

 

 

 

 

이를 간단하게 코드로 나타내보면 다음과 같다.

 

selection_sort(num[], n){
	for last = n downto 2{
		num[1....last] 중 가장 큰 수 num[k]를 찾음;
		num[k]와 num[last]를 바꿈;
	}
}

 

 

결국, 선택정렬 알고리즘은 크게

 

1. 정렬을 수행하는 부분 ( 값 교환 )

 

2. 큰 값을 찾는 부분

 

으로 나누어 볼 수 있다.

 

 

각 부분을 C++로 작성한 코드는 다음과 같다.

 

1. 정렬을 수행하는 부분

void selection_Sort(int nums[], int n) {
	int large = 0;
	for (int i = n-1; i >= 0; i--) {
		large = largest(nums, i);
		swap(nums[large], nums[i]);
	}
}

 

2. 큰 값을 찾는 부분

int largest(int nums[], int last) {

	int large = 0;
	int large_num = nums[0];
	for (int i = 0; i <= last; i++) {
		if (nums[i] > large_num) {
			large = i;
			large_num = nums[i];
		}
	}
	return large;
}