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.
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