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;

pairList, addElement (pair) ;

// bucket sort lists of value/location pairs

Vector bucket2= new Vector (l+maxVal) ;

for ( int i=0; i<bucket2.size(); ++i ) {

I Chapter I0

Get *Debugging by Thinking* now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.