## array sorted or not (bentley)

Moderator: Board moderators

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

### array sorted or not (bentley)

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

Code: Select all

``````for(i=0;i<n-1;i++)
if(arr[i] > arr[i+1]
return 0;
``````
but i don't get the partial checking part.
misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
To 1), the answer is no. You can view the running of an algorithm as a game: the algorithm poses questions and tries to learn as much as necessary to decide whether the array is sorted. Imagine an evil opponent that wants to convince your algorithm that the array is sorted when it is not. If you don't look at some element, he can choose an arbitrary value for this element. You have to look at each element at least once to be sure the array is really sorted.

As of 2), I don't get it either. Maybe this "partial checking" is already mentioned somewhere in the above text?
ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
say the array length is n, and you have m processors(computers) that can work simultaneously. then you can decide whether tha array is sorted or not in n/m times.

Code: Select all

``````x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12
^        ^        ^         ^
p1      p2       p3        p4
``````
the 1st processor p1 checks the array[x1...x4]
the 2nd processor p2 checks the array[x4..x7]
the 3rd processor p3 checks the array[x7...x10]
the 4th processor p4 checks the array[x10..x12]

and of course all the processors should work simultaneously
and if you have only one processor, you can't do it
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program