C++에서 Quicksort 알고리즘 구현
이 기사에서는 C++에서 퀵 정렬 알고리즘을 구현하는 방법에 대한 여러 방법을 보여줍니다.
std::vector컨테이너에 대한 Quicksort 구현
Quicksort는 최신 코드베이스에서 사용되는 가장 빠른 범용 정렬 알고리즘 중 하나입니다. 병합 정렬 알고리즘과 유사한 분할 및 정복 기술을 사용합니다. 그러나 전자는 일반적으로 파티셔닝이라고하는 작업에 의존합니다. 원래 벡터는pivot이라는 요소에서 분할되며, 이는 이전에 더 작은 요소와 이후에 더 큰 요소를 구분합니다. 이러한 비교는 사용자가 선택해야하는 피벗 값을 기준으로합니다. 피벗 값을 선택하는 것이이 알고리즘의 성능에 중요한 요소가되며, 나중에이 기사에서 분석 할 것입니다. 이 시점에서 피벗 요소가 원래 벡터의 첫 번째 요소라고 가정합니다. 피벗 선택 방법이 있으면 벡터를 재귀 적으로 제자리에 정렬 할 두 개의 작은 벡터로 분할 할 수 있습니다. 빠른 정렬 작업은 시작 위치가 서로 교차 할 때까지 벡터를 여러 번 분할한다는 점에서 병합 정렬과 유사합니다.
다음 예제 코드는 호출 될 때마다partitionVec함수를 호출하는 재귀sort함수로 알고리즘을 구현합니다. 분할 프로세스는 동일한 벡터 객체의 요소를 교체하여 선형 시간으로 수행 할 수 있습니다. 후자의 작업은partitionVec함수를 사용하여 구현되며 특정 방식으로 정렬 함수로도 작동합니다.
#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>
T partitionVec(vector<T> &vec, size_t start, size_t end) {
T pivot = vec.at(start);
auto lh = start + 1;
auto rh = end;
while (true) {
while (lh < rh && vec.at(rh) >= pivot) rh--;
while (lh < rh && vec.at(lh) < pivot) lh++;
if (lh == rh) break;
T tmp = vec.at(lh);
vec.at(lh) = vec.at(rh);
vec.at(rh) = tmp;
}
if (vec.at(lh) >= pivot) return start;
vec.at(start) = vec.at(lh);
vec.at(lh) = pivot;
return lh;
}
template <typename T>
void sort(vector<T> &vec, size_t start, size_t end) {
if (start >= end) return;
auto boundary = partitionVec(vec, start, end);
sort(vec, start, boundary);
sort(vec, boundary + 1, end);
}
template <typename T>
void quickSort(vector<T> &vec) {
sort(vec, 0, vec.size() - 1);
}
int main() {
vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};
printVector(vec1);
quickSort(vec1);
printVector(vec1);
return EXIT_SUCCESS;
}
출력:
43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;
Quicksort 구현에서 재귀 수준 조사
Quicksort는 O (n log n) 평균 시간 복잡도를 가지며 이는 병합 정렬 알고리즘과 동등합니다. 그러나 퀵 정렬 알고리즘은 피벗 선택 방법에 크게 의존합니다. 이 경우 벡터의 첫 번째 요소 인 피벗 값을 선택하기 위해 순진한 버전을 선택했습니다. 이로 인해 특정 시나리오에서 O(n2)로 상당히 나쁜 실행 시간이 발생할 수 있습니다. 실제로 랜덤 피벗을 선택하면 O (n log n) 성능을 얻을 확률이 높습니다. 그러나 최대 성능이 필요한 경우 입력 데이터를 기반으로하는 피벗 선택 방법을 알고 있어야합니다.
sort함수의 각 호출을 계산하는 추가 함수 인수를 사용하여 이전 코드 스 니펫에서 재귀 프로세스를 관찰 할 수 있습니다. 다음 예제에서는 크기가 다른 두 벡터에 대해 유사한 테스트를 실행하고 해당 합계를 인쇄합니다. 재귀 호출의 합은 벡터 크기를2n - 1함수와 관련시킵니다. 여기서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>
auto partitionVec(vector<T> &vec, size_t start, size_t end) {
T pivot = vec.at(start);
auto lh = start + 1;
auto rh = end;
while (true) {
while (lh < rh && vec.at(rh) >= pivot) rh--;
while (lh < rh && vec.at(lh) < pivot) lh++;
if (lh == rh) break;
T tmp = vec.at(lh);
vec.at(lh) = vec.at(rh);
vec.at(rh) = tmp;
}
if (vec.at(lh) >= pivot) return start;
vec.at(start) = vec.at(lh);
vec.at(lh) = pivot;
return lh;
}
template <typename T>
void sort(vector<T> &vec, size_t start, size_t end, int &level) {
if (start >= end) return;
auto boundary = partitionVec(vec, start, end);
sort(vec, start, boundary, ++level);
sort(vec, boundary + 1, end, ++level);
}
template <typename T>
void quickSort(vector<T> &vec, int &level) {
sort(vec, 0, vec.size() - 1, ++level);
}
int main() {
vector<int> vec3(100, 10);
vector<int> vec4(200, 10);
int recursion_level = 0;
quickSort(vec3, recursion_level);
cout << "level: " << recursion_level << endl;
recursion_level = 0;
quickSort(vec4, recursion_level);
cout << "level: " << recursion_level << endl;
return EXIT_SUCCESS;
}
출력:
level: 199
level: 399
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