array sorted or not (bentley)

Let's talk about algorithms!

Moderator: Board moderators

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

array sorted or not (bentley)

Post by temper_3243 »

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

 if(arr[i] > arr[i+1]
  return 0;
but i don't get the partial checking part.
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by 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?
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by 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
ishtiak zaman
the world is nothing but a good program, and we are all some instances of the program
Post Reply

Return to “Algorithms”