Transcript Tracing and Evaluating algorithms in java

Steven Fox – Chapter 2 Sections 2.1.4 & 2.1.5
TRACING AND EVALUATING ALGORITHMS
IN JAVA
Chapter 2 Section 2.1.4
TRACE ALGORITHMS IN JAVA
TRACE ALGORITHM EXAMPLE SPECS.
As an example, we will consider the useful
process of maintaining a full index to a data file
(or another array).
 The Class BookIndex will be described on the
next slide.

BOOKINDEX CLASS

A Class has the following data members:
Public class BookIndex
{
// instance variables or data members
private String bookNum; // book reference number
private int pos;
// book details location in main file
// This class also has accessor and mutator methods.
}

A Class then declares an array of these objects:
BookIndex[] bookIndexes = new BookIndex[500];
STRUCTURE

This structure is used in a library containing
fiction and non-fiction books. There are several
shelf units labeled A-H. Each shelf unit has four
shelves in it.
BOOKNUM FIELD STRUCTURE

The BOOKNUM field has the following structure:







The first character indicates a fiction or non-fiction book
The second character indicates the shelf unit letter (A to H)
The third indicates the number of the shelf (1 is bottom, 4 is
top)
The last three numbers indicate a subject code
Example a book number: NG2023
The POS field indicates where the rest of the details of the
book are located in a direct access data file.
When a new book is added, an entry is made at the end of
the data file. The book number is then inserted in the
correct position in the array.
SAMPLE DATA
Element
0
1
2
3
4
5
6
7
BOOKNUM
FA1021
FA1122
FA1233
FA2099
FA2103
FA2145
FA2238
…
POS
3
6
2
5
0
4
1
…
A new book, with reference number FA2139 is added to the end of the data file at a
position contained in an identifier newPos. This book now needs to be added to the
array. Consider the following algorithm.
INSERT METHOD
private void insert(String bookNum, int newPos)
{
int i = newPos;
//pointer to the array
// Shuffle up array entries from top end to entry position.
// This will find the next smallest to bookNum (or first element).
while ( (i>0) && (bookNum.compareTo(bookIndexes[i].getBookNum()) < 0))
{
bookIndexes[i] = bookIndexes[i-1];
i = i-1;
}
//Check boundary position at i = 0
if (i != 0)
{
i = i + 1; //insert above smaller entry
}
bookIndexes[i] = new BookIndex(bookNum, newPos);
}
TRACING THE INSERT METHOD

Assuming that the array is as shown in the
table and the next vacant location in the file is
7, let’s trace the insert method.
newPos
bookNum
i
book
<compare condition>
Indexes[i]
7
FA2139
7
FA2238
TRUE
7
6
FA2145
TRUE
7
5
FA2103
FALSE
At this point, the array looks like:
Element
0
1
2
3
4
5
6
7
BOOKNUM
FA1021
FA1122
FA1233
FA2099
FA2103
FA2145
FA2238
FA2238
POS
3
6
2
5
0
4
1
2
EXECUTING

The array looks like:
Element
0
1
2
3
4
5
6
7
BOOKNUM
FA1021
FA1122
FA1233
FA2099
FA2103
FA2145
FA2238
FA2238
POS
3
6
2
5
0
4
1
2
and the value of i is 4. Therefore, we execute:
if (i != 0)
{
i = i + 1; // insert above smaller entry
}
bookIndexes[i] = new BookIndex(bookNum, newPos);
Thus, bookNum FA2139 and the value 7 are inserted into the
correct position (5) in the array.
EVALUATE ALGORITHMS IN JAVA

When you evaluate algorithms in Java, you are
essentially tracing them with virtual data. An
example is an algorithm that takes an array
NAMES and sorts it so that names are at the
front (Bob) and other values are at the end
(XXXX). To evaluate this, take sample arrays
with this type of data and run through the
algorithm. After multiple traces, you have
evaluated the algorithm.