Close
Register
Close Window

CS330 - Data Structures, Algorithms, and Their Soc

Chapter 5 Recursion and Dynamic Programming

Show Source |    | About   «  5.3. Summary Exercises   ::   Contents   ::   6.1. Binary Trees Chapter Introduction  »

5.4. Recursive Sorting

5.4.1. Recursive Sorting

In looking for a recursive solution, you should first discover what characteristics of sorting make it a recursive problem. In order for any problem to be solved recursively it must satisfy:

1- There must be some way to break large problems down into simpler instances of the same problem.

2- Assuming that each of those subproblems can be solved by successive applications of the recursive procedure, there must be some way to generate a solution to the original problem from the solution to each of these smaller parts.

3- We must be able to determine a set of simple cases which can be solved diectly, without any further decomposition.

The next exercises will ask you to implement variations of merge sort.

   «  5.3. Summary Exercises   ::   Contents   ::   6.1. Binary Trees Chapter Introduction  »

nsf
Close Window