[정렬] 선택 정렬

1. 설명

 

• 가장 작은(혹은 가장 큰) 값을 찾아 **제일 앞(혹은 뒤)**으로 이동.
• O(n²)의 시간복잡도를 가짐.
• 작은 데이터에 적합하지만, 성능이 좋지 않음.

 

2. 코드

#include <iostream>
#include <vector>

using namespace std;

void selectionSort(vector<int>& arr) {
	int n = arr.size();

	for (int i = 0; i < n - 1; i++) {
		int minIndex = i;

		for (int j = i + 1; j < n; j++)
		{
			if (arr[j] < arr[minIndex])
				minIndex = j;
		}
		swap(arr[i], arr[minIndex]);
	}

}


int main() {
	vector<int> arr = { 64, 25, 12, 22, 11 };
	selectionSort(arr);

	for (int num : arr) cout << num << " ";

}