C++/알고리즘 개념
[ C++ / 정렬 ] 선택 정렬
코딩하는 공대생
2023. 10. 16. 21:25
반응형
https://blog.naver.com/ndb796/221226800661
2. 정렬의 개요와 선택 정렬(Selection Sort)
일반적으로 알고리즘을 공부할 때 가장 먼저 풀어보는 문제는 '정렬(Sort)' 문제입니다. 왜냐하면 ...
blog.naver.com
이코테 저자님의 블로그를 참고했습니다 !
'정렬(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)이다.
반응형