선택 정렬(Selection Sort)

https://github.com/GimunLee/tech-refrigerator/raw/master/Algorithm/resources/selection-sort-001.gif

 

개인적으로 가장 직관적이고 구현하기 쉬운방법 인것같다

반복문이 돌때마다 최솟값을 찾아서 해당 index에 배치하면 된다 

버블 정렬과 비슷하지만 교환이 일어나는 횟수는 버블정렬에 비해 적다

시간복잡도는 O(N^2)으로  10개의 배열의 경우 첫번째 배열에서 9개의 원소를 탐색

그다음은 8개 .. 7개.. 이런식으로 최악의 경우와 최선의 경우 상관없이

n-1 + n-2 + ... + 1 이런식이며

n(n-1)/2으로 시간복잡도는 O(N^2)이다.

#include <iostream>

using namespace std;

int main() {
	int arr[] = { 6,9,8,1,3,4,2,5,7 };
	int arrSize = sizeof(arr) / sizeof(int);
	int tmp;
	for (int i = 0; i < arrSize - 1; i++) {
		int min = i;
		for (int j = i + 1; j < arrSize; j++) {
			if (arr[min] > arr[j]) {
				min = j;
			}
		}
		tmp = arr[i];
		arr[i] = arr[min];
		arr[min] = tmp;
	}

	for (int i = 0; i < arrSize; i++) {
		cout << arr[i] << " ";
	}

}