[알고리즘] 선택 정렬(Selection Sort)

선택 정렬은 가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘이다.

 

#include<stdio.h>

int main()
{
	int i, j, temp, min, index;
	int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};	
	min = 9999;
		
	for(i=0; i<10; i++) {
		min = 9999; // min 값을 지속적으로 가장 큰 값으로 초기화 하는 이유는 그렇지 않으면 
        			// min 값에 가장 작은 값이 계속 저장되어 array[j]>min 경우만 발생한다.
		
		for(j =i; j<10; j++){
			if(array[j]<min)
			{			
				min = array[j];
				index = j;
			}
		}
		temp = array[i];
		array[i] = min;
		array[index] = temp;
		
	}
	
	for(i=0; i<10; i++)
	{
		printf("%d, ",array[i]);
	}
	
	return 0;
}

 

선택 정렬은 등차 수열로 진행된다.

배열에 {1, 2, 3, 4, 5 ,6 ,7 ,8 9, 10} 값이 무질서하게 정렬 되었을 때 

선택 정렬을 사용한다면

반복문은 10 + 9 + 8 ... + 1 이런 식으로 반복 된다.

이런 원리를 나타내는 경우 이런 식으로 변경할 수 있다. 

=> (10 * (10+1))/2

=> N * (N + 1) / 2

tip) 빅오 표기법 특정한 알고리즘의 수행시간을 간략하게 나타내는 표기법이다.

선택 정렬의 시간 복잡도 => O(n^2)