C++ std 라이브러리에서 sort() 사용
소개
이봐! 오늘 우리는 C++의 std 라이브러리에 있는 sort() 함수에 대해 논의할 것입니다.
기본적으로 정렬은 항목을 체계적으로 정렬하는 프로세스입니다. 이러한 항목은 시퀀스 또는 모든 데이터 구조의 요소가 될 수 있습니다.
C++에서 표준 라이브러리는 이 정렬 작업을 수행하기 위해 사전 정의되고 바로 사용할 수 있는 함수 sort()를 제공합니다. 그럼 바로 시작하겠습니다.
C++의 std::sort() 함수
C++의 std::sort() 함수는 특정 순서로 모든 형태의 데이터 구조를 정렬하는 데 사용되는 내장 함수입니다. algorithm 헤더 파일에 정의되어 있습니다. sort() 함수 프로토타입은 다음과 같습니다.
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
여기서 함수는 아무 것도 반환하지 않습니다. 첫 번째에서 마지막 이터러블 또는 위치까지 요소/항목을 업데이트합니다. 세 번째 매개변수(선택사항) comp는 요소가 정렬될 순서를 결정하는 함수여야 합니다. 지정하지 않으면 기본적으로 std::less 함수로 간주하여 오름차순으로 정렬합니다.
sort() 함수는 Introsort라는 3중 하이브리드 정렬 기술을 사용합니다. 퀵 정렬, 힙 정렬, 삽입 정렬의 조합입니다.
C++에서 sort() 함수를 사용하여 데이터 정렬
이제 sort() 함수의 기본 사항을 살펴보았으므로 C++ 프로그램에서 이 함수를 사용하여 일부 데이터 구조(예: 배열)를 정렬해 보겠습니다.
1. 오름차순 정렬
앞서 언급했듯이 기본적으로 sort() 함수는 comp 매개변수가 언급되지 않은 경우 항목 집합을 오름차순으로 정렬합니다.
따라서 아래 예에서는 배열을 오름차순으로 정렬하기 위해 첫 번째(시작) 및 마지막(종료) 반복 가능 항목만 전달했습니다.
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
//array initialisation
int demo[5] = {5, 4, 3, 2, 1};
int len = sizeof(demo)/sizeof(demo[0]);
cout<<"Before sorting array : ";
for(int i=0; i<len; i++)
{
cout<<" "<<demo[i];
}
std::sort(demo, demo + len);//Sorting demo array
cout<<"\n\nAfter sorting array : ";
for(int i=0; i<len; i++)
{
cout<<" "<<demo[i];
}
return 0;
}
산출:
여기서 demo는 첫 번째 요소의 주소이고 (demo + len)는 주어진 배열의 마지막 요소의 주소입니다. 따라서 기본적으로 comp를 std::less 함수로 간주하면 sort() 함수는 배열을 오름차순으로 정렬합니다.
참고: std::less 함수는 두 인수를 비교하고 첫 번째 인수가 다른 인수보다 작은지 여부에 따라 True 또는 False를 반환합니다.
2. 내림차순 정렬
세 번째 매개변수를 조작하여 내림차순으로 sort() 함수를 사용하여 데이터 구조를 정렬할 수도 있습니다. 방법을 살펴보겠습니다.
아래 코드에서 우리는 std::less 함수와 정반대로 작동하는 std::greater 함수를 사용했습니다. . 두 인수를 비교하고 첫 번째 인수가 다른 인수보다 크면 True를 반환합니다. 그렇지 않으면 False를 반환합니다.
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
//array initialisation
int demo[5] = {44, 22, 55, 33, 66};
int len = sizeof(demo)/sizeof(demo[0]);
cout<<"Before sorting array : ";
for(int i=0; i<len; i++)
{
cout<<" "<<demo[i];
}
std::sort(demo, demo + len, greater<int>());//Sorting demo array
cout<<"\n\nAfter sorting array : ";
for(int i=0; i<len; i++)
{
cout<<" "<<demo[i];
}
return 0;
}
아래와 같이 sort() 함수의 세 번째 매개변수로 람다 함수를 사용할 수도 있습니다.
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
//array initialisation
int demo[5] = {44, 22, 55, 33, 66};
int len = sizeof(demo)/sizeof(demo[0]);
cout<<"Before sorting array : ";
for(int i=0; i<len; i++)
{
cout<<" "<<demo[i];
}
std::sort(demo, demo + len, [](int &e1, int &e2){ return e1>e2; });//Sorting demo array
cout<<"\n\nAfter sorting array : ";
for(int i=0; i<len; i++)
{
cout<<" "<<demo[i];
}
return 0;
}
위의 두 예제는 아래와 같은 출력을 생성합니다. 그리고 demo 배열을 내림차순으로 성공적으로 정렬합니다.
산출:
3. 사용자 정의 순서로 정렬
std::sort() 함수의 세 번째 매개변수(comp)는 순서나 정렬을 정의하는 사용자 정의 함수일 수도 있습니다.
이 함수는 부울 값(True/False)을 반환해야 합니다.
예를 들어 아래 코드 조각에서 우리는 10으로 나눌 때 생성되는 나머지를 기준으로 배열의 요소를 정렬하려고 시도했습니다('%' 연산자 사용).
#include<iostream>
#include<algorithm>
using namespace std;
//our function
bool My_func( int a, int b)
{
return (a%10)<(b%10);
}
int main()
{
//array initialisation
int demo[5] = {18, 45, 34, 92, 21};
int len = sizeof(demo)/sizeof(demo[0]);
cout<<"Before sorting array : ";
for(int i=0; i<len; i++)
{
cout<<" "<<demo[i];
}
std::sort(demo, demo + len, My_func);//Sorting demo array
cout<<"\n\nAfter sorting array : ";
for(int i=0; i<len; i++)
{
cout<<" "<<demo[i];
}
return 0;
}
산출:
위 출력에서 볼 수 있듯이 demo 배열은 (element%10) 요소를 기준으로 성공적으로 정렬되었습니다. My_func() 함수의 도움으로.
C++에서 std::sort()의 복잡성
sort() 함수는 N 항목을 정렬하기 위해 Nlog(N) 비교를 수행합니다. 따라서 최악의 시나리오에서는 O(Nlog(N)) 복잡성이 있습니다.
합산
이것이 이것에 대한 것입니다. 오늘 우리는 C++ 표준 라이브러리에서 sort() 함수의 사용과 작동에 대해 이해했습니다. 명확한 이해가 있기를 바랍니다.
sort() 함수는 벡터 등과 같이 배열 이외의 데이터 구조에도 사용할 수 있습니다. 이 자습서에서는 더 나은 이해를 위해 배열을 고려했습니다.
C++ 자습서를 진행하는 것이 좋습니다.
추가 질문이 있으시면 아래 의견을 자유롭게 사용하십시오.
참조
- std::sort() - C++ 문서,
- C++의 표준 템플릿 라이브러리(STL),
- <알고리즘> – C++ 알고리즘 라이브러리.