C++에서 삽입 정렬 알고리즘 구현
이 기사에서는 C++에서 삽입 정렬 알고리즘을 구현하는 방법을 보여줍니다.
C++에서std::vector컨테이너에 대한 삽입 정렬 구현
이 가이드에서는std::vector객체에 대한 참조를 가져 와서 내용을 수정하는 별도의 함수로 삽입 정렬을 구현하는 방법을 보여줍니다. 삽입 정렬은 벡터의 각 요소를 반복합니다. 현재 요소와 이전 요소를 역순으로 비교하여 현재 위치 이전의 모든 요소가 정렬되도록합니다.
일반적으로 비교 순서는 알고리즘 성능에서 크게 중요하지 않지만 역순으로 가정하고 그에 따라 코드를 구현합니다. 또한 요소를 오름차순으로 정렬한다고 가정합니다. 그러나 실제 경우 일반 정렬 알고리즘은 사용자 지정 비교 함수를 인수로 사용할 수 있어야합니다. 비교 연산은 현재 요소가 이전 요소보다 작 으면 요소가 오른쪽으로 이동하도록하는 경우가 많습니다. 후자의 연산은 다른 중첩for루프를 사용하여 구현되며, 이는 잘못된 순서의 요소에 대해std::swap함수를 호출합니다.
다음 코드 스 니펫에는 외부for루프가 전체 배열 순회를 담당하는insertionSort함수가 포함되어 있습니다. 다음 단계는 이전 단계와의 비교를 포함하기 때문에 벡터의 두 번째 요소로 반복기를 초기화합니다. 내부 루프는 현재 요소에서 첫 번째 요소로 반복하여 비교합니다. 비교 함수가true로 평가되면 쌍이 스왑됩니다. else표현식은 하나 이상의 이전 요소가 현재 요소보다 작은 것으로 판명 될 때 내부 루프를 강제 종료합니다.
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
template <typename T>
void insertionSort(vector<T> &vec) {
for (auto it = vec.begin() + 1; it != vec.end(); ++it) {
auto key = it;
for (auto i = it - 1; i >= vec.begin(); --i) {
if (*i > *key) {
std::swap(*i, *key);
key--;
} else {
break;
}
}
}
}
int main() {
vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};
printVector(vec1);
insertionSort(vec1);
printVector(vec1);
return EXIT_SUCCESS;
}
출력:
43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;
또는while루프 구성을 사용하여insertionSort함수를 다시 구현할 수 있습니다. 후자가 사용자에게 더 읽기 쉬운 형식으로 선호되는 경우. 두 알고리즘은 유사한 구현 로직을 따르며 둘 다std::swap함수를 사용하여 요소를 이동합니다. 삽입 정렬은 대규모 데이터 세트에서 상당히 비효율적 인 알고리즘이며 평균 성능은 O(n2)입니다.
삽입 정렬은 선택 정렬이라고하는 또 다른 2 차 알고리즘과 유사합니다. 둘 다 벡터를 반복합니다. n반복 후에 첫 번째n요소가 정렬됩니다. 그러나 선택 정렬은 삽입 정렬과 달리 현재 위치에서 앞으로 요소를 평가합니다.
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
template <typename T>
void insertionSort2(vector<T> &vec) {
auto iter = vec.begin() + 1;
while (iter != vec.end()) {
auto key = iter;
auto it = iter - 1;
while (it >= vec.begin() && *it > *key) {
std::swap(*it, *key);
key--;
it--;
}
iter++;
}
}
int main() {
vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};
printVector(vec1);
insertionSort2(vec1);
printVector(vec1);
return EXIT_SUCCESS;
}
출력:
43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;
삽입 정렬은 다른 O(n2) 알고리즘에 비해 실제로 더 효율적일 수 있습니다. 항상 현재 요소를 모든 이전 요소와 비교할 필요가 없기 때문입니다. 한편, 선택 정렬은 가장 작은 (또는 가장 큰) 요소를 찾기 위해 항상 정렬되지 않은 하위 배열의 모든 요소를 검색해야합니다. 후자 클래스가 비교 연산자 오버로드를 구현하기 때문에std::string벡터에서insertionSort함수 구현을 모두 활용할 수 있습니다. 다음 예제는 string 형 벡터의 기본적인 사용법을 보여주고 정렬 된 단어 목록을 인쇄합니다.
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
template <typename T>
void insertionSort(vector<T> &vec) {
auto iter = vec.begin() + 1;
while (iter != vec.end()) {
auto key = iter;
auto it = iter - 1;
while (it >= vec.begin() && *it > *key) {
std::swap(*it, *key);
key--;
it--;
}
iter++;
}
}
int main() {
vector<string> vec2 = {"highway", "song", "work",
"borland", "death", "woman"};
printVector(vec2);
insertionSort(vec2);
printVector(vec2);
return EXIT_SUCCESS;
}
출력:
highway; song; work; borland; death; woman;
borland; death; highway; song; woman; work;
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