Check for a sorted array in C++
This post will discuss how to check for a sorted array in C++.
1. Using std::is_sorted
The standard solution to check if an array is sorted is using the standard library algorithm std::is_sorted that takes a range and comparison function. With C++11, you can pass an iterator to the beginning and end of the array. It can be used as follows to check for a sorted array in ascending order using the default comparison operator.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
#include <iostream> #include <algorithm> int main() { int arr[] = { -3, -2, 4, 5, 7 }; std::cout << "Is sorted: " << std::boolalpha << std::is_sorted(std::begin(arr), std::end(arr)); return 0; } |
Alternatively, you can specify the range to check using pointer notation:
|
1 2 3 4 5 6 7 8 9 10 11 |
#include <iostream> #include <algorithm> int main() { int arr[] = { -1, -2, 4, 5, 1 }; std::cout << "Is sorted: " << std::boolalpha << std::is_sorted(arr + 1, arr + 3); return 0; } |
To check for a sorted array in descending order, you can pass the comparison function std::greater<int>() that represents an object class for greater-than inequality comparison.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
#include <iostream> #include <algorithm> int main() { int arr[] = { 7, 5, 4, -2, -3 }; std::cout << "Is sorted: " << std::boolalpha << std::is_sorted(std::begin(arr), std::end(arr), std::greater<int>()); return 0; } |
The default comparison function works fine for an array of std::string. However, if you have an array of C-style strings, you have to provide a comparison function.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include <iostream> #include <algorithm> #include <cstring> int main() { const char* arr[] = { "a", "b", "c", "d" }; bool isSorted = std::is_sorted(std::begin(arr), std::end(arr), [](const char* lhs, const char* rhs) { return std::strcmp(lhs, rhs) < 0; }); std::cout << "Is sorted: " << std::boolalpha << isSorted; // true return 0; } |
2. Using std::adjacent_find function
Another option is to use the std::adjacent_find function to check for a sorted array in C++. It returns the first occurrence of adjacent elements that satisfies a binary predicate, or end of the range if no such pair is found.
To check for a sorted array in ascending order, you can pass the comparison function std::greater<int>(). If no pair is found that satisfies the comparison function, the array must be sorted.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <iostream> #include <algorithm> int main() { int arr[] = { -3, -2, 4, 5, 7 }; bool isSorted = std::adjacent_find(std::begin(arr), std::end(arr), std::greater<int>()) == std::end(arr); std::cout << "Is sorted: " << std::boolalpha << isSorted; // true return 0; } |
Similarly, to check for a sorted array in descending order, pass the comparison function std::less<int>() that represents an object class for less-than inequality comparison.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <iostream> #include <algorithm> int main() { int arr[] = { 7, 5, 4, -2, -3 }; bool isSorted = std::adjacent_find(std::begin(arr), std::end(arr), std::less<int>()) == std::end(arr); std::cout << "Is sorted: " << std::boolalpha << isSorted; // true return 0; } |
3. Naive Solution
Finally, you can write your custom logic for this trivial task. Here’s what the code would look like to check for a sorted array in ascending order:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <iostream> bool isSorted(int arr[], int n) { for (int i = 0; i < n - 1; i++) { if (arr[i] > arr[i + 1]) { return false; } } return true; } int main() { int arr[] = { -3, -2, 4, 5, 7 }; int n = sizeof(arr) / sizeof(*arr); std::cout << "Is sorted: " << std::boolalpha << isSorted(arr, n); // true return 0; } |
That’s all about checking for a sorted array in C++.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)