Algorithms in Java

The quicksort family of algorithms that we studied in are based on the selection operation—finding the kth smallest element in a file. We saw that...

Given two ordered input files, we can combine them into one ordered output file simply by keeping track of the smallest element in each file...

Although implementing a merge seems to require extra space, we still find the abstraction of an in-place merge useful in the implementations of sorting methods...

Once we have a merging procedure, it is not difficult to use that procedure as the basis for a recursive sorting procedure. To sort a...

As we saw with quicksort, we can improve most recursive algorithms by handling small cases differently. The recursion guarantees that the method will be used...

As we discussed in every recursive program has a nonrecursive analog that, although equivalent, may perform computations in a different order. As prototypes of...

Table shows the relative effectiveness of the various improvements that we have examined. As is often the case, these studies indicate that we can cut...

Extra space appears to be required for a practical implementation of mergesort, so we may as well consider a linked-list implementation. In other words, rather...

The programs of this chapter, and quicksort from the previous chapter, are typical of implementations of divide-and-conquer algorithms. We shall see several algorithms with similar...