6.2 Generic Sort Implementations
Although it is reasonable to learn most sorting algorithms by thinking of them as simply putting arrays of numbers into numerical order or characters into alphabetical order, it is also worthwhile to recognize that the algorithms are largely independent of the type of items being sorted, and that is not difficult to move to a more general setting. In this section, we discuss the conventions that we shall follow so as to make our sort implementations useful in a variety of contexts. By treating this topic in detail at the outset, we can significantly expand the applicability of our code and the ease of using it.
Program 6.2 Item interface
Any class of items to be sorted must include a method that gives an object from the class the capability to determine whether it is less than another object from the class, or not.
interface ITEM { boolean less(ITEM v); } Program 6.2 defines the most essential convention: to sort items, we need to be able to compare them. In Java, we express such a requirement by defining an interface that includes the method that we need and requiring that any class that defines an item to be sorted implement this interface. Such implementations are not difficult to develop (we will consider three detailed examples later in this section, in Programs 6.8 through 6.11); the net result is that we can use the method less for comparisons in our implementations and still use them to sort all types of items. This interface is very similar to the Comparable interface in Java, which requires implementations to include a compareTo method.
Beyond this fundamental step, the path towards developing generic implementations constitutes a digression from the algorithmics of sorting, and you may safely skip the rest of this section and refer or return to it while learning the basic algorithms and their properties in Sections 6.3 through 6.6, Section 6.8, and Chapters 7 through 9. You can understand any of those implementations as substitutions for the sort method in Program 6.1 that use the primitive type double instead of the generic type ITEM.
Program 6.3 shows our convention for packaging sort implementations as a method in the class Sort. Any client with an array of objects from a class that implements the ITEM interface (and therefore defines a less method) can sort the array by invoking Sort.sort. In this book, we are going to consider numerous implementations of sort. To avoid confusion, we give each implementation a different name so that clients can just call sort but we can substitute a different implementation, either by substituting its code for the example method in this Sort.java file or by using Java's class path mechanism (see Section 4.6).
Program 6.3 Class for sort methods
We keep our actual sort code as a static method in a separate class so that any client can use it to sort any array of objects of any type that implements the less function, as specified in the ITEM interface.
This class is also a convenient place to put the static utility methods less, exch, and compExch, for use by any of our sort implementations.
class Sort { static boolean less(ITEM v, ITEM w) { return v.less(w); } static void exch(ITEM[] a, int i, int j) { ITEM t = a[i]; a[i] = a[j]; a[j] = t; } static void compExch(ITEM[] a, int i, int j) { if (less(a[j], a[i])) exch (a, i, j); } static void sort(ITEM[] a, int l, int r) { example(a, l, r); } static void example(ITEM[] a, int l, int r) { for (int i = l+1; i <= r; i++) for (int j = i; j > l; j--) compExch(a, j-1, j); } } Our sort implementations generally use a two-parameter static method less to compare items. When items are a primitive type, we can use the < operator, as in Program 6.1. When items are of a class that implements ITEM, then we can define less in terms of the class method less for that class, as shown in Program 6.3. Some of our sort implementations also use the exch and compExch methods, whose implementations for primitive items are given in Program 6.1 and for reference items in Program 6.3. Alternatively, we could add less to our item class and the exchange operations to our array class; or, since they are one-liners, we can just include them as private methods in sorts. Using these methods provides us the flexibility, for example, to instrument our sorts to count comparisons, as in Program 6.1, or to animate them, as in Program 6.16.
Program 6.4 Item ADT interface
This ADT interface illustrates how to define generic operations that we might want to perform on the items that we sort: compare each item with another, read an item from standard input, generate a random item, and compute a string representation for each item (so as to be able to print it out). Every implementation must include less (to implement the ITEM interface) and may include toString (otherwise, the default from Object will be taken).
class myItem implements ITEM // ADT interface { // implementations and private members hidden public boolean less(ITEM) void read() void rand() public String toString() } We have talked in detail about breaking our programs into independent modules to implement data types and abstract data types (see Chapters 3 and 4); in this section, we consider ways in which we can apply the concepts discussed there to build implementations, interfaces, and client programs for sorting algorithms. Specifically, we consider ADTs for
Items, or generic objects to be sorted
Arrays of items
The item data type provides us with a way to use our sort code for any type of data for which certain basic operations are defined. The approach is effective both for primitive types and for reference types, and we shall consider numerous implementations. The array interface is less critical to our mission; we include it as a useful example of generic programming in Java.
To work with particular types of items and keys, we declare all the relevant operations on them in an explicit interface, then provide application-specific implementations of the operations defined in the interface. Program 6.4 is an example of such an interface. We add to the required less method the capability to generate a random item, to read an item, and to convert an item to a string (so, for example, we can print it).
Program 6.5 Sortable-array ADT interface
This ADT interface illustrates methods that we might want to provide for clients that sort arrays: initialize with random values, initialize with values read from standard input, show the contents, and sort the contents. We do not need to refer to the type of the items being sorted to define any of these operations.
class myArray // ADT interface { // implementations and private members hidden myArray(int) void rand() void read() void show(int, int) void sort(int, int) } Our sorting algorithms work not just with items, but with arrays of items. Accordingly, Program 6.5 is an ADT interface that defines a sortable array abstraction. The operations defined in this interface refer to arrays, not to items, and are intended to support clients that test or exercise sorting algorithms. (It is easy to arrange for a client that needs to sort a single array to just directly invoke the sort method (see Exercise 6.11).) The methods in Program 6.5 are but a few examples of operations that we might want to perform on arrays. In a particular application, we might want to define various other operations (the Vector class in the java.util package is one approach to providing a general interface of this kind). The ADT of Program 6.5 focuses on sortable arrays. As usual, we can substitute different implementations of the various operations without having to change client programs that use the interface.
For example, Program 6.6 is a simple driver that has the same general functionality of the main program in Program 6.1. It either reads an array or generates a random one, sorts it, and prints the result. This program demonstrates that we can define such a computation without reference to the type of items being sorted: it is generic. We can use the same ADT to define drivers that perform more complicated tasks and then arrange to use them for arrays of various types of items, without changing any implementation code (see Exercise 6.12).
Program 6.6 Sort driver for sortable arrays
This driver for array sorts fills a generic array with generic items, sorts it, and shows the result. It interprets the first command-line argument to be the number of items to be sorted and the existence of the second command-line argument to be a switch indicating whether to generate random items or read them from the standard input stream. Since it uses the ADT from Program 6.5, this code does not refer to the type of item being sorted.
This arrangement not only allows us to both use each sort implementation to sort various types of data without changing any code but also to develop methods for arrays independently (perhaps to develop various different drivers).
class ArraySort { public static void main(String[] args) { int N = Integer.parseInt(args[0]); myArray A = new myArray(N); if (args.length < 2) A.rand(); else A.read(); A.sort(0, N-1); A.show(0, N-1); } } Program 6.7 is an implementation of the sortable array ADT of Program 6.5, which is a client of the generic item ADT of Program 6.4. To read an array from standard input, we read items; to generate a random array, we generate random items; to print an array, we print its items; and to sort an array, we use Sort.sort. The modular organization allows us to substitute other implementations, depending on the application. For example, we might use an implementation where show prints out only part of the array when testing sorts on huge arrays.
Finally, we consider the ADT implementations that we need to sort various types of items (the point of the exercise). For example, Program 6.8 is an implementation of the myItem ADT that we could use to have Program 6.6 sort arrays of integers. This implementation can be used with any sort client, any sort implementation, and any array implementation, without changing any other client or implementation code at all.
Program 6.7 Sample implementation of sortable-array ADT
This implementation uses the generic item interface of Program 6.4 to maintain a private array of items. It uses the rand, read, and toString methods for items to implement the corresponding methods for arrays. For greater flexibility, the sort method is kept in a static class Sort. Implementations of sort use the less method from the myItem implementation.
class myArray { private myItem[] a; private int N; myArray(int N) { this.N = N; a = new myItem[N]; for (int i = 0; i < N; i++) a[i] = new myItem(); } void rand() { for (int i = 0; i < N; i++) a[i].rand(); } void read() { for (int i = 0; i < N; i++) if (!In.empty()) a[i].read(); } void show(int l, int r) { for (int i = l; i <= r; i++) Out.println(a[i] + ""); } void sort(int l, int r) { Sort.sort(a, l, r); } } Developing implementations that are similar to Program 6.8 for other types of records and keys is straightforward, so this mechanism makes our sort implementations broadly applicable. For primitive types, this flexibility comes at the usual price of an extra level of indirection, as discussed later in this section. In most practical situations, however, we work not with primitive types but with records that have all manner of information associated with keys, and the advantages of working with a generic item type outweigh the costs. We conclude this section with two more examples that show how easily such applications can be handled.
Program 6.8 ADT implementation for integer items
This code implements the generic myItem ADT Program 6.4 for records that are integer keys.
class myItem implements ITEM { private int key; public boolean less(ITEM w) { return key < ((myItem) w).key; } void read() { key = In.getInt(); } void rand() { key = (int) (1000 * Math.random()); } public String toString() { return key + ""; } } Consider an accounting application, where we might have a key corresponding to a customer's account number, a string with the customer's name, and a floating-point number corresponding to that customer's account balance. Program 6.9 is an implementation of a class for such records. Now, suppose that we wish to process the records in sorted order. Sometimes, we might want to see them in alphabetic order by name; other times, we might want to see them in order of account number or in order of the size of the balance. Program 6.10 shows how we can arrange to do any of these sorts by deriving a class from Record that implements the ITEM interface that includes a method for specifying the sort key.
For example, if Program 6.10 is the file myItem.java (perhaps in a directory indicated as appropriate by the class path mechanism) then Program 6.6 sorts records on the account number field. If we want records to appear in order of the size of the balance, we simply set the sort key field value to 1, as follows:
Program 6.9 Sample record class
This example illustrates a typical class for records in a data processing application. It has three fields: a string, an integer, and a floating-point number. These might hold, for example, a customer's name, account number, and account balance, respectively.
class Record { int id; double balance; String who; static int SortKeyField = 0; public String toString() { return id+""+balance + " " + who; } } Record.SortKeyField = 1;
Similarly, if we set the sort key field value to 2, then we get a sort on the name field. We also could invoke sort multiple times with multiple sort key field values in order to sort the records multiple times, using different keys for each sort. Implementing and invoking this mechanism requires no change at all in the sort code itself.
The approach for deriving a class that implements the ITEM interface that is illustrated in Program 6.10 is a general one that is useful in many applications. We can imagine a large body of software based on processing such records; with this approach, we can add the capability of sorting them without much extra expense and without changing any of the other software.
We can use the same approach to put our sorts to use for all types of data such as complex numbers (see Exercise 6.13), vectors (see Exercise 6.18), or polynomials (see Exercise 6.19) without changing the sort code at all. For more complicated types of items, the ADT implementations have to be more complicated, but this implementation work is completely separated from the algorithm-design questions that we have been considering. We can use these same mechanisms with most of the sorting methods that we consider in this chapter and with those that we shall study in Chapters 7 through 9 as well. We consider in detail one important exception in Section 6.10 it leads to a whole family of important sorting algorithms that have to be packaged differently, which is the subject of Chapter 10.
Program 6.10 ADT implementation for record items
This example shows how we can implement the ITEM interface and the myItem ADT by extending another class, in this case the data-processing records of Program 6.9. The implementation of the rand method is omitted. The less implementation allows clients to change the field used for sorting.
class myItem extends Record implements ITEM { public boolean less(ITEM w) { myItem r = (myItem) w; switch (SortKeyField) { case 2: return who.compareTo(r.who) < 0; case 1: return balance < r.balance; default: return id < r.id; } } void read() { id = In.getInt(); balance = In.getDouble(); who = In.getString(); } } The approach just described is known in the classical literature as pointer sorting, so called because we process references to items and do not move the data itself. In programming languages such as C and C++, programmers explicitly manipulate pointers; in Java, pointer manipulation is implicit. Except for primitive numeric types, we always manipulate references to objects (pointers), not the objects themselves.
For example, consider the difference between sorting chars (say, by changing all the doubles in Program 6.1 to chars) and using a myItem implementation like Program 6.8, except with a char key, as illustrated in Figure 6.2. In the former case, we exchange the characters themselves and put them in order in the array; in the latter, we exchange references to myItems, which contain the character values. If we are doing nothing more than sorting a huge file of characters, we are paying the cost of an equal number of references plus the extra cost of accessing the characters through the references. Note that if we were to use a Character object as the key field in the myItem implementation, we would add still another level of references.
Figure 6.2. Pointer sort
The typical situation in Java is that we sort a group of objects by rearranging references (pointers) to them instead of moving the objects. The top diagram illustrates a typical array to be sorted, with references to objects having the keys E X A M P L E, in that order. The bottom diagram illustrates the result of a sort, leaving the references such that the array refers to the objects in the order A E E L M P X.
For large records, which we typically encounter in practical applications, the extra space required for the references is small compared to the space required for the records themselves, and the extra time required to follow the references is more than offset by the time saved because the records do not have to be moved around. On the other hand, for small records, Java offers no good solution, except encoding records in a primitive numeric type, an approach recommended only for experts.
For another look at the issues involved, consider the problem of sorting strings. Program 6.11 illustrates the most natural way to proceed in Java: a direct implementation of the myItem ADT for String objects, using a String field for the key. This implementation (which works for any kind of object) adds a level of references: the array contains references to myItem objects, which contain Strings, which are references to sequences of characters. There are various ways to remove this second level of indirection in Java if necessary, but, in Java, it is common for programmers to accept extra levels of indirection in favor of the easily understood reference model. Since Java has automatic memory management, programmers do not have to face many of the serious issues that bedevil people who program in other languages.
We are faced with memory-management choices of this kind any time that we modularize a program. Who should be responsible for managing the memory corresponding to the concrete realization of an object: the client, the data-type implementation, or the system? Who should be responsible for decided which memory is unused and then reclaiming it? In many languages, there is no hard-and-fast answer to these questions; In Java, the system takes responsibility.
Program 6.11 ADT implementation for string items
This code implements the generic myItem ADT of Program 6.4 for records that are string keys.
class myItem implements ITEM { String key; public boolean less(ITEM w) { return key.compareTo(((myItem) w).key)<0; } void read() { key = In.getString(); } void rand() { int a = (int)('a'); key = ""; for (int i = 0; i < 1+9*Math.random(); i++) key += (char) (a + 26*Math.random()); } public String toString() { return key; } } There are certainly many benefits of the Java approach. In the context of sorting, the primary advantage of using references is that we avoid intruding on the data being sorted. We can "sort" a file even if read-only access is all that is available. Moreover, with multiple reference arrays, we can have two different sorted representations of a single body of data. This flexibility to manipulate the data without actually changing them is very useful in many applications. A full discussion of the issues involved is beyond the scope of this book, but we do need to be mindful of the impact on performance so that we can improve things when critical in applications. We will return to this issue in Section 6.6.
Another advantage of using references is that we avoid the cost of moving full records. The cost savings is significant for files with large records (and small keys), because the comparison needs to access just a small part of the record, and most of the record is not even touched during the sort. The reference approach makes the cost of an exchange roughly equal to the cost of a comparison for general situations involving arbitrarily large records (at the cost of the extra space for the references). Indeed, if the keys are long, the exchanges might even wind up being less costly than the comparisons. When we estimate the running times of methods that sort files of integers, we are often making the assumption that the costs of comparisons and exchanges are not much different. Conclusions based on this assumption are likely to apply to a broad class of applications, when we are sorting reference objects.
The approach that we have discussed in this section is a middle road between Program 6.1 and an industrial-strength fully abstract set of implementations complete with error checking, management of external storage, and even more general capabilities. Packaging issues of this sort are of increasing importance in some modern programming and applications environments. We will necessarily leave some questions unanswered. Our primary purpose is to demonstrate, through the relatively simple mechanisms that we have examined, that the sorting implementations that we are studying are widely applicable.
Exercises
6.10 Write a myItem ADT implementation for use in sorting doubles.
6.12 Modify your performance and exercise drivers from Exercises 6.8 and 6.9 to use Sort.sort. Add public methods to Program 6.3 to return the number of comparisons and exchanges used by the most recent sort, so that you can study those quantities in addition to the running time.
x + iy using the magnitude
for the key. Note: Ignoring the square root is likely to improve efficiency.
6.17 Extend the rand method in your implementation of myItem for doubles (see Exercise 6.10) so that it generates test data according to distributions similar to those illustrated in Figure 6.15. Provide an integer parameter for the client to use to specify the distribution.
6.19 Write classes for use in having the sorting methods sort polynomials (see Section 4.10). Part of your task is to define an appropriate ordering.
| Top |
EAN: 2147483647
Pages: 158