Friday, 1 December 2017

Explain a sorting technique which follows divide and conquer mechanism with an example. 

Divide and Conquer : 
This is a special case of recursion in which given problem is divided into two or more sub-problems of exactly same type and solution to problem is expressed in terms of solution to sub-problem. i.e. Dividing the list of elements into two approximately equal parts recursively and find solution independently then merged together into single list. Quick and merge sorts are based on Divide and Conquer concept.

The divide and conquer strategy solves a problem by :
1. Breaking into sub problems that are themselves smaller instances of the same type of problem.
2. Recursively solving these sub problems.
3. Appropriately combining their answers.

Two types of sorting algorithms which are based on this divide and conquer algorithm :
1. Quick sort: Quick sort also uses few comparisons (somewhat more than the other two). Like heap sort it can sort "in place" by moving data in an array.
2. Merge sort: Merge sort is good for data that's too big to have in memory at once, because its pattern of storage access is very regular. It also uses even fewer comparisons than heap sort, and is especially suited for data stored as linked lists.

Mukesh Rajput

No comments:

Post a Comment

Mukesh Rajput