[C++/STL] std::is_sorted() : 요소들이 정렬되어 있는지 확인하는 방법 (+ 직접 비교, 내림차순)

 

 

🗨 개인적인 공부 기록용으로 정리한 내용입니다. 잘못된 내용에 대한 피드백은 언제나 감사합니다 :)

 

 

 

STL은 알면 알수록 쓸 데가 많다!

 

 

 

⭐ 요약

`std::is_sorted()`는 C++ 표준 라이브러리 <algorithm> 헤더에 포함된 함수로, 특정 범위의 요소들이 정렬되어 있는지 확인하여 `true/false`를 반환한다.

 

 

 

📌 is_sorted() 함수

`is_sorted` 함수는 C++ 표준 라이브러리(STL)의 알고리즘 라이브러리에 포함된 함수로, 특정 범위의 요소들이 정렬되어 있는지 확인하는 데 사용된다.

이 함수는 요소들이 오름차순뿐만 아니라 사용자 정의 비교 함수로 다양한 정렬 기준을 적용할 수 있어 다양하게 활용 가능하다.

 

/* 1. 기본 (오름차순 확인) */
template<class ForwardIt>
bool is_sorted(ForwardIt first, ForwardIt last);

/* 2. 사용자 정의 비교 함수 사용 */
template<class ForwardIt, class Compare>
bool is_sorted(ForwardIt first, ForwardIt last, Compare comp);

 

 

 

🔖 헤더 (Header)

• `#include <algorithm>`

is_sorted는 알고리즘 라이브러리에 정의된 함수이다.

 

 

 

🔖 매개변수 (Parameters)

1. `first`
   • 범위의 시작 반복자
   • 정렬 여부를 확인할 첫 번째 요소를 가리킨다.
2. `last`
   • 범위의 끝 반복자
   • 확인할 마지막 요소 다음을 가리키므로, `[first, last)` 범위를 의미한다.
3. `comp`
   • 사용자 정의 비교 함수 (검사할 정렬 순서를 변경하는 데 사용됨)
   • 함수 객체 또는 람다 식을 전달하여 두 요소의 비교 방식을 정의할 수 있다.
   • 기본적으로 오름차순으로 정렬되었는지 확인하는 `<` 연산자를 사용한다.
   • 예: `std::greater<int>()`를 전달하면 내림차순 여부를 확인한다.

 

 

 

🔖 반환값 (Return Value)

• `true` : 지정한 범위 `[first, last)`의 요소들이 정렬되어 있을 경우.
• `false` : 정렬되어 있지 않을 경우.

 

 

 

🔖 동작 방식 및 시간 복잡도

`is_sorted()`는 범위 내에서 두 인접한 요소를 비교하며, 정렬이 되지 않은 요소 쌍이 발견될 때까지 진행한다.

 

⏱ 시간복잡도: $\mathbf{O(n)}$

 

 

 

📌 is_sorted() 사용

🔖 기본 (오른차순 정렬 확인)

#include <algorithm>    // std::is_sorted
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> vec0 = {1, 2, 3, 4, 4, 5, 6};
    vector<int> vec1 = {4, 5, 1, 3, 7, 2};

    cout << "vec0 정렬 상태 : ";
    if (is_sorted(vec0.begin(), vec0.end())) {
        cout << "오름차순 정렬" << endl;
    } else {
        cout << "정렬되지 않음" << endl;
    }

    cout << "vec1 정렬 상태 : ";
    if (is_sorted(vec1.begin(), vec1.end())) {
        cout << "오름차순 정렬" << endl;
    } else {
        cout << "정렬되지 않음" << endl;
    }

    return 0;
}

 

💻 출력

vec0 정렬 상태 : 오름차순 정렬
vec1 정렬 상태 : 정렬되지 않음

 

 

 

🔖 내림차순 정렬 확인

#include <algorithm>    // std::is_sorted
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> vec0 = {1, 2, 3, 4, 4, 5, 6};
    vector<int> vec1 = {8, 7, 4, 4, 3, 1};

    cout << "vec0 정렬 상태 : ";
    if (is_sorted(vec0.begin(), vec0.end(), greater<int>())) {	// 3번째 인자 추가
        cout << "내림차순 정렬" << endl;
    } else {
        cout << "정렬되지 않음" << endl;
    }

    cout << "vec1 정렬 상태 : ";
    if (is_sorted(vec1.begin(), vec1.end() , greater<int>())) {
        cout << "내림차순 정렬" << endl;
    } else {
        cout << "정렬되지 않음" << endl;
    }

    return 0;
}

 

💻 출력 

vec0 정렬 상태 : 정렬되지 않음
vec1 정렬 상태 : 내림차순 정렬

 

 

 

🔖 사용자 정의 비교 함수 (람다 사용)

아래는 문자열 길이를 기준으로 오름차순 정렬 여부를 확인하는 사용자 지정 함수로 비교하는 코드이다.

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

int main() {
    vector<string> words = {"a", "abc", "abcde"};

    /* 문자열 길이를 기준으로 정렬 여부를 확인하는 람다 함수 */
    auto length_cmp = [](const string& a, const string& b) {
        return a.size() <= b.size();  // 앞 문자열 길이가 뒤 문자열 길이보다 작거나 같은지 비교
    };

    cout << "words 정렬 상태 : ";
    if (is_sorted(words.begin(), words.end(), length_cmp)) {
        cout << "문자열 길이를 기준으로 정렬" << endl;
    } else {
        cout << "문자열 길이를 기준으로 정렬되지 않음" << endl;
    }

    return 0;
}

 

💻 출력

words 정렬 상태 : 문자열 길이를 기준으로 정렬

 

 

 

 

 

📌 is_sorted() 함수 없이 직접 비교하는 방법

std::is_sorted를 사용하지 않고, 각 요소를 직접 비교하여 정렬 여부를 확인하는 방법이다.

모든 인접한 요소 쌍이 올바른 순서로 있는지 확인하는 방식이다.

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

bool isSorted(const vector<int>& vec) {
    for (int i = 1; i < vec.size(); i++) {
        if (vec[i - 1] > vec[i]) {
            return false;  // 정렬되지 않음
        }
    }
    return true;  // 정렬됨
}

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

    cout << "vec 정렬 상태 : ";
    if (isSorted(vec)) {
        cout << "오름차순 정렬" << endl;
    } else {
        cout << "정렬되지 않음" << endl;
    }

    return 0;
}

 

💻 출력

vec 정렬 상태 : 오름차순 정렬

 

 

 

---

 

참고

 

is_sorted() in C++ STL - GeeksforGeeks

is_sorted() in C++ STL - GeeksforGeeks

 

std::is_sorted - cppreference.com

std::is_sorted - cppreference.com

 

cplusplus.com std::is_sorted

https://cplusplus.com/reference/algorithm/is_sorted/?kw=is_sorted

 

C++ STL algorithm 함수 is_sorted

<algorithm> 함수