Selection Sort?

• 가장 단순한 정렬 방법 중 하나
• 가장 작은 숫자를 차례대로 탐색 후, 가장 왼쪽 자리부터 swap
• 가장 작은 숫자를 선택하는 방식으로 정렬을 진행함.

Code

void selectionsort(int n, keytype S[])
{
	index i, j, smallest;
	
	for(i=0; i<n-1; i++){
		smallest = i;
		for(j=i+1; j<=n; j++){
			if(S[j] < S[smallest])
				smallest = j;
		}
		exchange S[i] and S[smallest];
	}
}

Time Complexity

• Worst : $O(n^2)$
• Average : $O(n^2)$
• Best : $O(n^2)$