O'Reilly logo

Data Structures Using Java by Duncan A. Buell

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

1.1 The Course of This Course 3
are inherently more efficient than others. Almost invariably, no matter how powerful
the computer, a person intending serious use of the computer to support some
activity will run up against the performance limitations of the machine and will
need to use better algorithms.
There are two ways in which computational performance can be improved:
One can change from an inefficient algorithm to an efficient algorithm, or one can
change from a poor implementation to a good implementation. It is usually argued
that the real improvements in performance (factors of 10 and 100) come from
improved algorithms, and that improved implementations usually provide factors
of perhaps 2 to 4. One should therefore look for a good algorithm and implement
that, and one should do a good implementation. That being said, it’s also possible
to overdo both of these. The really good algorithms will also be more complicated
to implement (and thus more prone to error), and the benefit of the algorithms is
usually only on large input sets. If the input data is small, then a good algorithm is
better than a naive algorithm and a great algorithm is probably overkill. Similarly,
if a small improvement in performance can be achieved by an implementation that
makes the code impossible to read, understand, and maintain, then maybe that’s
not good either.
1.1.3 Sorting
It will normally be the case that we want to keep an address book in sorted order,
usually by last name, because that is how we identify records for retrieval. It has
been estimated that perhaps a third of the CPU cycles expended in all of computing
are spent in sorting records to keep them accessible in a desired order. For this
reason, sorting records is an extremely important subject in data structures and in
computing in general, and thus we will spend an entire chapter on sorting.
There are sorting methods that are very simple to implement. Generally, since
there is no free lunch in this world, these are also the methods that are not very
good. The good sorting methods are somewhat more complicated, but it turns out
that a reasonably simple method—quicksort—is actually quite effective. Although
we can prove (and will prove) that quicksort is not the best method for all sorting
problems, it is quite good on average. We will spend a little more time on the bigger
picture of sorting because the comparison of the major sorting methods—quicksort,
heapsort,andmergesort—provides a good introduction into the trade-offs that good
software people need to make
between good algorithms that might be hard to implement and poorer algo-
rithms that are easy to implement;
between the best-case behavior,theworst-case behavior,andtheaverage-case
behavior of algorithms;

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required