C++에서 리스트 정렬하기: std::list::sort() 완벽 가이드

이 글에서는 C++ 표준 라이브러리를 활용해 배열이나 연결 리스트(linked list)를 정렬하는 방법을 살펴봅니다. C++는 다양한 용도에 맞게 사용할 수 있는 여러 표준 라이브러리를 제공하며, 그중 하나가 바로 정렬 기능입니다.

std::list::sort() 함수란?

C++의 std::list::sort() 함수는 리스트(list) 컨테이너의 요소들을 오름차순으로 정렬합니다. 이 함수의 주요 특징은 다음과 같습니다.

• 요소들을 오름차순으로 정렬합니다.
• 안정 정렬(stable sort) 방식이므로 값이 같은 요소들의 원래 순서가 유지됩니다.
• 기본적으로 operator<(작음 연산자)를 사용해 요소를 비교합니다.
• 내부적으로 병합 정렬 계열의 알고리즘을 사용하므로 시간 복잡도는 O(n log n)입니다.

기본 사용 예제

아래 예제는 정수형 리스트를 생성한 뒤, 정렬 전과 후의 내용을 출력하는 간단한 프로그램입니다.

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

int main(void) {
    list<int> l = {1, 4, 2, 5, 3};

    cout << "정렬 전 리스트의 내용" << endl;
    for (auto it = l.begin(); it != l.end(); ++it)
        cout << *it << endl;

    l.sort();

    cout << "정렬 후 리스트의 내용" << endl;
    for (auto it = l.begin(); it != l.end(); ++it)
        cout << *it << endl;

    return 0;
}

실행 결과

정렬 전 리스트의 내용
1
4
2
5
3
정렬 후 리스트의 내용
1
2
3
4
5

위 출력에서 확인할 수 있듯이, l.sort() 호출 한 줄만으로 리스트가 1부터 5까지 오름차순으로 깔끔하게 정렬된 것을 볼 수 있습니다.

내림차순 정렬: 비교 함수 활용하기

std::list::sort()는 비교 기준을 직접 지정할 수도 있습니다. 예를 들어 greater<int>()를 인자로 전달하면 내림차순으로 정렬할 수 있습니다.

#include <iostream>
#include <list>
#include <functional>
using namespace std;

int main(void) {
    list<int> l = {1, 4, 2, 5, 3};

    // 내림차순 정렬
    l.sort(greater<int>());

    for (int x : l)
        cout << x << endl;

    return 0;
}

5
4
3
2
1

마무리

C++ 표준 라이브러리의 std::list::sort()를 사용하면 별도의 정렬 알고리즘을 구현하지 않고도 안정적이고 효율적인 정렬을 손쉽게 적용할 수 있습니다. 기본 오름차순 정렬뿐 아니라 사용자 정의 비교 함수를 통해 다양한 정렬 기준을 유연하게 지원하므로, 실무에서도 매우 유용하게 활용할 수 있습니다.