array sorted or not (bentley)

[temper_3243]

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]

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]

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