std::is_sort()

#include <algorithm>

// default (1)
template <class ForwardIterator>  bool is_sorted (ForwardIterator first, ForwardIterator last);

// custom (2)	
template <class ForwardIterator, class Compare>  bool is_sorted (ForwardIterator first, ForwardIterator last, Compare comp);

범위 내의 요소들이 정렬되어 있는지 확인하는 함수이다.
기본적으로 오름차순(asceding)으로 정렬되어 있는지 확인하며, comp를 통해 정렬 기준을 정하여 정렬되어 있는지 확인할 수 있다.

시간 복잡도는 $O(N)$이다. 여기에서 $N$은 범위의 첫 번째와 마지막 사이의 거리이다.
std::is_sorted()는 범위 내에서 정렬이 맞지 않는 것이 발견될 때까지 요소의 쌍을 비교한다.

Parameters

Parameters	Description
first	정렬을 확인할 범위의 첫번째 forward iterator 범위에 포함된다.
last	정렬을 확인할 범위의 마지막 forward iterator 범위에 포함되지 않는다.
comp	인자 두 개를 받는 비교 함수로bool 값을 반환한다. 인수를 수정하지 않으며, 함수 포인터 또는 함수 객체일 수 있다.

comp 함수의 원형을 아래와 같은 형태를 취해야 한다.

bool cmp(const Type &a, const Type &b);

Return value

• 주어진 범위내 정렬되어 있을 경우 true
  • 주어진 범위 내 요소가 1개일 경우 항상 true를 반환한다.
• 주어진 범위내 정렬되어 있지 않은 경우 false

---

Example

Do not use comp

#include <iostream>
#include <algorithm>
 
int main()
{
    int A[] = { 10, 11, 15, 12 };
 
    // Index 0 to 2
    int range1 = 3;
 
    // Index 0 to 3
    int range2 = 4;
 
    if (std::is_sorted(A, A + range1)) {
        std::cout << "Sorted in the range : " << range1 << std::endl;
    } else {
        std::cout << "Not Sorted in the range : " << range1 << std::endl;
    }
 
    if (std::is_sorted(A, A + range2)) {
        std::cout << "Sorted in the range : " << range2 << std::endl;
    } else {
        std::cout << "Not Sorted in the range : " << range2 << std::endl;
    }
    
    return 0;
}

Output

Sorted in the range : 3
Not Sorted in the range : 4

use comp

#include <iostream>
#include <algorithm>
 
using namespace std;
 
bool ignore_case(char a, char b)
{
    // Converts both characters to lowercase and checks if a <= b
    return (tolower(a) <= tolower(b));
}
 
// Function that checks if string is sorted while ignoring the case
bool check_if_sorted(string str)
{
    // Function call to is_sorted with binary predicate ignore_case
    return is_sorted(str.begin(), str.end(), ignore_case);
}
 
int main()
{
    // String which is to be checked
    string str = "tOY";
 
    // Function returned true, string is sorted
    if (check_if_sorted(str)) {
        cout << "Sorted";
    }
    // Function returned false, string not sorted
    else {
        cout << "Not sorted";
    }
 
    return 0;
}

Output

Not sorted

---

참고 자료

• https://cplusplus.com/reference/algorithm/is_sorted/?kw=is_sorted
• https://www.geeksforgeeks.org/stdis_sorted-in-cpp/