C++ 표준 템플릿 라이브러리(STL)에서 정렬

Suraj P 2023년10월12일 C++ C++ Sorting
  1. sort() 함수를 사용하여 C++에서 배열 또는 STL 컨테이너 정렬
  2. C++에서 내림차순으로 배열 정렬
  3. partial_sort() 함수를 사용하여 배열 또는 벡터의 일부 정렬
  4. C++에서 sort() 함수를 사용한 사용자 정의 또는 사용자 정의 정렬
  5. C++에서 is_sorted() 메서드 사용
  6. 정렬 알고리즘의 시간 복잡성
C++ 표준 템플릿 라이브러리(STL)에서 정렬

이 튜토리얼에서는 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() 함수가 적용되는 요소의 수입니다.

튜토리얼이 마음에 드시나요? DelftStack을 구독하세요 YouTube에서 저희가 더 많은 고품질 비디오 가이드를 제작할 수 있도록 지원해주세요. 구독하다
작가: Suraj P
Suraj P avatar Suraj P avatar

A technophile and a Big Data developer by passion. Loves developing advance C++ and Java applications in free time works as SME at Chegg where I help students with there doubts and assignments in the field of Computer Science.

LinkedIn GitHub

관련 문장 - C++ Sorting