### array sorted or not (bentley)

Posted:

**Sun Jul 02, 2006 8:09 pm**hi,

this is regarding a problem from programming pearls by jon bentley column 5.

I have few questions ,

1) how to check if an array is sorted or not. Can it be done it sub - linear time

2) In section 5.8 problem 5, he describes saying that checking a array is sorted or not takes n-1 operations. How can you add partial checking to the function at significantly less cost.

I understand the n-1 part doing a
but i don't get the partial checking part.

this is regarding a problem from programming pearls by jon bentley column 5.

I have few questions ,

1) how to check if an array is sorted or not. Can it be done it sub - linear time

2) In section 5.8 problem 5, he describes saying that checking a array is sorted or not takes n-1 operations. How can you add partial checking to the function at significantly less cost.

I understand the n-1 part doing a

Code: Select all

```
for(i=0;i<n-1;i++)
if(arr[i] > arr[i+1]
return 0;
```