선택 정렬

• 선택 정렬(Selection sort)

  선택 정렬(selection sort)은 말 그대로 선택하면서 정렬이 진행된다. N개의 정렬되지 않은 데이터가 주어진다면 N개 중 가장 작은 데이터를 선택한다. 그 다음 N-1개 중 가장 작은 데이터를 선택하면서 총 N번 반복 선택하여 정렬을 진행한다. 시간 복잡도는 $O(\frac { n(n+1) }{ 2 } )\approx O({ n }^{ 2 })$이다.

---

• 예시)

  1회전 :

  10 6 1 3 4

  1 6 10 3 4

  2회전 :

  1 6 10 3 4

  1 3 10 6 4

  3회전 :

  1 3 10 6 4

  1 3 4 6 10

---

• 코드 구현(C++)

#include <iostream>
#include <algorithm>
using namespace std;
int A[5] = { 10,6,1,3,4 };
void print_arr() {
	cout << "\n";
	for (int i = 0; i < 5; i++) cout << A[i] << " ";
	cout << "\n";
}
int main(void) {
	for (int i = 0; i < 5; i++) {
		int idx = i;
		for (int j = i; j < 5; j++) {
			if (A[idx] > A[j]) {
				idx = j;
			}
		}
		if (idx != i) swap(A[i], A[idx]);
		print_arr();
	}
	return 0;
}

---

• 결과