[ C++ / 정렬 ] 선택 정렬

https://blog.naver.com/ndb796/221226800661

2. 정렬의 개요와 선택 정렬(Selection Sort)

이코테 저자님의 블로그를 참고했습니다 ! 

 

'정렬(sort)' 은 알고리즘의 효율성 차이를 극명하게 보여준다.

 

선택 정렬은 가장 직관적인 정렬 방법이다.

방법은 간단한데, 가장 작은 값을 선택해 가장 앞으로 보내주기만 하면 된다.

 

다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요 

1 10 5 8 7 6 4 3 2 9

 

#include <bits/stdc++.h>

using namespace std;

int main() {
	vector<int> arr = { 1,10,5,8,7,6,4,3,2,9 };
	for (int i = 0; i < arr.size()-1; i++) {
		int minV = 2e7;
		int idx = 0;
		for (int j = i; j < arr.size(); j++) {
			if (minV > arr[j]) {
				minV = arr[j];
				idx = j;
			}
		}
		int temp = arr[i];
		arr[i] = minV;
		arr[idx] = temp;
	}

	for (int i : arr) cout << i << ' ';

	return 0;
}

이런식으로 짜면 될 거 같다.

 

아 그리고 int arr[] = {} 으로 진행했더니 size()랑 length() 둘 다 안먹히는 현상이 발생했다. 

GPT가 그렇다고 하니 그냥 넘어가야지....흠

 

아무튼 위의 코드를 잘 보면, 시간 복잡도는 O(N^2)이라는 것도 알 수 있다. 

 

=> 정리 : 선택 정렬은 최솟값을 선택해서 맨 앞으로 보내주는 정렬이다. 시간 복잡도는 O(N^2)이다.