단순 선택 정렬

선택정렬 :
리스트 중 가장 작은 숫자를 선택하여 왼쪽 부터 정렬시켜 나가는 작업을 반복하는 정렬이다.

• 가장 작은 요소부터 정렬하는 알고리즘
• 아직 정렬하지 않은 부분에서 가장 작은 키의 값(a[min])을 선택
• a[min]과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환

/*--- 단순 선택 정렬 ---*/
#define swap(type, x, y) do { type t = x; x = y; y = t; } while (0)

void selection(int a[], int n)
{
	int i, j;
	for (i = 0; i < n - 1; i++) {
		int min = i;
		for (j = i + 1; j < n; j++)
			if (a[j] < a[min])
				min = j;
		swap(int, a[i], a[min]);
	}
}

단순 선택 정렬의 시간복잡도

• 비교횟수 : (n-1) + (n-2) + ... + 1 = n(n-1)/2
• 시간복잡도 : O(n^2)

단순 선택 정렬은 unstable sort

동일한 키값이 있는 경우, 위치가 뒤바뀌는 안정적이지 않은 정렬이다. (unstable sort)

원래 데이터에서는 3L이 3R보다 앞에 있었다. 하지만 정렬 후에는 위치가 바뀌어 3R이 앞에 있다.

안정성이 있는 정렬이란?

: 입력 데이터에 동일한 키 값을 갖는 레코드가 여러 개 존재할 경우 이들의 상대적인 위치가 정렬 후에도 그대로 바뀌지 않는 것을 안정성 있는 정렬이라고 한다.

-> 선택정렬은 안정성이 없고 비효율적이지만 구조가 단순하여 구현이 간단하다는 장점이 있다.

참고)

• (내 손으로 직접 코딩하며 확인한다!) 자료구조와 함께 배우는 알고리즘 입문 - C 언어 편
• https://wonjayk.tistory.com/217?category=558920