Java Reference

In-Depth Information

worst case. It takes roughly
n

log
(
n
) operations to sort the array, which is a significant

improvement over the previous algorithms. For an array of size one million elements, it will

take roughly twenty million operations to sort the array.

Note that it is possible to combine several of the proposed sorting algorithms. For

example, insertion sort can be used on small arrays (e.g., less than 10 elements). For a

bigarray,mergesortcanbeapplieduntilthearraybecomessmallerthan10elements,at

which point insertion sort can be used again. Using merge sort guarantees us good worst-

case running time. Conversely, applying insertion sort to small arrays will limit the number

of recursive calls and make the program more ecient. In other words, the bubble sort,

insertion sort, and selection sort are good for sorting small arrays. The quick and merge

sort perform better on bigger arrays. Creating an algorithm that is a combination of two

sorting algorithms can give us the best of both worlds. For example, this is the approach

that is used in implementing the
Arrays.sort
and
Collections.sort
Java methods.

∗

14.5 Summary

The chapter describes the mechanisms behind recursive calls. It gives examples of using

recursion and shows how recursion can be used to implement binary search and different

sorting algorithms. Recursion is described in this topic because it is an important program-

ming technique. For example, it is not obvious how to solve the Tower of Hanoi or implement

merge sort without using recursion. On the other hand, one should not go overboard writing

recursive methods and the iterative approach is preferred when possible because it has less

overhead.

The chapter also briefly describes dynamic programming. This is a bottom-up approach

that calculates the result by starting with small problems and then merging the results. It

is an alternative to a recursive algorithm in some cases and it is the preferred choice when

applicable. The chapter also covered the topic of tail recursion. This is a scenario where all

the recursive calls are at the end of the execution paths of the method. The chapter shows

how tail recursion can be easily rewritten into an iterative solution that uses an infinite

while
loop.

14.6 Syntax

a.addAll(b);
⇒

.The
ArrayList b
is added to the end of the
ArrayList a
.

14.7 Important Points

1. A recursive solution breaks a big problem into smaller problems. The smaller prob-

lems are solved by applying exactly the same breakup algorithm. When the problem

becomes simple enough, the solution can be directly identified using the base cases.