Java Reference
In-Depth Information
When seeing how the assignment to
p
is implemented, look at the code
underneath the statement “set
p
to …”; do not look at the rest of the program.
Learning to read a program on different levels of abstraction like this is impor-
tant. Study activities 8-6.1, 8-6.2, and 7-6.2 of
ProgramLive
for more informa-
tion on not thinking in terms of nested loops.
Analysis of execution time
We analyze the execution time of
selectionSort
. Finding the minimum of
a segment of size
n
requires
n-1
array comparisons. Therefore, the first itera-
tion of the loop makes
b.length - 1
array comparisons, the next iteration makes
b.length - 2
, etc. Here is the well-known formula for the sum of these values:
1+2+...+(b.length - 1) = (b.length - 1) * b.length / 2
Thus, selection sort requires on the order of (
b.length)
2
array comparisons.
Hence, it is
quadratic
in the size of the array to be sorted.
8.6
Parallel vs. class-type arrays
A list of item names together with their prices can be maintained in two arrays:
/**
The item names are in
items[0..size-1]
For each
items[i]
, its price is in
prices[i] */
String[] items=
new
String[1000];
double
[] prices=
new double
[1000];
int
size= 0;
Arrays
items
and
prices
are
parallel
arrays. If one had more data for each
item, say its weight, or price for buying two at a time, one would have more par-
allel arrays.
While parallel arrays can be used in this fashion, and in some cases may be
the quickest way to get a program going, they really are not good style. One
problem with them is that a method that operates on the arrays must have all the
parallel arrays as parameters. Also, a method that deals with one item, say
items[t]
, must be passed
prices[t]
and the corresponding elements of other
parallel arrays. Further, once the program is written, it may be difficult to change
it if a new parallel array is needed to contain some new property of items.
Better is to identify the
concept
involved —in this case, an item and its asso-
ciated properties— and to define a class whose instances are these items:
public class
Item {
/**
The name and price of the item
*/
private
String item;
private double
price;
//
Setter and getter methods would go here
}
Search WWH ::
Custom Search