Best Case : $\Omega(n^2)$

Average Case : $\Theta(n^2)$

Worst Case : $O(n^2)$

우리말로 선택 정렬이라고 하는 Selection Sort 알고리즘은 max값을 갖고 하나하나 비교해나가는 알고리즘이다.

[출처] : ESSLAB "Algorithm" Lecture Note - Elementary Sorting

1. 첫번째 원소부터 N번째 원소를 max값과 비교한다.
2. 이때 max값 보다 큰 값이 나타나면, 나타난 값으로 max값을 업데이트 한다.
3. N번째까지 비교한 후, 검사한 맨 뒤의 값과 max값을 Swap한다.
4. N의 크기를 1킨 줄인다.
5. 1~4의 과정을 N번 반복한다.

따라서 제일 큰 값은 맨뒤로가게 되고, 뒤에서부터 순차적으로 정렬되게 된다.

때로는 반대로 각 원소 중에서 작은것을 찾고 맨앞의 원소와 Swap하기도 한다.

Pseudo Code

SELECTION-SORT(A)
	while N>0
		for i <- 1 to N 
			if(A[i]>A[max]) 
				do max <- A[i]
		swap(A[N-1], A[max])             
	

아래는 위의 코드를 바탕으로 C언어로 구현한 것이다.