선택정렬(selection sort)

오름차순을 기준으로 정렬한다

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

선택정렬(selection sort)의 시간 복잡도

• T(n)=(n-1)+(n-2)+...2+1=n(n-1/2=O(n^2)

Name	Best	Avg	Worst	Run-time (int 60,000) sec
버블정렬	n^2	n^2	n^2	22.89
선택정렬	n^2	n^2	n^2	10.84
삽입정렬	n	n^2	n^2	7.43
셀정렬	n	n^1.5	n^2	0.05
퀵정렬	nlog₂n	nlog₂n	n^2	0.01
힙정렬	nlog₂n	nlog₂n	nlog₂n	0.03
병합정렬	nlog₂n	nlog₂n	nlog₂n	0.02

 

 

#include<stdio.h>
#define SWAP(x,y,temp)((temp=(x),(x)=(y),(y)=(temp)))
#define MAX_SIZE 5

void selection_sort(int list[], int n)
{
	int i, j, least, temp;

	for (i = 0; i < n - 1; i++)
	{
		least = i;

		for (j = i + 1; j < n; j++)
		{
			if (list[j] < list[least])
				least = j;
		}

		if (i != least)
		{
			SWAP(list[i], list[least], temp);
		}
	}
}

int main()
{
	int i;
	int n = MAX_SIZE;
	int list[] = { 9,6,7,3,5 };

	selection_sort(list, n);

	for (i = 0; i < n; i++)
	{
		printf("%d", list[i]);
	}
}