Selection Sort

기본 아이디어

정렬 중간 과정에 데이터가 두 부분으로 나뉘어 진다.

왼쪽 데이터

정렬이 된 데이터가 들어있으며 오른쪽 데이터에서 가장 작은 수부터 정렬된다.

오른쪽 데이터

정렬이 되지 않은 데이터가 들어있으며. 오른쪽 데이터에서 가장 작은 수와 오른쪽 데이터의 제일 앞 수를 교환한다.

---

---

특징

In-Place Algorithm : 입력 데이터를 저장하는 메모리 이외에 상수 메모리만 필요하다.
Unstable sorting Algorithm : 크기가 같은 데이터가 정렬된 이후에 입력된 순서를 유지하지 못한다.
big-O notation : O($n^2$)의 시간 복잡도를 가지고 있다.

구현

void swap(int& i, int& j) {
	int k;
	k = i;
	i = j;
	j = k;
}


void SelectionSort(vector<int>&A) {
	int countCmpOps = 0; // 비교 연산자 실행 횟수
	int countSwaps = 0; // swap 함수 실행 횟수
	int n = A.size();
	int jMin;
	for (int i = 0; i < n - 1; i++) {
		jMin = i;
		for (int j = i + 1; j < n; j++) {
			if (A[j] < A[jMin]) {
				jMin = j;
			}
			countCmpOps++;
		}
		if (jMin != i) {
			swap(A[jMin], A[i]);
			countSwaps++;
		}
	}
	cout << countCmpOps << " " << countSwaps << endl;
}