선택 정렬

선택 정렬: 가장 작은 것을 반복적으로 선택하여 제일 앞으로 보내는 정렬 알고리즘.

 

정렬이 안된 숫자들 중에서 최소값을 선택하여 배열의 맨 앞쪽 요소와 교환한다.

 

Ex)

정렬할 데이터 :

 

1 10 5 8 7 6 4 3 2 9

1 2 5 8 7 6 4 3 10 9

1 2 3 8 7 6 4 5 10 9

1 2 3 4 7 6 8 5 10 9

~

1 2 3 4 5 6 7 8 9 10

 

시간복잡도 : O(N^2)

최악의 경우 연산의 횟수가 기하급수적으로 늘어나므로 비효율적인 정렬 알고리즘.

 

#include <stdio.h>
#include <limits.h> 
int main()
{
	int i, j, min, index, temp; 	// index : 가장 작은 원소가 존재하는 위치 
	int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
	for(i = 0; i<10; i++)
	{
		min = INT_MAX;
		for(j=i; j<10; j++)
		{
			if(min>array[j]) {
				min = array[j];
				index = j;
			}  
		}   
		temp = array[i];
		array[i] = array[index];
		array[index] = temp;
		// 반복적으로 가장 작은 값의 위치를 선택해서 앞으로 옮겨줌. 
	}
	for(i=0; i<10; i++)
	{
		printf("%d ", array[i]);
	}
	
	
	return 0;
}