[알고리즘] 선택정렬(SelectionSort)

 

위 GIF에서 볼 수 있듯이

최소값(Minimum) 을 찾아 swap 해줌으로써 

정렬을 완성해나가는 식이다.

 

내 기준 선택정렬이 가장 떠올리기 어려운 정렬이다.

이름만으로는 감이 안온다

 

모든 정렬 알고리즘에서 "선택" 은 항상 존재한다. 

따라서 "선택"이라는 단어가 정렬 알고리즘 상에서 매우 보편적인 단어인데

이걸 정렬방법 이름으로 써놨다. 그냥 답이 없다

 

void SelectSort(int arr[], int n) {
	int idx;
	for (int i = 0; i < n-1; i++) {
		idx = i;
		for (int k = i+1; k < n; k++) {
			if (arr[idx] > arr[k]) {
				idx = k;
			}
		}
		int temp = arr[idx];
		arr[idx] = arr[i];
		arr[i] = temp;
	}
}

 

int main() {
	int arr[6] = { 4,2,1,7,3,5};
	SelectSort(arr, 6);
	for (int i = 0; i < 6; i++) printf("%d ", arr[i]);
	return 0;
}

 

잘 돌아간다

 

---

[ 시간복잡도 계산 ] 

[ 점화식 ]

 

얘도 버블정렬하고 똑같다.

만약 한 개의 데이터가 맨 뒤에 추가된다면

T(N-1)일때보다 N-1만큼의 비교연산이 추가된다.

왜냐하면 N-1개의 원소들의 비교연산이 한번씩만 추가되는 것이므로!

 

따라서 O(N^2)이 나온다.

 

[ 노가다 ]

 

얘는 구조가 버블정렬과 좀 다르다.

 

일단 교환 코드가 2번째 for문 밖에 있다.

하지만 이는 최악의 경우와 상관이 없다

왜? 최악의 경우는 비교연산 쪽에서 결정나기 때문이다

 

최악의 경우는 생각해볼 필요가 없다!

 

마지막 for문의 비교연산에는 탈출문이 없기 때문에

무조건 끝까지 돌 다 나오는 놈이기 때문이다!

 

따라서 얘도 버블정렬과 똑같이 O(n^2)이다

이것도 버블정렬과 똑같다

 

그럼 (N-1) + (N-2) + ..... + 3 + 2 + 1 이므로 O(N^2) 나옴