10.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 particular error in question.

This example presents a lexicographic sort that works on arrays of integers written in Java. The original design for this algorithm can be found in Aho, Hopcroft, and Ullman, The Design and Analysis of Computer Algorithms [AHU74]. A lexicographic sort orders a set of tuples or strings of values. 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,

2 4 3 2 1 1 2 3 5 3 1 2 4 1 3 5 3 4 2 2 3 5 2 5 

performing a lexicographic sort of this set produces the following output:

1 2 3 4 5 1 3 5 2 3 5 2 4 2 5 3 1 2 4 3 2 1 3 4 2 

The algorithm works as follows:

1. Find the length of the longest tuple.

2. Make lists of value and location pairs that appear in the tuples.

3. Bucket sort the lists of value and...