2 replies to this topic

[shabu]

Hello,

I have to consider the problem of finding the largest and smallest values of a sequence of n values.

I need to design a divide-and-conquer algorithm (pseudocode is fine) that solves this problem using no more than 3n/2 key comparisons.

I don't even really know where to begin in creating this algorithm.

If anyone could help me out with this I would really appreciate it!

Even just pointing me in the right direction would be great!

Thank you!

[WingedPanther]

Well, if you just compare the first two values, then the largest of those with the third value, then the largest of those with the fourth, you'll solve it in n-1 < 3n/2 comparisons

[fayyazlodhi]

In addition if you strictly like to go by divide and conquer (though you should have a pretty good reason not to use the above technique mentioned by winged panther which is the straight forward and best approach), then here is the idea:

Divide the n values into two equal halves. If each half contains more than two numbers, keep on dividing them (use recursion similar to that in merge sort)

When you reach the point with only two values left, compare them and return the smaller/larger (depending upon which one you are looking for at a time). On every return compare the two values obtained from the previous level. When you are done with all recursive calls you have the largest/smallest number. Repeat the process for the other.

It's running time sure is going to be more than above linear solution, but it is a divide and conquer approach.

Edited by fayyazlodhi, 03 May 2011 - 12:47 PM.
text edit