실행 가능한 C++ 문서: 정렬

Q: C++에서 벡터를 어떻게 정렬하나요?

을 포함하고 sort(v.begin(), v.end())를 호출하세요. 이는 operator<를 사용해 요소를 제자리에서 오름차순으로 정렬합니다. 배열을 정렬하려면 arr와 arr + n(또는 begin(arr) / end(arr))을 전달하세요.

Q: C++에서 내림차순으로 정렬하려면 어떻게 하나요?

a > b를 반환하는 비교자를 전달하세요: sort(v.begin(), v.end(), [](int a, int b){ return a > b; });. 에 있는 내장 sort(v.begin(), v.end(), greater ());를 사용할 수도 있습니다.

Q: 왜 내 비교자가 C++에서 std::sort를 크래시시키나요?

비교자는 반드시 엄격 약순서(strict weak ordering)여야 합니다. 즉, 두 인자가 같을 때 false를 반환해야 합니다. =를 사용하면(같은 요소에 대해 true를 반환하므로) 그 규칙을 위반하게 되며 이는 미정의 동작입니다. std::sort가 범위 밖을 읽어 크래시할 수 있습니다. 항상 로 비교하세요.

정렬도 그저 하나의 알고리즘일 뿐

이전 페이지에서 표준 라이브러리가 이터레이터를 통해 어떤 범위에서도 동작하는 기성 알고리즘들을 제공한다는 것을 보았습니다. 정렬은 그중에서도 가장 자주 쓰게 될 알고리즘이며, 별도의 페이지를 두는 이유는 몇 가지 날카로운 함정이 있기 때문입니다. 사용자 정의 순서, 안정성, 그리고 어기면 틀린 답이 아니라 미정의 동작을 안겨주는 규칙입니다.

핵심 일꾼은 <algorithm>의 std::sort입니다. 범위의 시작과 끝을 주면 요소들을 제자리에서 오름차순으로 재배치합니다:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    sort(nums.begin(), nums.end());   // 오름차순, 제자리에서

    for (int n : nums) cout << n << " ";  // 1 2 3 5 8 9
    cout << "\n";
    return 0;
}

복사본은 만들어지지 않습니다. 벡터 자체가 재정렬됩니다. 내부적으로 std::sort는 보통 인트로소트(힙소트로 전환되는 퀵소트)이며, 평균적으로 O(n log n)을 제공합니다. 이는 직접 정렬을 작성하는 것보다 거의 항상 더 빠르고 오류가 훨씬 적습니다.

평범한 C 배열에서도 동작합니다. 범위를 포인터로 기술하기만 하면 됩니다:

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int arr[] = {40, 10, 30, 20};
    int n = 4;

    sort(arr, arr + n);               // 또는 sort(begin(arr), end(arr));

    for (int x : arr) cout << x << " ";  // 10 20 30 40
    return 0;
}

비교자로 사용자 정의 순서 만들기

기본적으로 std::sort는 operator<로 요소를 정렬합니다. 다르게 정렬하려면 세 번째 인자를 전달하세요. 두 요소를 받아 첫 번째가 두 번째보다 앞에 와야 하면 true를 반환하는 비교자입니다.

람다가 자연스럽게 어울립니다. 내림차순은 그냥 a > b입니다:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    sort(nums.begin(), nums.end(), [](int a, int b) {
        return a > b;   // a가 더 클 때 "a가 b보다 앞" -> 내림차순
    });

    for (int n : nums) cout << n << " ";  // 9 8 5 3 2 1
    cout << "\n";
    return 0;
}

내장 타입에 대한 단순한 내림차순이라는 흔한 경우를 위해, 라이브러리는 <functional>에 기성 비교자 greater<T>()까지 제공합니다:

#include <functional>
sort(nums.begin(), nums.end(), greater<int>());  // a > b와 동일

비교자는 값 그 자체가 아닌 다른 기준으로 정렬하는 방법이기도 합니다. 예를 들어 문자열을 알파벳순이 아니라 길이순으로 정렬하는 경우입니다:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    vector<string> words = {"pear", "fig", "banana", "kiwi"};

    sort(words.begin(), words.end(), [](const string& a, const string& b) {
        return a.size() < b.size();   // 더 짧은 단어를 먼저
    });

    for (const string& w : words) cout << w << " ";  // fig kiwi pear banana
    cout << "\n";
    return 0;
}

몇 바이트보다 큰 것(예: string)은 비교자 매개변수를 const&로 받으세요. 비교할 때마다 모든 요소를 복사하는 것은 순전한 낭비입니다.

구조체를 필드 기준으로 정렬하기

실제 프로그램에서는 보통 구조체 컬렉션을 그 필드 중 하나로 정렬합니다. 비교자는 관심 있는 필드에 접근하기만 하면 됩니다. 여기서는 사람들을 나이순으로, 가장 어린 사람부터 정렬합니다:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct Person {
    string name;
    int age;
};

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return a.age < b.age;
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";
    return 0;
}

Linus와 Dennis가 둘 다 25세인 것에 주목하세요. 여기서는 원래의 상대 순서대로 나왔지만, std::sort는 그것을 보장하지 않습니다. 같은 요소의 상대 순서가 중요하다면, 그 순서를 유지하는 std::stable_sort를 사용하세요(약간의 성능 비용이 있습니다):

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct Person { string name; int age; };

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    stable_sort(people.begin(), people.end(),
        [](const Person& a, const Person& b) { return a.age < b.age; });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";
    // Linus가 Dennis보다 앞에 유지됨 - 입력 순서가 보존된다
    return 0;
}

동점을 의도적으로 처리하려면(예: 나이로 정렬한 다음 이름의 알파벳순으로), 기본 키가 같을 때만 보조 키를 비교하세요. std::tie를 쓰면 깔끔합니다:

