Case Studies H
/0
I0.1
Case Study 2
I0.1.1
The Program
The case studies in this book are intended to demonstrate the use of some
of the concepts presented in the preceding chapters of this section of the
book. The defects analyzed are the actual mistakes made by the author
when developing this software. Different people are prone to make different
mistakes. Focus on the method used in debugging, rather than the particu-
lar error in question.
This example presents a lexicographic sort that works on arrays of inte-
gers written in Java. The original design for this algorithm can be found in
Aho, Hopcroft, and Ullman,
The Design and Analysis of Computer Algo-
rithms
[AHU74]. A lexicographic sort orders a set of tuples or strings of val-
ues. Dictionaries for natural languages have entries sorted in lexicographic
order. The tuples do not have to be the same length, and in general they are
not the same length. Given the following set of integer tuples,
24
321
1235
3124
135
342
235
25
performing a lexicographic sort of this set produces the following output:
257
258 I O. I Case Study 2
12345
135
235
2 4
2 5
3124
321
342
The algorithm works as follows:
o
.
.
4.
,
6.
.
8.
.
Find the length of the longest tuple.
Make lists of value and location pairs that appear in the tuples.
Bucket sort the lists of value and location pairs.
Create lists of unique values at each location.
Make lists of all strings of the same length.
Process each group of tuples of the same length from longest to
shortest.
Add to the queue the tuples of the same length.
Sort the tuples in the queue into buckets according to the value at
the current position.
Read the tuples from buckets that contain partially sorted tuples
and write them to the queue for more processing.
The code for the original program is listed as follows"
import java.util.Vector;
//
// Input:
// A sequence of string (tuples), A[I], A[2], ..
// i[n-l],
// whose components are integers in the range 0 to
// m-l. Let l[i] be the
// length of A[i] : (a[ill, a[i21,., a[il,i]).
/ / Output:
I O. I Case Study 2 259
// A permutation B[I], B[2],., B[n]
// of the A[i]'s such that B[I] <: B[2] < .... <= B[n]
//
// ................................
public final class Sort {
public static Vector lexSortTuples (
int [] [] tupleList) {
// find the length of the longest tuple
int maxLen= -i;
int tupleListLen= tupleList, length;
for ( int j: 0; j<tupleListLen; ++j ) {
int [] tuple= tupleList[j] ;
maxLen= Math.max(maxLen, tuple, length) ;
}
// make list of value/location pairs that
// appear in the tuples
int maxVal= - 1 ;
Vector pairList= new Vector () ;
for ( int j=0; j<tupleListLen; ++j ) {
int [ ] tuple= tupleList [j ] ;
int tupleLen= tuple.length;
for ( int k=0; k<tupleLen; ++k ) {
int value= tuple [k] ;
maxVal: Math.max(maxVal, value) ;
int [] pair= new int[2] ;
pair[0]= k+l;
pair [ 1 ] = value;