6.1 Rules of the Game
Before considering specific algorithms, we will find it useful to discuss general terminology and basic assumptions for sorting algorithms. We shall be considering methods of sorting files of items containing keys. All these concepts are natural abstractions in modern programming environments. The keys, which are only part (often a small part) of the items, are used to control the sort. The objective of the sorting method is to rearrange the items such that their keys are ordered according to some well-defined ordering rule (usually numerical or alphabetical order). Specific characteristics of the keys and the items can vary widely across applications, but the abstract notion of putting keys and associated information into order is what characterizes the sorting problem.
If the file to be sorted will fit into memory, then the sorting method is called internal. Sorting files from tape or disk is called external sorting. The main difference between the two is that an internal sort can access any item easily, whereas an external sort must access items sequentially, or at least in large blocks. We shall look at a few external sorts in Chapter 11, but most of the algorithms that we consider are internal sorts.
We shall consider both arrays and linked lists. The problem of sorting arrays and the problem of sorting linked lists are both of interest: during the development of our algorithms, we shall also encounter some basic tasks that are best suited for sequential allocation and other tasks that are best suited for linked allocation. Some of the classical methods are sufficiently abstract that they can be implemented efficiently for either arrays or linked lists; others are particularly well suited to one or the other. Other types of access restrictions are also sometimes of interest.
We begin by focusing on array sorting. Program 6.1 illustrates many of the conventions that we shall use in our implementations. It consists of a driver that fills an array by generating random numbers, then calls a sort method to put the numbers in the array in order, then prints out the sorted result.
Program 6.1 xample of array sort with driver program
This program illustrates our conventions for implementing basic array sorts. The main method is a driver that initializes an array of doubles with random values, calls a sort method to sort that array, then prints out the ordered result.
The sort method here is a version of insertion sort (see Section 6.4 for a detailed description, an example, and an improved implementation). It uses the methods less (compare two items), exch (exchange two items), and compExch (compare two items and exchange them if necessary to make the second not less than the first).
We can use this code to sort arrays of any primitive numeric type simply by replacing double with the type name everywhere. With an appropriate implementation of less, we can sort arrays of items of any reference type (see Section 6.2).
class ArraySortBasic { static int cnt = 0; static boolean less(double v, double w) { cnt++; return v < w; } static void exch(double[] a, int i, int j) { double t = a[i]; a[i] = a[j]; a[j] = t; } static void compExch(double[] a, int i, int j) { if (less(a[j], a[i])) exch (a, i, j); } static void sort(double[] 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); } public static void main(String[] args) { int N = Integer.parseInt(args[0]); double a[] = new double[N]; for (int i = 0; i < N; i++) a[i] = Math.random(); sort(a, 0, N-1); if (N < 100) for (int i = 0; i < N; i++) Out.println(a[i] + ""); Out.println("Compares used: " + cnt); } } As we know from Chapters 3 and 4, there are numerous mechanisms available to us to arrange for our sort implementations to be useful for other types of data. We shall discuss the use of such mechanisms in detail in Section 6.2. The sort method in Program 6.1 refers to the items being sorted only through its first parameter and a few simple operations on the data. As usual, this approach allows us to use the same code to sort other types of items. For example, if code for generating, storing, and printing random keys in the main in Program 6.1 were changed to process integers instead of floating-point numbers, we would only have to change double to int in sort and its associated methods to have it sort arrays of integers. To provide such flexibility (while at the same time explicitly identifying those variables that hold items), our sort implementations will be implemented using a generic data type ITEM. For the moment, we can think of ITEM as int or double; in Section 6.2, we shall consider in detail data-type implementations that allow us to use our sort implementations for arbitrary items with floating-point numbers, strings, and other different types of keys, using mechanisms discussed in Chapters 3 and 4.
We can substitute for sort any of the array-sort implementations from this chapter or from Chapters 7 through 10. They all assume that items of type ITEM are to be sorted, and they all take three parameters: the array and the left and right bounds of the subarray to be sorted. They also all rely on less to compare keys in items and exch or compExch to exchange items. To differentiate sorting methods, we give our various sort routines different names. It is a simple matter to rename one of them or to change the driver in a program such as Program 6.1 without having to change any code in the sort implementation.
These conventions will allow us to examine natural and concise implementations of many array-sorting algorithms. In Section 6.2, we shall consider a driver that illustrates how to use the implementations in more general contexts, and numerous data type implementations. Although we are ever mindful of such packaging considerations, our focus will be on algorithmic issues, to which we now turn.
The example sort method in Program 6.1 is a variant of insertion sort, which we shall consider in detail in Section 6.4. Because it uses only compare exchange operations, it is an example of a nonadaptive sort: The sequence of operations that it performs is independent of the order of the data. By contrast, an adaptive sort is one that performs different sequences of operations, depending on the outcomes of comparisons (invocations of less). Nonadaptive sorts are interesting because they are well suited for hardware implementation (see Chapter 11), but most of the general-purpose sorts that we consider are adaptive.
As usual, the primary performance parameter of interest is the running time of our sorting algorithms. The sort method in Program 6.1 always does exactly N(N - 1)/2 comparisons (and exchanges), so it cannot be used when N is huge. The selection-sort, insertion-sort, and bubble-sort methods that we discuss in Sections 6.3 through 6.5 also require time proportional to N2 to sort N items, as discussed in Section 6.6. The more advanced methods that we discuss in Chapters 7 through 10 can sort N items in time proportional to N log N, but they are not always as good as the methods considered here for small N and in certain other special situations. In Section 6.8, we shall look at a more advanced method (shellsort) that can run in time proportional to N3/2 or less, and, in Section 6.10, we shall see a specialized method (key-indexed sorting) that runs in time proportional to N for certain types of keys.
The analytic results described in the previous paragraph all follow from enumerating the basic operations (comparisons and exchanges) that the algorithms perform. As discussed in Section 2.2, we also must consider the costs of the operations, and we generally find it worthwhile to focus on the most frequently executed operations (the inner loop of the algorithm). Our goal is to develop efficient and reasonable implementations of efficient algorithms. In pursuit of this goal, we will not just avoid gratuitous additions to inner loops but will also look for ways to remove instructions from inner loops when possible. Generally, the best way to reduce costs in an application is to switch to a more efficient algorithm; the second best way is to tighten the inner loop. We shall consider both options in detail for sorting algorithms.
The amount of extra memory used by a sorting algorithm is the second important factor that we shall consider. Basically, the methods divide into three types: those that sort in place and use no extra memory except perhaps for a small stack or table; those that use a linked-list representation or otherwise refer to data through references or array indices and so need extra memory for N references or indices, and those that need enough extra memory to hold another copy of the array to be sorted.
We frequently use sorting methods for items with multiple keys we may even need to sort one set of items using different keys at different times. In such cases, it may be important for us to be aware whether or not the sorting method that we use has the following property:
Definition 6.1 A sorting method is said to be stable if it preserves the relative order of items with duplicated keys in the file.
For example, if an alphabetized list of students and their year of graduation is sorted by year, a stable method produces a list in which people in the same class are still in alphabetical order, but a nonstable method is likely to produce a list with no vestige of the original alphabetic order. Figure 6.1 shows an example. Often, people who are unfamiliar with stability are surprised by the way an unstable algorithm seems to scramble the data when they first encounter the situation.
Figure 6.1. Stable-sort example
A sort of these records might be appropriate on either key. Suppose that they are sorted initially by the first key (top). A nonstable sort on the second key does not preserve the order in records with duplicate keys (center), but a stable sort does preserve the order (bottom).
Several (but not all) of the simple sorting methods that we consider in this chapter are stable. On the other hand, many (but not all) of the sophisticated algorithms that we consider in the next several chapters are not. If stability is vital, we can force it by appending a small index to each key before sorting or by lengthening the sort key in some other way. Doing this extra work is tantamount to using both keys for the sort in Figure 6.1; using a stable algorithm would be preferable. It is easy to take stability for granted; actually, few of the sophisticated methods that we see in later chapters achieve stability without using significant extra time or space.
As we have mentioned, sorting programs normally access items in one of two ways: either keys are accessed for comparison, or entire items are accessed to be moved. If the items to be sorted are large, it is wise to avoid shuffling them around by doing an indirect sort: we rearrange not the items themselves, but rather an array of references such that the first entry refers to the smallest item, the second entry refers to the next smallest item, and so forth. We could rearrange the items after the sort, but that is often unnecessary, because we do have the capability to refer to them in sorted order (indirectly, through the references). In Java, indirect sorting is actually the norm, as we shall see in the next section, where we address the process of sorting files of items that are not just simple numeric types.
Exercises
6.1 A child's sorting toy has i cards that fit on a peg in position i for i from 1 to 5. Write down the method that you use to put the cards on the pegs, assuming that you cannot tell from the card whether it fits on a peg (you have to try fitting it on).
6.2 A card trick requires that you put a deck of cards in order by suit (in the order spades, hearts, clubs, diamonds) and by rank within each suit. Ask a few friends to do this task (shuffling in between!) and write down the method(s) that they use.
6.3 Explain how you would sort a deck of cards with the restriction that the cards must be laid out face down in a row, and the only allowed operations are to check the values of two cards and (optionally) to exchange them.
6.5 Give all sequences of three compare exchange operations that will sort three elements (see Program 6.1).
6.8 Write a performance driver that runs sort multiple times on files of various sizes, measures the time taken for each run, and prints out or plots the average running times.
| Top |
EAN: 2147483647
Pages: 158