Thread: problem in divide and conquer approach to find max-min

i must say, some posts laserlight is cryptic, others he is right to the point, speaking in 2nd grade phrases, and people still sit there and go...."huh????"

lol

right off the bat, i see one big problem, your array is set for 20, then you ask to inputhow many are going in the array, with no error checking to make sure the # of inputs dont excede the array size.

another problem, is that you didnt post your complete code from beginning to end (yes your end is missing), your code is a mess, inconsistant spacing and tabs, and etc

BUT here is your major problem, to find min and max in a full array, that does not sort them first, you CANNOT half it. You either have to sort the entire array into numerical order, then min max at the beginning array[0], and the end array[n]

===OR===

you have to search one by one, through the entire array, array[0] to array[n]

in plain english, your trying to cut the search time in half, by skipping half of what you need to do...it isnt your compilier, it is your programming logic.

someone please correct me if i am wrong, or i missed something in the code snippits.

Crossfire, there IS actually a "fast select" algorithm to find what he wants. It has logic which seems vaguely similar to Quicksort, except it's faster, because it doesn't sort the array - it only finds the i'th value, within an array. It's complexity iirc is O(n), which is to say it's blinding fast.

I haven't used it before, but happened to stumble across it when trying to create a new sorting algorithm. It uses a partitioning scheme to split the array.

I'll get some more info on it, and post back.

Well, this is the link to QuickSelect.

Selection algorithm - Wikipedia, the free encyclopedia

Which is substantially faster selecting than sorting the array with QuickSort.

Originally Posted by ashutosh124

Adak, the two algos to find the max-min that you talked about are straightforward and I know this. What I want to do is to implement the "divide and conquer approach" to it. But your such a long post ends up prematurely without pointing the bug in it or suggesting a way out.

Wow, ashutos. This was so unnecessary. Instead of just saying 'thanks' to stahta01, who actually pointed out the bug you could not find, you criticize Adak, who gave you other advise, but did not point out the bug.


Your bug was like a big red flag for any experienced programmer with patience enough to read your whole program. But something makes it invisible: it is preceded by several larger red flags.


In first place, the assignment sucks. I hope your teacher made clear that this is just a 'conceptual' exercise and that, in The Real World, it is a bad idea to apply divide-and-conquer to this particular problem. The naive solution takes a time proportional to the size of the array. No sequential algorithm can beat this, and your solution must be, at least, several times slower. I hope that your teacher gives you several examples of cases where divide-and-conquer is good.


You didn't even describe the problem you were having when you started the thread! And this badly indented code... You used global variables...


With your last comment you just showed that std10093 was right with his attitude of not wasting time in trying to help you.

It was an honest answer, so I appreciate it. I thought he was looking for a min-max finding program - which he is not. He's looking for a recursive Quickselect-like program, ONLY. IF I understand him correctly, now.

Unfortunately, I am not familiar with this algorithm, but it motivates me to study that algorithm pseudo code, over on the link I gave (Wikipedia). I know partitioning is very fast (I was using that in a new sorting algorithm extensively), but I'm not clear why it would be better to use than a plain vanilla linear search.

Maybe it's not. I'm going to time them both, and see.

from what i read and understood, the way it devides the array into groups, (dont know if it sorts or not, but they do mention move alot) the groups being looked at are compaired, then compairs to another ect ect ect...i may be totally ass backwards and wrong. But it seems the grouping and excluding other groups (and maybe moving) cuts the time down compaired to just starting at 0 and going to xxx. But IF the search isnt perfect, it is like laserlight said, could take up to 4 times longer then 0-xxx.

to be honest i have always done the sort then min/max, or just the 0-xxx. The other is grated more complex and in theory can make a quick search of huge arrays, but it is to me too complicated, and too much code to be practical for most c programs. Unless your array has like 100K + records!!!

Originally Posted by Adak

It was an honest answer, so I appreciate it. I thought he was looking for a min-max finding program - which he is not. He's looking for a recursive Quickselect-like program,[..]

I think he was asked to make a program to find min-max with a divide-and-conquer approach. The goal would be to learn how divide-and-conquer works, not to get a fast min-max finding algorithm.

If the elements are in a normal array, not sorted, and there's no additional data... the only way to beat the min-max plain search is using some kind of parallelism.