Java Reference
In-Depth Information
Another improvement that is commonly made in practice is to switch to insertion
sort when the array is short, because the total number of operations of insertion
sort is lower for short arrays. The Java library makes that switch if the array length
is less than 7.
R
ANDOM
F
ACT
14.1: The First Programmer
Before pocket calculators and personal computers existed, navigators and
engineers used mechanical adding machines, slide rules, and tables of logarithms
and trigonometric functions to speed up computations. Unfortunately, the tablesȌ
for which values had to be computed by handȌwere notoriously inaccurate. The
mathematician Charles Babbage (1791Ȍ1871) had the insight that if a machine
could be constructed that produced printed tables automatically, both calculation
and typesetting errors could be avoided. Babbage set out to develop a machine for
this purpose, which he called a Difference Engine because it used successive
differences to compute polynomials. For example, consider the function f(x)=x
3
.
Write down the values for f(1), f(2), f(3), and so on. Then take the differences
between successive values:
647
648
1
7
8
19
27
37
64
61
125
91
216
Repeat the process, taking the difference of successive values in the second
column, and then repeat once again:
1
7
8 12
19 6
27 18
