Java Reference
In-Depth Information
input from a physical process beyond the user's control). The relationship between
programs and functions is explored further in Section 17.3.
Algorithms: An algorithm is a method or a process followed to solve a problem.
If the problem is viewed as a function, then an algorithm is an implementation for
the function that transforms an input to the corresponding output. A problem can be
solved by many different algorithms. A given algorithm solves only one problem
(i.e., computes a particular function). This topic covers many problems, and for
several of these problems I present more than one algorithm.
For the important
problem of sorting I present nearly a dozen algorithms!
The advantage of knowing several solutions to a problem is that solution A
might be more efficient than solution B for a specific variation of the problem,
or for a specific class of inputs to the problem, while solution B might be more
efficient than A for another variation or class of inputs. For example, one sorting
algorithm might be the best for sorting a small collection of integers (which is
important if you need to do this many times). Another might be the best for sorting
a large collection of integers. A third might be the best for sorting a collection of
variable-length strings.
By definition, something can only be called an algorithm if it has all of the
following properties.
1. It must be correct. In other words, it must compute the desired function,
converting each input to the correct output. Note that every algorithm im-
plements some function, because every algorithm maps every input to some
output (even if that output is a program crash). At issue here is whether a
given algorithm implements the intended function.
2. It is composed of a series of concrete steps. Concrete means that the action
described by that step is completely understood — and doable — by the
person or machine that must perform the algorithm. Each step must also be
doable in a finite amount of time. Thus, the algorithm gives us a “recipe” for
solving the problem by performing a series of steps, where each such step
is within our capacity to perform. The ability to perform a step can depend
on who or what is intended to execute the recipe. For example, the steps of
a cookie recipe in a cookbook might be considered sufficiently concrete for
instructing a human cook, but not for programming an automated cookie-
making factory.
3. There can be no ambiguity as to which step will be performed next. Often it
is the next step of the algorithm description. Selection (e.g., the
if
statement
in Java) is normally a part of any language for describing algorithms. Selec-
tion allows a choice for which step will be performed next, but the selection
process is unambiguous at the time when the choice is made.
4. It must be composed of a finite number of steps. If the description for the
algorithm were made up of an infinite number of steps, we could never hope
