# Divide and Conquer

• 05-20-2011, 01:07 PM
whateverme
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.

Thank you in advance.
• 05-20-2011, 01:51 PM
turboscrew
Quote:

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.