선택 정렬

선택 정렬은 간단한 정렬 알고리즘 중 하나로, 배열이나 리스트를 정렬하는 데 사용된다. 동작 과정은 다음과 같다.

동작 과정

1. 주어진 리스트에서 최소값(또는 최대값)을 찾는다.
2. 찾은 값을 현재 정렬되지 않은 부분의 첫 번째 요소와 교환한다.
3. 정렬된 부분을 확장하고, 정렬되지 않은 부분에서 위 과정을 반복한다.

전체 코드

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_SIZE 10
#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )

int list[MAX_SIZE];
int n;

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;
		SWAP(list[i], list[least], temp);
	}
}

int main(void) {
	int i;
	n = MAX_SIZE;
	srand(time(NULL));
	for (i = 0; i < n; i++) 
		list[i] = rand() % 100;

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

시간 복잡도와 안정성

• 시간 복잡도: 최선, 평균, 최악의 경우 모든 이중 반복문이기 때문에 $O(n^2)$이다.
• 공간 복잡도: 제자리 정렬 방식으로 추가 메모리 사용 없기 때문에 $O(1)$이다.
• 안정성: 안정적이지 않음(동일한 값의 상대적 순서가 바뀔 수 있음)

출처
C언어로 쉽게 풀어쓴 자료구조 - 천인구