Absolute C++ (4th Edition) part 85. KEY BENEFIT: C++ programming concepts and techniques are presented in a straightforward style using understandable language and code. KEY TOPICS: C++ Basics; Flow of Control; Function Basics; Parameters and Overloading; Arrays; Structures and Classes; Constructors; Operator Overloading, Friends, and References; Strings; Pointers and Dynamic Arrays; Separate Compilation and Namespaces; Streams and File I/O; Recursion; Inheritance; Polymorphism and Virtual Functions; Templates; Linked Data Structures; Exception Handling; Standard Template Library; Patterns and UML. MARKET: Useful for both beginning and intermediate C++ programmers. . | 848 Patterns and UML The Divide-and-Conquer Sorting pattern must divide the interval being sorted into two smaller intervals. If there were cases in which the split function divided the interval into an empty interval and the rest then one subinterval would be the same as the original interval being divided and infinite recursion would result. In the quick-sort realization we avoided this infinite recursion with the following lines from the definition of split if up 0 return begin up else return begin 1 Ensures that both pieces are nonempty. Without this extra adjustment the function split could compute 0 as the value of up and so divide the interval into two intervals with one of the two being empty. That would produce infinite recursion. The way this is usually avoided with a quick-sort realization and the way that produces the nicest code is to separate out the split point and divide only the remaining element so that the array interval is divided into three pieces the split point the subinterval before the split point and the subinterval after the split point. This guarantees that even if one subinterval is empty the other is shorter than the interval being divided. Thus infinite recursion is avoided. When these points are taken into consideration you are likely to change the Sorting pattern to the following when you are designing the quick-sort realization if end - begin 1 int splitPt split a begin end sort a begin splitPt - 1 sort a splitPt 1 end else sorting one or fewer elements so do nothing. Patterns are there to help you not to provide an obstacle. Feel free to adjust them if need be. PATTERN FORMALISM A well-developed body of techniques exists for using patterns. We will not go into the details here. The UML discussed in Section is one formalism used to express patterns. The place of patterns and any specific formalisms for patterns within the software design process is not yet clear. However it is clear that basic patterns as well as certain .
