1. Member
Join Date
Oct 2010
Posts
51
Rep Power
0

## Divide and Conquer

Hey there,
Could someone please explain the Divide and Conquer approach in Java.

All I know is that, for divide and conquer approach requires data to be sorted.
So basically we can either choose to do linear search or opt to do divide and conquer approach. What is the difference between them? Is one better than another?
I really need a clarification for this one.

2. Member
Join Date
May 2011
Location
Nokia, Finland
Posts
22
Rep Power
0
Originally Posted by whateverme
Hey there,
Could someone please explain the Divide and Conquer approach in Java.

All I know is that, for divide and conquer approach requires data to be sorted.
Does Java world have its own special meaning for "divide and conquer"?

In other engineering disciplines it just means splitting the problem into smaller pieces or sub-problems and solving them one by one, and then putting the results together as a solution of the original problem.

In this case sorting a group of objects is divided into smaller groups - maybe rough division into group of "bigger than X" and "smaller than X" and using that recursively. First all the elements are sorted as "bigger than X" and "smaller than X" the "X" being something like a value in the middle of the range. Then the subgroups are treated the same way, until a sub-sub-...-subgroup contains only one element.

You divide all groups into two mutually sorted sub-groups, and by division until the subgroups of only one element, conquer the whole problem.

In other fields, like politics, it means that people are divided into 2 or more groups that are treated differently, so the bitterness of the groups towards each other keeps them acting against each other and use their energy there instead of using their energy towards the group in power.
But then, that you already knew. Didn't you?

BTW, bubble-sort is quite fast, if otherwise suitable. Also insertion-sort is somewhat fast - not as fast as bubble-sort, but much simpler.
Last edited by turboscrew; 05-20-2011 at 01:55 PM.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•