Need to check if array is sorted using a function in C

Question

Basically, we need to check if the elements of an 1D array are sorted using a function: if they are sorted in an ascending order: return 1 if they are sorted in an descending order: return -1 if they are not sorted: return 0 This is the method im using, however it doesnt return 1 but isntead 0, Im unsure where is the problem, Any comments or new methods of solving the problem are welcome since im a beginner.

int Is_Sorted(int* A, int n){
    int tempcr, tempdcr;

for (int i=0; i<N-1; i++){

    if (A[i]<=A[i+1]){
        tempcr++;
    }else if (A[i]>=A[i+1]){
    tempdcr++;
    }
}
   if(tempcr==N-1){
        return 1;
   }else if(tempdcr==N-1)
        return -1;
   else
    return 0;

}

tempcr and temdcr are not initialised. Means that they can contain any garbage value to start off with. — kaylum
– kaylum, Commented Nov 23, 2021 at 21:28
Thank you very much. Is there any better way of solving this problem? — Pung
– Pung, Commented Nov 23, 2021 at 21:31
What should be the result if all items have the same value? Or if the array contains only one value? — Cheatah
– Cheatah, Commented Nov 23, 2021 at 21:33
Pung, note that n in Is_Sorted(int* A, int n) is not used in the function. — chux
– chux, Commented Nov 23, 2021 at 21:38
@kaylum Interesting micro-optimization. Consider if arrays are typically near ascending/descending, then the extra checks you suggest slow the compare. IMO, one optimization would check the the end-points. If they differ, only one order testing needed. IAC, these ideas are all O(n) complexity and do not reduce O(). — chux
– chux, Commented Nov 23, 2021 at 22:02

chux · Accepted Answer · 2021-11-24 05:24:03Z

2

Wrong logic

