# Thread: Check if array is sorted

1. ## Check if array is sorted

I need to write a function which checks if the elements in an array are in a monotonous order, I wrote the following program which works for some values but it doesn't work for others. For the current array the output is: "The elements are not sorted", and it should be "The array is decreasing". Any ideas? Also, I'm not sure if I used the correct way of updating the loop (++i), would i++ be better?
Code:
```/* Implement the function int isSorted(unsigned t[], unsigned n)
which checks if the array has the elements in a monotonous order (either increasing or decreasing)returning a logical result; */

#include <stdio.h>
#include <stdlib.h>
void isSorted(unsigned t[], unsigned n){
unsigned counterIncr = 0;
unsigned counterDecr = 0;
for(int i = 0; i < n; ++i){
if(t[i] <= t[i+1])
counterIncr++;
else
if(t[i] > t[i+1])
counterDecr++;

}
if(counterIncr == (n-1))
printf("The array is increasing");
else
if(counterDecr == (n-1))
printf("The array is decreasing");
else
printf("The elements are not sorted");
}

int main()
{
unsigned t[4] = {1, 2, 3, 4};
isSorted(t, 4);
return 0;
}```

2. Easier if you check only if the next value is greater than the previous (or vice-versa).

3. Also what is the purpose of checking if the array is sorted?

If it is not sorted will you need to sort the array?

If the array is not sorted in the correct way, will you need to sort the array?

With small arrays it may be faster to just sort the array and be done with it.

4. Safe to assume it is the build-up to writing a sort function.

Write the test first....

5. This is the wrong thing to check "counterIncr == (n-1)"
What would the value be for an input of 1,2,2,3,4 ?
What would the value be for an input of 1,1,1 ?
What would the value be for an input of 1,1,0 ?

Tim S.

6. I suggest testing counterIncr > 0 and counterDecr == 0

Tim S.

7. If rmmstn is still reading the thread, you have a problem here:

Code:
`for(inti = 0; i < n; ++i){`
For n items, you need to make n-1 comparisons.

8. I suggest posting the input that it fails to work on!

Tim S.

9. Originally Posted by hamster_nz
If rmmstn is still reading the thread, you have a problem here:

Code:
`for(inti = 0; i < n; ++i){`
For n items, you need to make n-1 comparisons.
Good catch fixing that seems to fix it for me.

But, I do not like the logic; it just seems flawed what should the result of a array with a single element be?

Here is what I used to test my own version of the OP program.
Code:
```int main()
{
unsigned empty[] = {};
//    unsigned t[] = {1, 2, 3, 4};    // The array is increasing
//    unsigned t[] = {2, 2, 3, 4};    // The array is increasing
//    unsigned t[] = {4, 3, 2, 1, 4}; // The elements are not sorted
//    unsigned t[] = {4, 3, 2, 1, 1}; // The array is decreasing
//    unsigned t[] = {1};             // The array has only one item in it
unsigned t[] = {2, 2};          // The array has only the same value

isSorted(t, sizeof(t)/sizeof(t[0]));

isSorted(empty, 0); // The array is empty
return 0;
}```
Tim S.

10. Your function need to return a value. Maybe something like this:

Code:
```#include <stdio.h>

int order(unsigned array[], size_t length) {
int result = 0;
for (size_t index = 1; index < length; ++index) {
unsigned left = array[index - 1], right = array[index];
int check = (left < right) ? 1 : (left > right) ? -1 : 0;
if (check != result && index > 1)
return 0;
result = check;
}
return result;
}

void dump(const char* tag, unsigned array[], size_t length) {
printf("%s:", tag);
for (size_t index = 0; index < length; ++index) {
printf(" %u", array[index]);
}
int direction = order(array, length);
if (direction < 0)
puts(" decreasing");
else if (direction > 0)
puts(" increasing");
else
puts(" not ordered");
}

#define LEN(array) sizeof(array) / sizeof(array[0])

int main(void) {
unsigned a[] = {1, 2, 3, 4}, b[] = {5, 8, 3}, c[] = {3, 9}, d[] = {11};
dump("a", a, LEN(a));
dump("b", b, LEN(b));
dump("c", c, LEN(c));
dump("d", d, LEN(d));
}```

11. I would approach it this way.

Code:
```  // Returns 0 if all the same or empty.
//         1 if increasing
//         2 if decreasing
//         3 if unsorted
int order(unsigned array[], size_t length) {
int result = 0;
for (size_t index = 1; index < length && result != 3; ++index) {
if(array[index - 1] < array[index])
result |= 1;
if(array[index - 1] > array[index])
result |= 2;
}
return result;
}```

12. Well my logic was that, if neither counter is (n-1) in the end, that would mean that the array is not increasing/decreasing, but I think I didn't understand the task right. I believe 1, 2, 2, 3, 4 is still a sorted array since the elements are in increasing order (right?). 1, 1 ,1 is unsorted (because they're all equal?) and 1, 1, 0 is sorted because the elements are decreasing. Is this logic right? Does it matter if the elements are repeated?

13. Originally Posted by hamster_nz
I would approach it this way.

Code:
```  // Returns 0 if all the same or empty.
//         1 if increasing
//         2 if decreasing
//         3 if unsorted
int order(unsigned array[], size_t length) {
int result = 0;
for (size_t index = 1; index < length && result != 3; ++index) {
if(array[index - 1] < array[index])
result |= 1;
if(array[index - 1] > array[index])
result |= 2;
}
return result;
}```
Damn, I really overcomplicated things in my approach. Thank you very much! I have a question though, is it necessary to use size_t data type (I've never used this data type before, I've also tried using int and it worked fine with your code), is size_t similar to the sizeof operator used for bitwise operators?

14. Originally Posted by Sir Galahad
Your function need to return a value. Maybe something like this:

Code:
```#include <stdio.h>

int order(unsigned array[], size_t length) {
int result = 0;
for (size_t index = 1; index < length; ++index) {
unsigned left = array[index - 1], right = array[index];
int check = (left < right) ? 1 : (left > right) ? -1 : 0;
if (check != result && index > 1)
return 0;
result = check;
}
return result;
}

void dump(const char* tag, unsigned array[], size_t length) {
printf("%s:", tag);
for (size_t index = 0; index < length; ++index) {
printf(" %u", array[index]);
}
int direction = order(array, length);
if (direction < 0)
puts(" decreasing");
else if (direction > 0)
puts(" increasing");
else
puts(" not ordered");
}

#define LEN(array) sizeof(array) / sizeof(array[0])

int main(void) {
unsigned a[] = {1, 2, 3, 4}, b[] = {5, 8, 3}, c[] = {3, 9}, d[] = {11};
dump("a", a, LEN(a));
dump("b", b, LEN(b));
dump("c", c, LEN(c));
dump("d", d, LEN(d));
}```
Thank you! I think my understanding of the task was faulty from the beginning which is why my code was pretty sketchy

15. Using size_t is the right thing to do, but feel free to use plain old int.

'size_t' is just an appropriately sized unsigned integer that matches the processor's address space.