分类：Algorithms

The development of a string data type implementation similar to Program 5 and 6 is of particular interest, because character strings are widely used as sort keys. 继续阅读“Sorting～Elementary Sorting Methods III”

Selection sort, insertion sort, and bubble sort are all quadratic-time algorithms both in the worst and in the average case, and none requires extra memory. Their running times thus differ by only a constant factor, but they operate quite differently, as illustrated in Figures 1 through 3. 继续阅读“Sorting～Elementary Sorting Methods II”

For our first excursion into the area of sorting algorithms, we shall study several elementary methods that are appropriate for small files, or for files that have a special structure. 继续阅读“Sorting～Elementary Sorting Methods I”

For our final example of a recursive program in this series, we consider one of the most important of all recursive programs: recursive graph traversal, or depth-first search. This method for systematically visiting all the nodes in a graph is a direct generalization of the tree-traversal methods that we considered in Recursion and Trees～ Mathematical Properties of Trees and Tree Traversal, and it serves as the basis for many basic algorithms for processing graph. 继续阅读“Recursion and Trees～Graph Traversal”

The tree-traversal algorithms that we considered in Recursion and Trees～ Mathematical Properties of Trees and Tree Traversal exemplify the basic fact that we are led to consider recursive algorithms for binary trees, because of these trees’ very nature as recursive structures. Many tasks admit direct recursive divide-and-conquer algorithms, which essentially generalize the traversal algorithms. We process a tree by processing the root node and (recursively) its subtrees; we can do computation before, between, or after the recursive calls (or possibly all three). 继续阅读“Recursion and Trees～ Recursive Binary-Tree Algorithms”

Before beginning to consider tree-processing algorithms, we continue in a mathematical vein by considering a number of basic properties of trees. We focus on binary trees, because we use them frequently throughout this series.  继续阅读“Recursion and Trees～ Mathematical Properties of Trees and Tree Traversal”

Trees are a mathematical abstraction that play a central role in the design and analysis of algorithms because

• We use trees to describe dynamic properties of algorithms.
• We build and use explicit data structures that are concrete realizations of trees.

We have already seen examples of both of these uses. We designed algorithms for the connectivity problem that are based on tree structure in 算法：C语言实现～连通性问题, and we described that call structure of recursive algorithms with tree structures in Recursion and Trees～ Divide and Conquer and Recursion and Trees～ Dynamic Programming. 继续阅读“Recursion and Trees～ Trees”

An essential characteristic of the divide-and-conquer algorithms that we considered in Recursion and Trees～ Divide and Conquer is that they partition the problem into independent subproblems. When the subproblems are not independent, the situation is more complicated, primarily because direct recursive implementation of even the simplest algorithms of this type can require unthinkable amounts of time. In this article, we consider a systematic technique for avoiding this pitfall for an important class of problems. 继续阅读“Recursion and Trees～ Dynamic Programming”

In Recursion and Trees～ Recursive Algorithms we have discussed the relationship between mathematical recurrences and simple recursive programs, and we consider a number of examples of practical recursive programs. In this article we examine the fundamental recursive scheme known as divide and conquer, which we use to solve fundamental problems in several later sections. 继续阅读“Recursion and Trees～ Divide and Conquer”