선택 정렬(selection sort)

선택 정렬(selection sort)은 제자리 정렬 알고리즘중 하나이다.

입력 배열 이외에 다른 추가 메모리를 요구하지 않고, 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다.

 

따라서 자료 이동 횟수가 미리 결정되어 있지만, 같은 값이 같은 배열에 있을 경우에 상대적인 위치가 변경될 수 있어서 안정성을 만족하지 않는다.

 

#include <stdio.h>
#define SIZE 5

void selection_sort(int arr[],int n);

int main()
{
	int arr[SIZE]={9,6,7,3,5};

	selection_sort(arr,SIZE);

	for(int i=0;i<SIZE;i++)
		printf("%d ",arr[i]);
	printf("\n");
}

void selection_sort(int arr[],int n)
{
	int i,j,min,tmp;

	for(i=0;i<n-1;i++){
		min=i;
		for(j=i+1;j<n;j++){
			if(arr[j]<arr[min])
				min=j;
		}
		if(i != min){
			tmp=arr[min];
			arr[min]=arr[i];
			arr[i]=tmp;
		}
	}
}