#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <algorithm>
using namespace std;

struct Person { string name; int age; };

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return tie(a.age, a.name) < tie(b.age, b.name);  // 나이, 그다음 이름
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";  // Dennis와 Linus는 25, 알파벳순
    return 0;
}

엄격 약순서의 함정

이것은 C++ 정렬에서 가장 위험한 실수입니다. 틀린 답을 주는 것이 아니라 미정의 동작을 주기 때문이며, 이는 흔히 크래시나 범위 밖 읽기를 의미합니다.

std::sort는 비교자가 엄격 약순서를 정의할 것을 요구합니다. 실용적인 규칙: 임의의 요소 x에 대해 comp(x, x)는 반드시 false여야 합니다. 다시 말해, 요소는 결코 자기 자신보다 "앞"에 있지 않습니다. 그것이 바로 <와 >가 주는 것이고, 정확히 <=와 >=가 깨뜨리는 것입니다:

// 버그: a == b일 때 true를 반환하여 엄격 약순서를 위반함.
sort(v.begin(), v.end(), [](int a, int b) {
    return a <= b;   // 미정의 동작 - 일부 입력에서 크래시할 수 있음
});

<=를 쓰면 비교자는 5가 다른 5보다 앞에 온다고 주장하는 셈인데, 이는 모순입니다. 그러면 std::sort는 포인터를 범위의 끝 너머로 진행시킬 수 있습니다. 작은 입력에서는 때때로 동작하는 것처럼 보이는데, 그것이 이 버그를 무섭게 만듭니다. 테스트는 통과하고 프로덕션에서 크래시할 수 있으니까요. 해결책은 그냥 <입니다:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};

    sort(v.begin(), v.end(), [](int a, int b) {
        return a < b;   // 올바름: 같을 때 false
    });

    for (int x : v) cout << x << " ";
    cout << "\n";
    return 0;
}

두 번째 고전적인 함정: 정렬은 그 범위 안을 가리키는 모든 것을 무효화합니다. 정렬 전에 저장해 둔 이터레이터, 포인터, 인덱스는 요소들이 이동했기 때문에 정렬 후에는 더 이상 같은 논리적 요소를 가리키지 않습니다. 필요한 위치는 정렬 후에 다시 구하세요, 절대 그 전에 하지 마세요.

범위의 일부만 정렬하기

때로는 전부를 정렬할 필요가 없고, 상위 몇 개만 필요할 때가 있습니다. 앞의 세 개를 읽으려고 벡터 전체를 정렬하는 것은 낭비입니다. std::partial_sort는 요청한 요소만 배열하고 나머지는 미지정 순서로 남겨두므로 더 저렴합니다:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};

    // 가장 작은 3개를 순서대로 앞쪽에 배치. 나머지는 미지정.
    partial_sort(v.begin(), v.begin() + 3, v.end());

    for (int i = 0; i < 3; i++) cout << v[i] << " ";  // 1 2 3
    cout << "\n";
    return 0;
}

그리고 특정 위치에 놓이게 될 단 하나의 요소만 필요하다면(예: 중앙값), std::nth_element는 일을 더 적게 합니다. 올바른 요소를 그 인덱스에 배치하고, 더 작은 것은 모두 앞에, 더 큰 것은 모두 뒤에 두는데, 모두 평균 O(n)입니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};
    size_t mid = v.size() / 2;

    nth_element(v.begin(), v.begin() + mid, v.end());

    cout << "median is " << v[mid] << "\n";  // 5
    return 0;
}

"완전 정렬"이 문제가 실제로 필요로 하는 것보다 과할 때 이것들을 사용하세요. 큰 데이터에서 실질적인 시간을 절약해 줍니다.

다음: 템플릿

같은 std::sort가 int, string, 그리고 여러분 자신의 Person 구조체를 처리했고, greater<int>()가 그만큼 손쉽게 greater<string>()이 될 수 있었다는 것을 알아차렸나요? 그 일반성은 마법이 아닙니다. 그것은 템플릿, 즉 호출자가 끼워 넣는 어떤 타입에 대해서도 하나의 코드가 동작하도록 해주는 메커니즘입니다. 다음 페이지에서는 여러분 자신의 템플릿 함수와 클래스를 작성하는 방법을 살펴봅니다. 그러면 여러분의 코드도 지금까지 사용해 온 알고리즘들만큼 타입에 구애받지 않게 만들 수 있습니다.

자주 묻는 질문

C++에서 벡터를 어떻게 정렬하나요?

<algorithm>을 포함하고 sort(v.begin(), v.end())를 호출하세요. 이는 operator<를 사용해 요소를 제자리에서 오름차순으로 정렬합니다. 배열을 정렬하려면 arr와 arr + n(또는 begin(arr) / end(arr))을 전달하세요.

C++에서 내림차순으로 정렬하려면 어떻게 하나요?

a > b를 반환하는 비교자를 전달하세요: sort(v.begin(), v.end(), [](int a, int b){ return a > b; });. <functional>에 있는 내장 sort(v.begin(), v.end(), greater<int>());를 사용할 수도 있습니다.

왜 내 비교자가 C++에서 std::sort를 크래시시키나요?

비교자는 반드시 **엄격 약순서(strict weak ordering)**여야 합니다. 즉, 두 인자가 같을 때 false를 반환해야 합니다. <=나 >=를 사용하면(같은 요소에 대해 true를 반환하므로) 그 규칙을 위반하게 되며 이는 미정의 동작입니다. std::sort가 범위 밖을 읽어 크래시할 수 있습니다. 항상 < 또는 >로 비교하세요.