C++ 표준 템플릿 라이브러리(STL)에서 정렬
-
sort()함수를 사용하여 C++에서 배열 또는 STL 컨테이너 정렬 - C++에서 내림차순으로 배열 정렬
-
partial_sort()함수를 사용하여 배열 또는 벡터의 일부 정렬 -
C++에서
sort()함수를 사용한 사용자 정의 또는 사용자 정의 정렬 -
C++에서
is_sorted()메서드 사용 - 정렬 알고리즘의 시간 복잡성
이 튜토리얼에서는 sort()라는 널리 사용되는 C++ 함수에 대해 배울 것입니다. 정렬과 관련된 다른 기능도 살펴보겠습니다.
C++에서 데이터를 정렬하려면 알고리즘을 작성하고 데이터에 적용하거나 C++ STL에 있는 내장 함수 sort()를 사용할 수 있습니다. sort() 함수는 algorithm 헤더 파일에 정의되어 있습니다.
이 함수는 Quicksort, Heapsort, Insertion sort의 세 가지 정렬 알고리즘을 사용하여 실행 시간을 최소화하는 하이브리드 정렬 알고리즘인 IntroSort 알고리즘을 사용합니다.
이 함수는 주어진 범위의 요소를 정렬합니다.
통사론:
sort(start iterator, end iterator, compare_function)
이것은 기본적으로 시작 반복자와 끝 반복자가 정의한 범위의 요소를 오름차순으로 정렬합니다(기본 compare_function).
sort() 함수를 사용하여 C++에서 배열 또는 STL 컨테이너 정렬
정렬은 데이터에 대해 수행되는 기본 작업 중 하나입니다. 데이터를 증가, 감소 또는 사용자 정의(사용자 정의 정렬) 방식으로 정렬합니다.
sort() 함수를 사용하여 C++에서 vector, set, map 등과 같은 배열 또는 STL 컨테이너를 정렬할 수 있습니다.
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
int arr[] = {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};
// array size
int n = sizeof(arr) / sizeof(arr[0]);
vector<int> v{35, 67, 11, -9, 7, -22}; // vector
cout << "The array after sorting is : \n";
sort(arr, arr + n);
sort(v.begin(), v.end()); // sorting vector
for (int i = 0; i < n; ++i) cout << arr[i] << " ";
cout << endl;
cout << "The vector after sorting is : \n";
for (int i = 0; i < v.size(); ++i) cout << v[i] << " ";
}
출력:
The array after sorting is :
0 1 2 3 4 5 6 7 8 9
The vector after sorting is :
-22 -9 7 11 35 67
항목은 기본적으로 오름차순으로 정렬됩니다.
C++에서 내림차순으로 배열 정렬
C++ STL에 있는 배열이나 컨테이너를 내림차순으로 정렬하려면 sort() 함수에서 greater<type>()이라는 세 번째 매개변수를 전달해야 합니다. 이 함수는 끝에 있는 요소가 내림차순으로 정렬되도록 비교를 수행합니다.
Type은 사용 중인 배열 또는 컨테이너의 유형, int, float 또는 string 유형을 나타냅니다.
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
int arr[] = {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};
// array size
int n = sizeof(arr) / sizeof(arr[0]);
vector<int> v{35, 67, 11, -9, 7, -22}; // vector
cout << "The array after sorting is : \n";
sort(arr, arr + n, greater<int>());
sort(v.begin(), v.end(), greater<int>()); // sorting vector
for (int i = 0; i < n; ++i) cout << arr[i] << " ";
cout << endl;
cout << "The vector after sorting is : \n";
for (int i = 0; i < v.size(); ++i) cout << v[i] << " ";
}
출력:
The array after sorting is :
9 8 7 6 5 4 3 2 1 0
The vector after sorting is :
67 35 11 7 -9 -22
partial_sort() 함수를 사용하여 배열 또는 벡터의 일부 정렬
partial_sort()를 사용하여 배열의 일부만 정렬할 수 있습니다. 이 방법은 원래 정렬 방법의 변형에 불과합니다.
통사론:
partial_sort(first, middle, last)
범위(first, last)의 요소를 재정렬하여 가운데 앞의 요소는 오름차순으로 정렬되고 중간 이후의 요소는 특정 순서 없이 남도록 합니다.
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
vector<int> vr{35, 67, 11, -9, 7, -22}; // vector
cout << "The vector after partial sorting is : \n";
partial_sort(vr.begin(), vr.begin() + 2, vr.end());
for (int i = 0; i < vr.size(); ++i) cout << vr[i] << " ";
}
출력:
The vector after partial sorting is :
-22 -9 67 35 11 7
처음 두 개의 요소만 정렬되어 있고 나머지는 임의의 순서로 존재한다는 것을 알 수 있습니다.
C++에서 sort() 함수를 사용한 사용자 정의 또는 사용자 정의 정렬
데이터를 오름차순 또는 내림차순으로 정렬하려는 경우 이 기능을 사용할 수 있지만 데이터를 사용자 정의 방식으로 정렬해야 하는 경우가 있습니다.
여기에서 sort() 함수의 세 번째 매개변수로 전달할 사용자 정의 정렬 함수를 작성해야 합니다.
#include <algorithm>
#include <iostream>
using namespace std;
bool myfunction(string x, string y) { return x.size() < y.size(); }
int main() {
string str[] = {"a", "abc", "ba", "abcd"};
int n = 4;
sort(str, str + n); // normal sort function
cout << "Array after sorting : \n";
for (int i = 0; i < n; ++i) cout << str[i] << " ";
cout << endl;
sort(str, str + n, myfunction);
cout << "Array after user defined sorting : \n";
for (int i = 0; i < n; ++i) cout << str[i] << " ";
}
출력:
Array after sorting :
a abc abcd ba
Array after user defined sorting :
a ba abc abcd
첫 번째 정렬 방법은 기본적으로 사전식 오름차순으로 문자열 배열을 정렬합니다. 두 번째 정렬 방법은 길이, 즉 myfunction이라는 사용자 정의 비교 기능에서 언급한 조건을 기준으로 문자열을 정렬합니다.
C++에서 is_sorted() 메서드 사용
주어진 데이터 범위가 정렬되었는지 여부를 확인하려면 이 방법을 사용할 수 있습니다.
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
vector<int> v{35, 67, 11, -9, 7, -22}; // vector
cout << is_sorted(v.begin(), v.end());
}
출력:
0
벡터가 정렬되지 않았기 때문에 거짓을 의미하는 0으로 출력을 얻습니다.
정렬 알고리즘의 시간 복잡성
sort()는 O(NlogN)의 시간 복잡도를 가지며, 여기서 N은 sort() 함수가 적용되는 요소의 수입니다.
