C++에서 선택 정렬 알고리즘 구현
이 기사에서는 C++에서 선택 정렬 알고리즘을 구현하는 방법을 설명합니다.
C++에서std::vector컨테이너에 대한 선택 정렬 구현
간단한 정렬 알고리즘 중에서 선택 정렬을 구현하기 가장 간단한 것으로 간주 할 수 있습니다. 그러나 O(n2) 복잡성이 있고 큰 벡터에서 완전히 비효율적입니다.
선택 정렬은 다음 루틴으로 지정할 수 있습니다. 처음에는 벡터에서 최소값을 찾아 첫 번째 요소로 교체합니다. 그런 다음 포인터를 두 번째 요소로 이동하고 나머지 하위 벡터에서 두 번째 요소와 교체 할 최소값을 찾습니다. 포인터를 한 번에 한 요소 씩 이동하면서 나머지 벡터에 대해 이전 단계를 계속합니다.
선택 정렬에 대한 다른 설명은 입력 벡터를 두 부분으로 나누는 것이라고 말할 수 있습니다. 첫 번째는 정렬 된 하위 벡터이고 두 번째는 정렬되지 않은 요소의 나머지 하위 벡터 (원래 순서)입니다. 정렬 된 하위 벡터가 주어진 벡터에 존재한다고 가정 할 수 없기 때문에 정렬 된 하위 벡터와 정렬되지 않은 하위 벡터 사이의 제수로 첫 번째 요소를 선택해야합니다. 따라서 최소값을 시작 위치의 요소로 교체하기 시작할 때. 벡터는 자연스럽게 정렬 된 부분과 정렬되지 않은 부분으로 나뉩니다.
다음 예제에서는std::vector객체에 대한 참조를 가져와 요소의 내부 수정을 수행하는selectionSort함수를 구현합니다. std::min_element알고리즘을 사용하여 각 반복에서 최소값을 찾았습니다. 이것은 처음으로 알고리즘을 더 잘 이해하는 데 도움이됩니다.
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
template <typename T>
void selectionSort(vector<T> &vec) {
for (auto it = vec.begin(); it != vec.end(); ++it) {
std::swap(*it, *std::min_element(it, vec.end()));
}
}
int main() {
vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};
printVector(vec1);
selectionSort(vec1);
printVector(vec1);
return EXIT_SUCCESS;
}
출력:
43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;
또는 각 반복의 나머지 정렬되지 않은 하위 벡터에 대한 최소값을 찾는 두 번째for루프를 사용하여selectionSort함수를 다시 작성할 수 있습니다. 이 버전은 알고리즘 복잡도 분석에 적합합니다. 선택 정렬 알고리즘에는 2 차 실행 시간이 있지만 병합 정렬 또는 힙 정렬과 같은 O (n log n) 알고리즘에 비해 작은 벡터에서 놀랍도록 효율적일 수 있습니다. 우리는 여전히 하나의 STL 함수 인std::swap을 사용합니다. 이것은이 경우에 일정한 시간 연산이며, 코드 예제를 간결하게하는 데 유용합니다.
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
template <typename T>
void selectionSort(vector<T> &vec) {
for (auto it = vec.begin(); it != vec.end(); ++it) {
auto min = it;
for (auto i = it + 1; i != vec.end(); ++i) {
if (*i < *min) min = i;
}
std::swap(*it, *min);
}
}
int main() {
vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};
printVector(vec1);
selectionSort(vec1);
printVector(vec1);
return EXIT_SUCCESS;
}
출력:
43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook