Thread: Check if array is sorted

  1. #1
    Registered User
    Join Date
    Oct 2020
    Posts
    69

    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. #2
    Registered User
    Join Date
    Feb 2019
    Posts
    851
    Easier if you check only if the next value is greater than the previous (or vice-versa).

  3. #3
    Registered User
    Join Date
    May 2010
    Posts
    4,595
    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. #4
    Registered User
    Join Date
    Sep 2020
    Posts
    223
    Safe to assume it is the build-up to writing a sort function.

    Write the test first....

  5. #5
    Registered User
    Join Date
    May 2009
    Posts
    4,008
    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.
    Last edited by stahta01; 11-22-2020 at 01:29 PM.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  6. #6
    Registered User
    Join Date
    May 2009
    Posts
    4,008
    I suggest testing counterIncr > 0 and counterDecr == 0

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  7. #7
    Registered User
    Join Date
    Sep 2020
    Posts
    223
    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. #8
    Registered User
    Join Date
    May 2009
    Posts
    4,008
    I suggest posting the input that it fails to work on!

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  9. #9
    Registered User
    Join Date
    May 2009
    Posts
    4,008
    Quote Originally Posted by hamster_nz View Post
    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.
    Last edited by stahta01; 11-22-2020 at 03:08 PM.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  10. #10
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    240
    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. #11
    Registered User
    Join Date
    Sep 2020
    Posts
    223
    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. #12
    Registered User
    Join Date
    Oct 2020
    Posts
    69
    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. #13
    Registered User
    Join Date
    Oct 2020
    Posts
    69
    Quote Originally Posted by hamster_nz View Post
    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. #14
    Registered User
    Join Date
    Oct 2020
    Posts
    69
    Quote Originally Posted by Sir Galahad View Post
    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. #15
    Registered User
    Join Date
    Sep 2020
    Posts
    223
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How to check if an array of doubles is sorted?
    By Lina_inverse in forum C Programming
    Replies: 20
    Last Post: 10-06-2012, 03:12 PM
  2. How to detect if a array is sorted.
    By just_rookie in forum C++ Programming
    Replies: 14
    Last Post: 09-10-2012, 05:35 AM
  3. Selecting pivot in sorted array.
    By infantheartlyje in forum General Discussions
    Replies: 4
    Last Post: 10-14-2011, 09:43 AM
  4. how delete 1th element of a sorted array
    By vicky_4040 in forum C Programming
    Replies: 4
    Last Post: 10-11-2009, 06:12 AM
  5. finding max/min in a sorted array
    By Crcullen3916 in forum C++ Programming
    Replies: 9
    Last Post: 09-23-2008, 02:18 AM

Tags for this Thread