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.
