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

C++ 표준 라이브러리의 <algorithm>에 있는 sort() 함수를 사용해 배열이나 벡터를 제자리에서 정렬하세요. 기본적으로 이 함수는 first부터 last 직전까지의 반개 범위를 오름차순으로 정렬합니다. 다른 순서를 선택하려면 비교자를 전달하세요.

sort() 함수를 사용해 C++에서 배열 또는 벡터 정렬하기

std::sort는 임의 접근 반복자를 허용하므로 배열과 벡터에서 동작합니다. std::set이나 std::map는 임의 접근 반복자를 제공하지 않으므로 제자리에서 재배열할 수 없습니다. 이 완전한 프로그램은 배열과 벡터를 모두 정렬합니다.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main() {
    int values[] = {8, 3, 6, 1, 5};
    std::vector<int> scores{14, 7, 22, 9};

    std::sort(std::begin(values), std::end(values));
    std::sort(scores.begin(), scores.end());

    for (int value : values) std::cout << value << ' ';
    std::cout << '\n';
    for (int score : scores) std::cout << score << ' ';
    std::cout << '\n';
    return 0;
}

std::begin과 std::end는 배열의 범위를 제공하고, 벡터는 그 begin() 및 end() 반복자를 사용합니다. 이 프로그램은 실행되지 않은 예제로 제공되며, 그 출력은 구성된 런타임에서 관찰될 때까지 생략됩니다. 두 호출 모두 원래 요소를 수정하므로, 이후 코드는 새 순서로 요소들을 보게 됩니다. 컨테이너의 일부만 정렬하려면 그 부분을 구분하는 반복자를 전달하세요.

C++에서 배열 또는 벡터를 내림차순으로 정렬하기

가장 큰 값부터 가장 작은 값 순으로 정렬하려면 세 번째 인수로 std::greater<>를 전달하세요. 비교자를 위해 <functional>을 포함하세요. 예를 들어 std::sort(values.begin(), values.end(), std::greater<>{});는 벡터를 내림차순으로 정렬합니다. 비교자는 어떤 범위를 정렬할지는 바꾸지 않고 순서 규칙을 변경합니다.

partial_sort()를 사용해 배열 또는 벡터의 일부 정렬하기

접두사만 정렬되면 될 때는 partial_sort(first, middle, last)를 사용하세요. 이는 가장 작은 middle - first개의 요소를 정렬된 순서로 middle 앞에 배치합니다. middle부터 last까지의 요소는 특정 순서가 보장되지 않습니다. 예를 들어 std::partial_sort(values.begin(), values.begin() + 3, values.end());는 처음 세 위치에 대해 가장 작은 세 값을 선택합니다.

C++에서 sort()와 함께 사용자 정의 비교자 사용하기

비교자를 사용하면 문자열 길이와 같은 키를 기준으로 값을 정렬할 수 있습니다. 예를 들어 std::sort(words.begin(), words.end(), [](const std::string& a, const std::string& b) { return a.size() < b.size(); });는 더 짧은 문자열을 먼저 배치합니다. 비교자는 엄격한 약한 순서를 정의해야 합니다. 일관성이 있어야 하며 항목이 자기 자신보다 앞에 온다고 간주해서는 안 됩니다. 길이가 같은 문자열은 이 비교에서 동등하므로, 그 상대적 순서는 명시되지 않습니다. 이 예제를 사용할 때는 <algorithm>과 함께 <string>을 포함하세요.

is_sorted()로 범위가 정렬되었는지 확인하기

std::is_sorted(first, last)는 first부터 last 직전까지의 범위가 기본 비교에 따라 정렬되어 있을 때 true를 반환하고, 그렇지 않으면 false를 반환합니다. 요소들을 재배열하지 않고 범위를 확인합니다. 사용자 정의 순서를 확인할 때는 그 순서에 사용한 것과 같은 비교자를 제공하세요. 예: std::is_sorted(words.begin(), words.end(), compare).

정렬 알고리즘의 시간 복잡도

std::sort의 경우, 표준은 최악의 경우 O(N log N)번의 비교를 명시합니다. 여기서 N은 범위 내 요소의 개수입니다. 이는 작업량이 범위의 길이에 따라 어떻게 증가하는지를 설명하며, 특정 정렬 구현을 약속하지는 않습니다. std::partial_sort는 N개 중 K개의 요소를 선택하고 정렬할 때 약 N log K번의 비교를 사용하고, std::is_sorted는 최대 N - 1번의 비교를 수행합니다. 이러한 한계는 범위를 완전히 정렬하는 것과 접두사만 정렬하는 것, 또는 기존 순서를 확인하는 것을 구별하는 데 도움이 됩니다.