OP's code fails due to

}else if (A[i]>=A[i+1]){
tempdcr++;

should be

}
if (A[i]>=A[i+1]) {
  tempdcr++;

Consider the case when A[i]==A[i+1], both counters should increment.

Junk Values

Missing initialization @kaylum.

// int tempcr, tempdcr;
int tempcr = 0;
int tempdcr = 0;

Alternative approach:

There are 4 possibilities

Array has the same value value every where - or is of length 0.
Array is ascending. A[i] >= A[i-1] for all i > 0 and length is more than 0.
Array is descending. A[i] <= A[i-1] for all i > 0 and length is more than 0.
None of the above.

Simply loop and adjust two flags. int tempcr, tempdcr; counters not needed.

int Is_Sorted(const int* A, int n) {
  bool isAscending = true;
  bool isDescending = true;
  for (int i = 1; i<n; i++) { // start at 1
     if (A[i] < A[i-1]) isAscending = false;
     if (A[i] > A[i-1]) isDescending = false;
  }
  if (isAscending && isDescending) {
    return TBD; // Unsure what OP wants here
  }
  if (isAscending) {
    return 1;
  }
  if (isDescending) {
    return -1;
  }
  return 0;
}

Simplifications and some micro optimization possible, but something to clarify a clear approach.

Too much fun.

If int a[] is not constant, we can only use 1 test per iteration instead of 3: test i, is less, is more of the above code.

First look for inequality from the end toward the beginning. The first element is adjusted to be different from the last.

If we walk the entire list, we are done, otherwise the first part of the list differs from the last element.

If the last compare is ascending, set the first element to INT_MAX and search toward the beginning for a non-ascending pair.

Otherwise
If the last compare is descending, set the first element to INT_MIN and search toward the beginning for a non-descending pair.

Upon finding a compare failure occurs, either the array is unordered or we are at the beginning. If at the beginning, handle that special case.

In any case, only 1 compare per iteration.

#define ASCENDING 1
#define DESCENDING -1
#define UNORDERED 0
#define ALLSAME 1 // Adjust as desired
#define SHORT_LENGTH 1 // Adjust as desired

int is_sorted(size_t n, int *a) {
  if (n <= 1) {
    return n ? ALLSAME : SHORT_LENGTH;
  }

  int last = a[--n];
  int first = a[0];
  a[0] = !last;
  while (last == a[--n]) {
    ;
  }
  a[0] = first; // restore
  if (n == 0) {
    if (a[0] < a[1]) {
      return ASCENDING;
    }
    if (a[0] > a[1]) {
      return DESCENDING;
    }
    return ALLSAME;
  }

  if (a[n - 1] < a[n]) {
    // Only ascending, unordered possible
    a[0] = INT_MAX;
    while (a[n - 1] <= a[n]) {
      n--;
    }
    a[0] = first; // restore
    if (a[n - 1] <= a[n]) {
      return ASCENDING;
    }
  } else {
    // Only descending, unordered possible
    a[0] = INT_MIN;
    while (a[n - 1] <= a[n]) {
      n--;
    }
    a[0] = first; // restore
    if (a[n - 1] <= a[n]) {
      return DESCENDING;
    }
  }
  return UNORDERED;
}

I'll do some more testing later.

If the array is const, need 2 test per loop.

edited Nov 24, 2021 at 5:24

answered Nov 23, 2021 at 21:49

chux

158k17 gold badges160 silver badges311 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

500 - Internal Server Error Over a year ago

You can break out of the for loop once (if) both flags become false.

chux Over a year ago

@500-InternalServerError True, yet that is not a certain optimization as it could also slow the run time as it is doing more checking. Depends of typical array sets. IAC, it does not reduce O(). More here.

chux Over a year ago

@500-InternalServerError For fun, it might be interesting to bi-sect the array at each compare step and check the end points until down to size 1. Certainly slower in the worst case, but likely to catch early non-ordered arrays and allow for single order compare and/or end-early code.

Jonathan Leffler Over a year ago

For large arrays, or if the code is generalized to match qsort() or bsearch(), the early break is likely to be beneficial for performance — it avoids potentially many function calls. When the data type is int, the overhead of comparison is much smaller, so the early break vs extra testing is not so clear cut.

chux Over a year ago

@500-InternalServerError So I had some fun to only use 1 compare per loop.

|

Vlad from Moscow · Accepted Answer · 2021-11-23 22:19:39Z

For starters the function should be declared like

int Is_Sorted( const int* A, size_t n );

that is at least the first parameter should have the qualifier const because the passed array is not being changed within the function.

The variables tempcr and tempdcr were not initialized and have indeterminate values. So the function has undefined behavior. You have to initialize them like

int tempcr = 0, tempdcr = 0;

There is no sense to continue iterations of the loop if it is already known that the array is unsorted because it is inefficient.

Moreover the function has a logical bug.

Consider the array { 0, 0, -1 }

In this case in the first iteration of the loop the variable tempcr will be increased due to the if statement

if (A[i]<=A[i+1]){
    tempcr++;
}else if (A[i]>=A[i+1]){
tempdcr++;
}

But in the second iteration of the loop the variable tempdcr will be increased.

So the function will report that the array is unsorted though it is sorted in the descending order.

I would define the function the following way

int is_sorted( const int a[], size_t n )
{
    size_t ascending = 0, descending = 0;

    for (size_t i = 1; ( ascending == 0 || descending == 0 ) && i < n; i++)
    {
        if ( a[i-1] < a[i] ) ++ascending;
        else if ( a[i] < a[i-1] ) ++descending;
    }

    return descending == 0 ? 1 : ( ascending == 0 ? -1 : 0 );
}

If the passed array has all elements equal each other then the function considers it as sorted in the ascending order.

As pointed @chux - Reinstate Monica in his answer instead of counting elements you can use the corresponding variables as boolean objects. In this case the function can look like

int is_sorted1( const int a[], size_t n )
{
    int ascending = 0, descending = 0;

    for (size_t i = 1; ( ascending == 0 || descending == 0 ) && i < n; i++)
    {
        if ( a[i-1] < a[i] ) ascending = 1;
        else if ( a[i] < a[i-1] ) descending = 1;
    }

    return descending == 0 ? 1 : ( ascending == 0 ? -1 : 0 );
}

Collectives™ on Stack Overflow

Need to check if array is sorted using a function in C

2 Answers 2

6 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related