Content-type: text/HTML 1998 - Paper 415.231: Dr. Georgy Gimel'farb
Department of Computer Science
The University of Auckland
Tamaki Campus Bldg 731 Room 311
phone: 373 7599 ext. 6609
Email: g.gimelfarb@auckland.ac.nz
1 JAVA: EXCEPTIONS
1.1 Why exceptions?
1.2 Simple examples
of runtime errors
1.3 How to catch
an exception?
1.4 How to define
your own exception
1.5 More about
creating exception types
1.5.1
The throws clause
1.5.2
Three choices for exception processing
1.5.3
When to use exceptions?
2 JAVA: STREAM I/O
2.1 How to locate
and read files?
2.1.1
Data files
2.1.2
Package java.io
2.1.3
Overview of Reader class
2.1.4
Overview of Writer class
2.1.5
Several standard stream types
2.1.6
Reading a text file
2.2 Reading and
counting characters
2.3 Reading text
files line-by-line
2.4 Copying a text
file
2.5 Reading numbers
2.6 Reading data
files
2.6.1
Data i/o interfaces
2.6.2
Example of data file i/o
2.7 Getting file
parameters: class java.io.File
3 ALGORITHM ANALYSIS
3.1 Some informal
definitions
3.1.1
Efficiency of algorithms
3.1.2
A few ``how?''
3.1.3
Why do you need to analyse algorithms?
3.1.4
Time-memory relations
3.1.5
First examples of algorithm analysis
3.1.6
Problem 1: the sum of all items
3.1.7
Problem 2: the contiguous subsequence sums
3.1.8
How to use more memory for running faster
3.2 Running time
for simple loops
3.3 Tools for analysing
time complexity
3.3.1
Running time and input data size
3.3.2
``Big-Oh'' tool for analysing algorithms
3.3.3
``Big-Oh'' notation
3.3.4
Examples of ``Big-Oh'' relations
3.3.5
Time complexity of algorithms
3.3.6
Some features of ``Big-Oh''
3.4 Worst-case
and average-case performance
3.4.1
Basic recurrence relations
3.4.2
Recurrence T(n) = T(n-1)+n =n ·(n+1)/ 2
3.4.3
Recurrence T(n) = T(n/2)+1 = log2n
3.4.4
Recurrence T(n) = T(n/2)+n =2·n
3.4.5
Recurrence T(n) = 2 ·T(n/2)+n =n
·log2n
3.5 Algorithm
analysis: possibilities and limitations
4 EFFICIENCY OF SORTING
4.1 Order and ordering
relation.
4.2 Insertion sorting
4.2.1
Average complexity
4.2.2
Additional analysis of insertion sort
4.3 Algorithm Shellsort
4.3.1
Time complexity
4.4 Algorithm Mergesort
4.4.1
Linear-time merging of sorted arrays
4.4.2
Java implementation
4.5 Algorithm Quicksort
4.5.1
Analysis of Quicksort
4.5.2
Choosing the pivot
4.5.3
Partitioning strategy
4.5.4
Java implementation
4.6 Algorithm Heapsort
4.6.1
Binary heap
4.6.2
Linear time heap construction.
4.6.3
Another approach to yield the same result
4.6.4
Heapsort implementation.
4.7 Data selection
4.7.1
Analysis of Quickselect
4.8 Lower complexity
bound for sorting
4.8.1
The worst-case complexity
4.8.2
The worst-case complexity: another approach
4.8.3
The average-case complexity
5 EFFICIENCY OF SEARCH
5.1 Sequential
search
5.2 Binary search
5.2.1
More detailed algorithm analysis.
5.2.2
Comparisons and binary trees
5.2.3
Complexity of binary search
5.2.4
Faster binary search
5.2.5
Interpolation search
6 BINARY SEARCH TREES: EFFICIENCY OF OPERATIONS
6.1 What is the
binary search tree?
6.1.1
Operations within a tree
6.1.2
Find/insert operations
6.1.3
Node removal
6.1.4
Order statistics
6.2 Performance
analysis of binary search tree operations
6.3 Balanced trees
6.3.1
AVL trees
6.3.2
Red-black trees and AA-trees
6.3.3
B-trees: efficiency of external search
A TEST BENCH FOR COMPARING SORTING METHODS
B CLASS SortMeth OF SORTING METHODS
C CLASS TestMeth OF SORTING METHODS
1 Program throwing
a runtime error.
2 Stack trace for
a program crash.
3 Information in
a stack trace.
4 One more runtime
error.
5 Stack trace message
for a program crash.
6 Stack trace message
for a program crash.
7 Simple exception
handling.
8 Output of DivideByZeroTest.
9 Structure of exception
handling.
10 Processing without
an exception event.
11 Processing with
an exception event.
12 Handling two
different exceptions.
13 Output of ExceptionTest.
14 User-defined
exception class.
15 Example of using
the exception class defined in Figure 14.
16 Example of using
the exception class defined in Figure 14.
17 Output of OwnExceptionTest..
18 Compile-time
error message.
19 User-defined
exception classes for a binary tree search in Section 6.
20 Java data streams.
21 Connecting streams
to get the desired processing.
22 Simple program
that locates, reads, and prints a text file.
23 Class FileView
forming a search window for locating a file.
24 Search window
formed by FileView.
25 Simple program
that counts characters and white spaces.
26 Reading text
lines.
27 Program that
copies a text file.
28 Simple program
that reads numbers.
29 Simple program
that writes and reads a data file (part 1).
30 Simple program
that writes and reads a data file (part 2).
31 Program for retrieving
disk information about a file or a directory.
32 Part 2 of the program
in Figure 31.
33 Part 3 of the program
in Figure 31.
34 Part 4 of the program
in Figure 31.
35 ``Don't exist''
output of FileInformation.
36 File information
displayed by FileInformation.
37 Directory information
displayed by FileInformation.
38 Time-space boundaries.
39 Simple insertion
sorting.
40 Simple insertion
sorting giving a standard run-time exception.
41 Shellsort implementation
with divide a gap by 2.2.
42 Linear-time merging
of two sorted arrays.
43 Basic Mergesort
routines
44 Merging two sorted
halves of a subarray.
45 Quicksort: median-of-three,
partitioning, cutoff of small arrays
46 Methods used
in the basic Quicksort routine in Figure 45 .
47 A complete binary
tree and its array representation.
48 A binary heap
and its array representation.
49 Basic Heapsort
routines.
50 Quickselect:
median-of-three, partitioning, cutoff of small arrays
51 Decision tree
for n = 3
52 Sequential search.
53 Binary search
using three-way comparisons.
54 Binary search
for the integer key 42.
55 Binary tree representation
of the sorted array using the binary search.
56 Faster binary
search using two-way comparisons.
57 Binary trees:
only the leftmost tree is a binary search tree.
58 Examples of find
and insert operations in the binary search tree.
59 Binary search
tree with the depth about log2n.
60 Binary search
trees with the depth about n.
61 Removal of the
node with key 10 from the shown binary search tree.
62 Binary search
tree with order statistics.
63 Binary search
trees obtained by inserting permutations of 1,2,3,4 (a).
64 Binary search
trees obtained by inserting permutations of 1,2,3,4 (b).
65 Binary search
trees obtained by inserting permutations of 1,2,3,4 (c).
66 Multiway search
tree of order m = 4.
67 B-tree of order
m = 4 with storage size l = 7.
1 Character-stream
classes in the java.io package.
2 Corresponding character-
and byte-stream classes in the java.io package.
3 Basic methods from
the public class BufferedReader.
4 Sizes of Java primitive
data types.
5 I/O methods for
Java's data types.
6 Methods of the
class File.
7 Typical algorithmic
operations and operands.
8 Input data size
for different algorithms.
9 Relative growth
of time complexity as input size increases from n = 5 to n
= 625.
10 The largest sizes
n of input data that can be processed by an algorithm with running
time O(f(n)) for various f(n).
11 Example of the
insertion sort.
12 Number of inversions
for an array element with respect to all preceding elements
13 Example of Shellsort.
14 Example of pivot
positioning in Quicksort.
15 Successive steps
of the Heapsort.
More reading about Java...
More reading about algorithm analysis...
This handout covers the following topics of the paper 415.231: (i) Java exceptions and stream I/O and (ii) practical and theoretical aspects of program performance. Techniques are presented for measuring performance of programs, for instance, the Big-Oh notation for expressing an efficiency of a program, basic recurrences to estimate running times, and similar tools. Tradeoffs between time and space in programming are briefly discussed. The performance of basic sorting and searching algorithms is analysed. In particular, a simple sorting by insertion is compared with much more efficient Shellsort, Mergesort, Quicksort, and Heapsort algorithms. Efficiency of standard binary search techniques, binary tree searching, and operations with balanced binary search trees (in particular, AVL, red-black, AA, and B-trees) is discussed.
The handout explains in more detail some basic topics on Java programming and algorithm analysis in the recommended textbook of Mark A. Weiss (in part, by using available auxiliary sources).
You can hardly find a programmer who has not written a program which is successfully compiled but crashes when it runs. There are a lot of reasons for this. In the simplest cases, the program may try to divide an integer by zero, to index data outside the legal bounds of an array, to compute a value outside the legal range (so-called arithmetic overflow), to pass invalid method parameters, to use more than available memory space, and so on. There could be much more complex cases when specific combinations of input data result in a program crash. Some programming languages and their implementations react to such errors by immediate terminating the program. This is a real problem if you have developed a so-called mission-critical or business-critical application. Such a program must be robust and reliable in the real-world environment when any legal or illegal input data combinations could be met. In other languages the application may behave in an arbitrary or unpredictable manner, and this is even worse in practice.
Java uses a much more attractive way to detect errors and other violations, which provides portability and robustness of the resulting programs. The Java exception-handling mechanism is similar to that used in C++ programming language but develops it further. When a Java component, say, a class object, encounters a difficulty, a Java Virtual Machine signals this error to the program by a special exception. The environment of that component can be programmed to catch that exception and to deal with it.
An exception is a Throwable object that stores the information about the abnormal behaviour of the program. Such an object is transmitted outside the normal return sequence and propagated back through the calling sequence until some routine catches the exception. Java's exception-handling capabilities are especially important to an object-oriented world where large program systems are constructed from reusable prefabricated components bult by different programmers.
Remember that
Java is extremely strict about processing exceptional cases in a program and has much better security and error handling requirements than other programming languages such as C or C++.
Therefore, you have to learn the exceptions, their hierarchy, and their handling, to know how to write your program so it handles any exceptional problems that may occur, and to understand how you can involve your own definitions of exceptions.
During execution, applications can run into many kinds of errors of varying degrees of severity. When methods are invoked on an object, the object can detect:
There are strong reasons not to test for all possible error conditions: code becomes unintelligible if each method invocation checks for all possible errors before the next is executed, these checks affect notably the program performance, and error flags must be unified if the program is created by a big team. Exceptions provide a clean way to check for errors without cluttering code. Exceptions also provide a mechanism to signal errors directly rather than using flags or side effects such as fields that must be checked. Exceptions make the error conditions that a method can signal an explicit part of the method's contract. The list of exceptions can be seen by the programmer, checked by the compiler, and preserved by extended classes that override the method.
Java has special (and, probably, somewhat novel to you) statements, namely, try, catch, finally, throws, and throw, which allow you
If the exception is not caught, a default exception handler takes effect, usually printing useful information about where the exception was thrown (such as a call stack).
The simple Java class RunError in Figure 1 is designed specially to crash due to dividing by zero when the program is running. Such errors are called runtime errors.
1 class RunError
2 public static void main( String [] args ) {
3 int result = divide(1, 0); // Illegal divisor 0
4 }
5 static int divide( int dividend, int divisor ) {
6 return dividend / divisor; // Will crash when divisor = 0
7 }
8 }
The compilation using the Java Language Compiler javac or any other implementation will be successful because the compilers cannot check whether the initial data for processing are legal. But, when you run the Java Interpreter java then the message called a stack trace is obtained (see Figures 2 and 3).
java.lang.ArithmeticException: / by zero
at RunError.divide(RunError.java:6)
at RunError.main(RunError.java:3)
The message in Figure 2 is given for a JDK1.1.4 versions of the Java Language Compiler javac and the Java Interpreter java installed on an IBM PC compatible platform. It may differ slightly for various Java implementations and platforms but the information will be mostly the same.
This message points out the type of exception and traces the calls to the place where the exception occured. You have to read the stack trace, which contains three text strings, from the top:
Of course, in this simple example the stack trace told what you already knew. But, for larger programs such messages are very useful.
Let us consider one more example of a runtime error (see Figure 2):
1 class RunError1 {
2 public static void main( String [] args ) {
3 int [] array = new int[10]; // Legal indices are 0,...,9
4 fillArray( array, 20 ); // Wrong limit
5 }
6 static void fillArray( int [] arr, int wrongLimit ) {
7 for(int i = 0; i < wrongLimit; i++ )
8 arr[ i ] = i // Will crash when i = 10
9 }
Here, the following stack trace is obtained (see Figure 2):
java.lang.ArrayIndexOutOfBoundsException: 10
at
at RunError1.main(RunError1.java:4)
It is quite possible that your Java implementation will give more detailed message at string 2 (see Figure 6). But, even the text in Figure 5 is quite sufficient to find the desired point in the program. It contains a short message that the wrong index value is 10 (string 1) and tells you that the method that caused the error had been called in line 4 of Run.Error1.main().
java.lang.ArrayIndexOutOfBoundsException: 10
at RunError1.fillArray(RunError1.java:8)
at RunError1.main(RunError1.java:4)
Of course, there exists a popular alternative way for dealing with such malfunctions: to put error-handling code directly at all the places where the errors can occur. But this has at least the two following drawbacks.
Java's exception handling allows you to remove error-handling parts from the ``main stream'' of computations. This improves program clarity, enhances modifiability, speeds computations, and makes programs more robust.
Exception handling is designed for dealing only with synchronous errors that occur as the program executes its instructions. There exist also asynchronous events to be caught, such as network message arrivals, disk i/o completions, keystrokes, etc. These latter events, of course, are legal and not erroneous. Thus, they are best handled through other means, such as interrupt processing. Also, if your method is able to avoid a possible error it need not throw an exception. But, in many cases an error can be easily detected at the lower level (that is, inside a particular method) but only the higher level (that is, the caller of the method) can tell how to cope with this error.
Look once more to the example in Figure 1. It is very easy to detect the exceptional case when divisor is zero. But, only the main program may know which value of result has to be used in this case. Thus, it is much safer to throw back the exception signalling that the case occured than to invent a particular ``exceptional-case'' behaviour of the low-level method divide.
Therefore, the typical programming rule is as follows:
you must use Java's exception handling in all situations where malfunctions have to be processed at a higher level than that which detected the malfunction.
To implement the exception handling you need know the diverse hierarchy of the exception and error classes existing in Java. The hierarchy is rooted at class Throwable, a direct subclass of Object. The classes Exception and Error are direct subclasses of Throwable. The class Exception is the superclass of all the exceptions that ordinary programs may wish to recover from. The class Error and its standard subclasses are exceptions which ordinary programs are not ordinarily expected to recover from. The class RuntimeException is a direct subclass of Exception.
Standard exception classes are declared by the standard Java packages java.lang, java.util, java.io, and java.net. For instance, part of the hierarchy of the exception classes defined in the package java.lang is as follows:
We will not describe these classes in detail. If necessary, you may refer to the available Java documentation. But, you need know that Java compilers check for exception handlers with respect to most of the standard classes, except for the class RuntimeException and its subclasses. To take advantage of such compile-time checking, you may define your own additional exception classes as checked exception classes. In so doing, you have to define them specifically as subclasses of Exception that are not subclasses of RuntimeException.
Typically you will use only a small part of the standard exception classes in your programming. Of course, you will need most of them for developing large and complicated programs in future. But, here we restrict the consideration to a few particular exceptions such as ArithmeticException and ArrayIndexOutOfBoundsException in Figures 2 and 5 which are the subclasses of the class RuntimeException.
When a program throws an exception back this means that the program instantiates a new object of this class and traces back through the methods that have been called, to see if any of them can catch and handle this object. If none can, and the trace back arrives at the Java Interpreter or AppletViewer, the program is terminated and the stack trace is printed out. But, it is possible to catch a thrown exception to avoid such a crash because the circumstances which are fatal at the lower level may be easily handled and fixed at the higher level.
Figure 7 shows a simple program which uses Java's
try, catch, finally and throw statements
to detect, indicate, and handle a divide-by-zero ArithmeticException.
If you run this example then the output obtained after normal execution
of the program will be similar to that in Figure 8.
Notice that the program in Figure 7 uses two methods
defined for the class Exception. The methods getClass()
and getMessage() allow the caller to get a name and a String
message, respectively, from a thrown exception.
1 class DivideByZeroTest {
2 public static void main( String [] args ) {
3 int result = -1;
4 for(int k = 0; k < 4; k++) {
5 System.out.println();
6 try {
7 System.out.println ( "6 / " + k + " = " );
8 result = divide( 6 , k );
9 System.out.println ( result );
10 }
11 catch ( Exception e ) {
12 System.out.println ( " !! Thrown " + e.getClass()
13 + " : " + e.getMessage() );
14 }
15 finally {
16 System.out.println ( " <- OK " );
17 }
18 }
19 }
20 static int divide( int dividend, int divisor )
21 throws Exception {
22 if( divisor == 0 )
23 throw new Exception( "divisor is zero" );
24 return dividend / divisor;
25 }
26 }
Figure 7: Simple exception handling.
6 / 0 = !! Thrown class java.lang.Exception : divisor is zero <- OK
6 / 1 = 6 <- OK
6 / 2 = 3 <- OK
6 / 3 = 2 <- OK
Figure 8: Output of DivideByZeroTest.
Just the same result (except for the exception class) will be obtained
if Exception in lines 11, 21, and 23 (Figure 7)
is replaced with its subclass ArithmeticException. Notice that you may throw
an instance of any subclass of the class specified in the throws
statement at line 21, but not vice versa, that is, you may not throw an
instance of a superclass. In other words, if the method divide()
throws either Exception or ArithmeticException,
then you may throw and catch an ArithmeticException
at lines 23 and 11, respectively. But, the Java compiler will fail if you
try to throw and catch an object from the superclass
Exception but define a method which throws only the
subclass ArithmeticException.
This example shows the following main code segments used in exception handling (see also Figure 9):
The whole try block is executed only if there is no exception. If the called method has thrown an exception then the exception is caught by the catch block and all the instructions both in the method after the point of throwing the exception and in the try block of the caller after the point of calling the method are omitted. But, the instructions in the finally block will be executed in any case, even if the exception is traced back to a higher level than the current caller (see Figures 10 and 11).
...
try {
... // code that is executes whether an
... // exception occurs or not
Method( ... ); // may throw an exception
... // code that executes only when no
... // exception event occurs
}
catch ( SubClassofParticularException e1 ) {
... // handle an exception event e1
... // identifier e1 can be used only in this block
}
catch ( ParticularException e2 ) {
... // handle an exception event e2
... // identifier e2 can be used only in this block
}
...
finally {
... // code that executes in all cases
}
...
static void Method( ... ) throws ParticularException {
... // code that executes in all cases
if( certainConditions )
throw new ParticularException( message );
... // code that executes only when an
... // exception event occurs
}
Figure 9: Structure of exception handling: an exception is thrown under certain conditions checked by a given method.
The example in Figure 12 handles simultaneously exceptions from the standard classes ArithmeticException and ArrayIndexOutOfBoundsException. These classes are independent in the hierarchy and occupy different levels with respect to their superclass RuntimeException. Output of this program is given in Figure 13. There are two exceptional cases in the computations:
Either method throws the corresponding standard exception which is caught correctly by the corresponding catch block.
1 class ExceptionTest {
2 public static void main( String [] args ) {
3 int [] result = new int [6];
4 for(int k = 0; k < 4; k++) {
5 System.out.println();
6 try {
7 System.out.println ( "k = " + k + ": ");
8 int indexResult = jokeFillResult( result, k );
9 System.out.println ("result[ " + indexResult +
10 "] =" + result[ indexResult ] );
11 }
12 catch ( ArithmeticException e1 ) {
13 System.out.println ( " !! Arithmetic Exception: "
14 + e1.getMessage() );
15 }
16 catch ( ArrayIndexOutOfBoundsException e2 ) {
17 System.out.println ( " !! Index Out Of Bounds: "
18 + e2.getMessage() );
19 }
20 finally {
21 System.out.println ( " <- OK " );
22 }
23 }
24 }
25 static int jokeFillResult( int [] array, int formIndex)
26 throws ArrayIndexOutOfBoundsException {
27 int index = divide ( array.length, formIndex );
28 array[ index ] = index;
29 return index;
30 }
31 static int divide( int dividend, int divisor )
32 throws ArithmeticException {
33 return dividend / divisor;
34 }
35 }
k = 0: !! Arithmetic Exception : / by zero <- OK k = 1: !! Index Out Of Bounds: 6 <- OK k = 2: result[ 3 ] = 3 <- OK k = 3: result[ 2 ] = 2 <- OK
Another way of handling exceptions, besides throwing a standard Exception with a proper String parameter, is to declare a new exception within your program and throw that. As mentioned before, it is desirable to define the new class as checked exception class which is a subclass of Exception but not a subclass of RuntimeException. Figure 14 shows such a definition and Figures 15 and 16 present an example of its usage.
1 class OwnException extends Exception {
2 OwnException() { super(); }
3 OwnException( String s ) { super( s ); }
4 }
11 class OwnExceptionTest {
12 public static void main( String [] args ) {
13 int [] result = new int [6];
14 for( int k = 0; k < 4; k++ ) {
15 System.out.println();
16 try {
17 System.out.println ( "k = " + k + ": ");
18 int indexResult = jokeFillResult( result, k );
19 System.out.println ("result[ " + indexResult +
20 "] =" + result[ indexResult ] );
21 }
22 catch ( OwnException e ) {
23 System.out.println ( e.getClass() + " : " +
24 + e.getMessage() );
25 }
26 finally {
27 System.out.println ( " <- OK " );
28 }
29 }
30 }
Figure 15: Example of using the exception class defined in Figure 14.
31 static int jokeFillResult( int[] array, int formIndex)
32 throws OwnException {
33 int index = 0;
34 try {
35 index = divide ( array.length, formIndex );
36 }
37 catch ( OwnException e ) {
38 throw e; // rethrow an exception up to a caller
39 }
40 if( index < 0 || index >= array.length )
41 throw new OwnException( " Index " + index +
42 " out of bounds!" );
43 array[ index ] = index;
44 return index;
45 }
46 static int divide( int dividend, int divisor )
47 throws OwnException {
48 if( divisor == 0 )
49 throw OwnException( " Divide by zero!" );
50 return dividend / divisor;
51 }
52 }
Figure 16: Example of using the exception class defined in Figure 14.
Notice that in this case it is you who are responsible for stating malfunction conditions in the methods involved. Conditions to throw the divide-by-zero exception are checked in line 48 of Figure 16 and the try - catch construction in lines 34-39 has to handle this exception at higher level. In this case, the method OwnExceptionTest.jokeFillResult() simply rethrows the exception up, to the main program. If necessary, you may use the method e.printStackTrace() for printing the stack trace for this user-defined exception.
If you run this example then you will see the output shown in Figure 17. You may replace line 37 by catch( Exception e) and still have the same behaviour of the program because Exception is a superclass of the defined checked class OwnException. But the Java compiler will not allow you to catch an improper class, say, catch (RuntimeException e ) at line 37! Figure 18 displays the corresponding error message from the Java Language Compiler. This is the immediate result of defining our exception class OwnException as the checked one. Now it is the compiler that checks if you handle properly the defined exceptions.
k = 0: class OwnException : Divide by zero! <- OK k = 1: class OwnException : Index 6 out of bounds <- OK k = 2: result[ 3 ] = 3 <- OK k = 3: result[ 2 ] = 2 <- OK
OwnExceptionTest.java:37:
Class RuntimeException not found in type declaration.
catch ( RuntimeException e ) {
^
You will see later, in Section 6, that for implementing a binary tree search in Java you will have to define and use two new own exceptions: ``ItemNotFound'' indicating an unsuccessful search and ``DuplicateItem'' indicating that an item you try to insert into a tree is already present there (see Figure 19).
1 class ItemNotFound extends Exception {
2 ItemNotFound() { super(); }
3 ItemNotFound( String s ) { super( s ); }
4 }
5
6 class DuplicateItem extends Exception {
7 DuplicateItem() { super(); }
8 DuplicateItem( String s ) { super( s ); }
9 }
Figure 19: User-defined exception classes for a binary tree search in Section 6.
Exceptions in Java are objects and all exception types must extend the Java language class Throwable or one of its subclasses. The Throwable class contains a string that can be used to describe the exception. By convention, new exception types extend the subclass Exception of Throwable.
All Java exceptions, except for standard runtime exceptions and errors, are primarily checked exceptions. In other words, the compiler checks that your methods throw exceptions they have declared themselves to throw. Therefore, all exceptions you create should extend Exception, making them checked exceptions. Standard runtime exceptions and errors extend the classes RuntimeException and Error, creating unchecked exceptions.
Sometimes you need more data for describing the exceptional condition than just the string that Exception provides. In such cases, it is possible to extend Exception in such a manner as to create a class that contains the added data (usually set in the constructor). You will find more details in Chapter 7 of K. Arnold and J. Gosling, "The Java\sc TM Programming Language", pp.134-136.
As you have seen above, the first thing in the method is a declaration stating which checked exceptions it throws. Java requires the declaration of the checked exceptions that methods throw, because programmers invoking a method need to know the exceptions it can throw just as much as they need to know its normal behaviour. These exceptions are declared with a throws clause, which takes a comma-separated list of exception types.
A method may throw several different classes of exceptions that all are extensions of a particular exception class, and declare only the superclass in the throws clause. However, by doing so you hide potentially useful information from programmers invoking the method. The throws clause should be as complete and specific as possible!
Notice that you can throw only a type of exception that has been declared in the throws clause. Throwing any other type of exception is invalid. If a method has no throws clause, it means no exceptions may be thrown (except RuntimeExceptions and subclasses of this).
Java is strict about enforcing checked exception handling because this helps avoid bugs that come from not dealing with errors. If you invoke a method that lists a checked exception in its throws clause, you have three choices:
Several examples of catching exceptions were presented above. You must be careful in choosing the order of catch clauses associated with a particular try. Because the catch clauses are examined in order, a catch that picks up one exception type before a catch for an extended type of exception is a mistake. The first clause would always catch the exception, and the second clause would never be reached. For this reason, putting a superclass catch clause before a catch of one of its subclasses is a compile-time error:
class SubException extends Exception{ }
class SubSubException extends SubException{ }
class BadCatch {
public void doSomething() {
try {
throw new SubSubException();
}
catch ( SubException se ) {
// Catches both SuperException and SubException
}
catch ( SubSubException sse ) {
// This will never be reached
}
}
}
Only one exception is handled in any single execution of a try clause. If a catch or finally clause throws another exception, the catch clauses of the try are not reexamined. The catch and finally clauses are outside the protection of the try clause itself. Such exceptions can, of course, be handled by any encompassing try clock in which the inner catch or finally clauses are nested:
try {
... // some "outer" block
try {
... // some "inner" block
... // that throws InnerException
}
catch ( InnerException ein ) {
... // processing the exception caught
throw new OuterException();
}
}
catch ( OuterException e ) {
... // processing the exception caught
}
Exception handling has to be used only for dealing with unexpected error conditions. Exceptions are not meant for simple, expected situations (although we use them above to illustrate exceptions). For instance, reaching the end of a file is expected so that it is better to use simply some return code indicating end-of-input. But, continuing to read past an end-of-file is not expected, and this is an excellent case for a ReadPastEndException. Such behaviour is outside the expected use of your file class, and throwing an exception is the right way to handle it.
Of course, deciding which situations are expected and which are not is a fuzzy area. But, the point is to use exceptions only in really exceptional situations and not to abuse exceptions as a way of reporting expected situations.
In many cases, if your program tries to set an array size to a negative value or searches for a programmer-specified word in a string array and cannot find any occurrence of the word, you can, but need not, involve the exception mechanism. Of course, the preceding is true if these situations are absolutely predictable and can be taken into account directly in the processing method or in its return value. Otherwise, you must use an appropriate exception.
Also, you cannot expect that a file provided to an "open" method does not exist, or that it exists, but security prevents the user from using it, or that the remote machine cannot be contacted during an attempt to open a network connection to a remote server process, or that the network connection stops operating just in the middle of a conversation with a remote server process, or so on. Such unexpected events can be handled most effectively by throwing and catching exceptions.
When you run and then terminate a program any data stored in a computer main memory is lost. For long-term data storing, you must use secondary, or peripheral devices such as magnetic tapes, magnetic disks, or optical disks. Here, large amounts of data are organised in files with specific names and internal structures. In particular, the operating system of your PC and other software you use consists of many different files.
File processing is a most important part of any commercial, industrial, or scientific application which has to deal with a large number of data items. Thus, each programming language has to support such applications with adequate powerful and versatile input and output tools. Below, we will deal mostly with ``ordinary'' text files, or stream files. A text file consists of a long sequence of characters - letters, numbers, and special symbols. Other file types will be met in later courses.
Notice that only Java applications are allowed to input and output data files.
This is a default Java feature which is quite justified: would you be pleased if some ``alien'' applet that came to you via Internet start reading and rewriting your files? It is possible to relax the default limitations but just now let us restrict the file processing only to Java applications.
Java views each file simply as a sequential stream of bytes:
|
which ends with an end-of-file (EOF) marker. Alternatively, a file may end at a specific byte number specified by an operating system. This byte stream may support a specific hierarchy of data items to be processed, for instance, a bottom-up hierarchy of items such as
For instance, a Java program stored in a file with the extension .java has text lines as records and words as fields. A line in Java character stream is considered to be terminated by any one of a line feed ('\n'), a carriage return ('\r'), or a carriage return followed immediately by a line feed ('\r\n').
To perform data stream processing in Java, the standard package java.io must be imported. This package includes definitions of stream classes for getting data from a stream and for putting data to a stream. Notice that a file is but one possible source for data. You may acquire data from other sources such as the keyboard, a socket on the network, elements of an array or String, and so on. Thus, a Stream in Java could be getting its bytes from or sending them to a file, a String, etc. (see Figure 20).
Previous versions 1.0.* of Java have supported only byte streams, via the abstract classes InputStream and OutputStream and their subclasses. The Java API, version 1.1.1 and higher, introduces support for character streams to the java.io package. Character streams are like byte streams, but they contain 16-bit Unicode characters rather than 8-bit bytes. They are implemented by the Reader and Writer abstract classes and their subclasses. Readers and Writers support essentially the same operations as InputStreams and OutputStreams, except that where byte-stream methods operate on bytes or byte arrays, character-stream methods operate on characters, character arrays, or strings.
Most of the functionality available for byte streams is also provided for character streams. This is reflected in the name of each character-stream class, whose prefix is usually shared with the name of the corresponding byte-stream class. Table 1 summarizes the character-stream classes (in the left column, an indentation indicates subclass relationships) and Table 2 shows correspondences between the character- and byte-stream classes.
Note that most files are byte-based; in particular, any file you can access with a normal word processor, or the program editor. Character-based files are of no use outside Java, at present.
An InputStreamReader serves as a bridge from byte streams to character streams; it reads bytes and translates them into characters according to a specified character encoding. The encoding may be specified by name, or the platform's default encoding may be accepted. For ASCII, it will simply put the byte in the low-order byte of the character, and set the other byte to 0. Only if non-ASCII characters are used (e.g., Chinese) will a different encoding be used. Each invocation of one of the read() methods of this class causes one or more bytes to be read from the underlying byte-input stream. For top efficiency, you may wrap an InputStreamReader by a BufferedReader, for example,
BufferedReader in =
new BufferedReader( new InputStreamReader( System.in ) );
When a file is opened, an object of a steam class is created and a stream is associated with the object. The classes FileReader and FileWriter are derived, that is, inherit the functionality of classes InputStreamReader and OutputStreamWriter, respectively. Generally, to get the exact processing you want it is necessary to connect various streams. In particular, the FileInputStream in Figure 21 allows the reading of byte arrays from a given file specified by its name (of String type). But, to read data items such as characters, integer or float numbers, and so on, it must be connected to a DataInputStream. For instance, the following code constructs a DataInputStream from a FileInputStream and then reads integer values from the file (in this case, each successive 4 bytes are interpreted as one int number):
FileInputStream fis;
DataInputStream dis;
try{
fis = new FileInputStream( fileName );
dis = new DataInputStream( fis );
int i;
while( true ) {
i = dis.readInt();
}
} catch (EOFException eof) { ... }
catch ( IOException ioe) { ... }
For an extended discussion see the next sections.
Figure 21: Connecting streams to get the desired
processing.
| Character-stream class |
Extends |
Description |
| Reader | java.lang.Object | Abstract class for character-input streams |
| BufferedReader | Reader | Buffers input, parses lines |
| LineNumberReader | BufferedReader | Keeps track of line numbers |
| CharArrayReader | Reader | Reads from a character array |
| InputStreamReader | Reader | Translates a byte stream into a character stream |
| FileReader | InputStreamReader | Translates bytes from a file into a character stream |
| FilterReader | Reader | Abstract class for filtered character input |
| PushBackReader | FilterReader | Allows characters to be pushed back to the stream |
| PipedReader | Reader | Reads piped streams from a PipedWriter |
| StringReader | Reader | Reads from a String |
| Writer | java.lang.Object | Abstract class for character-output streams |
| BufferedWriter | Writer | Buffers output, uses platform's line separator |
| CharArrayWriter | Writer | Writes to a character array |
| OutputStreamWriter | Writer | Translates a character stream into a byte stream |
| FileWriter | OutputStreamWriter | Translates a character stream into a byte file |
| PipedWriter | Writer | Writes piped streams to a PipedReader |
| PrintWriter | Writer | Prints values and objects to a Writer |
| StringWriter | Writer | Writes to a String |
Table 2: Corresponding character- and byte-stream classes in the java.io package.
| Character-stream class | Byte-stream class | Extends |
| Reader | InputStream | java.lang.Object |
| BufferedReader | BufferedInputStream | FilterInputStream |
| LineNumberReader | LineNumberInputStream | Deprecated! |
| CharArrayReader | ByteArrayInputStream | InputStream |
| InputStreamReader | (none) | (none) |
| FileReader | FileInputStream | InputStream |
| FilterReader | FilterReader | InputStream |
| PushBackReader | PushBackInputStream | FilterInputStream |
| PipedReader | PipedInputStream | InputStream |
| StringReader | StringBufferInputStream | Deprecated! |
| Writer | OutputStream | java.lang.Object |
| BufferedWriter | BufferedOutputStream | FilterOutputStream |
| CharArrayWriter | ByteArrayOutputStream | OutputStream |
| OutputStreamWriter | (none) | (none) |
| FileWriter | FileOutputStream | OutputStream |
| PipedWriter | PipedOutputStream | OutputStream |
| PrintWriter | PrintStream | FilterOutputStream |
| StringWriter | (none) | (none) |
This public abstract class, extending the Object class, is the base class of most input character streams in java.io and declares methods for reading these streams. It has a non-argument constructor Reader() and supports, in particular, the following methods:
The method should be invoked to release any resources (such as file descriptors) associated with the stream. If this method is not invoked, associated reources remain in use, at least, until the garbage collector gets around to running a stream's finalize method.
The only methods that a subclass of Reader must implement are read(char[], int, int) and close(). Most subclasses, however, will override some of the above methods in order to provide higher efficiency, additional functionality, or both.
This public abstract class, extending Object, is the base class of most output character streams in java.io and declares methods for writing these streams. It has a non-argument constructor Writer() and supports, in particular, the following methods:
The only methods that a subclass of Writer must implement are write(char[], int, int), flush(), and close(). Most subclasses, however, will override some of the above methods in order to provide higher efficiency, additional functionality, or both.
Note that the method flush() is very important. Characters are never written directly to a file, but are stored in the computer's memory until there are enough to justify writing. If the power fails, stored characters will be lost. Flushing is used to ensure that vital data is actually saved on the file, by forcing the computer to write all stored character onto the file.
The java.io package define many types of streams and here we will list some of them. Notice, that the stream types usually have I/O pairs:
In particular, the abstract class Reader contains the following subclasses (see, also, Tables 1 and 2):
In general, each read request made of a Reader causes a corresponding read request to be made of the underlying character or byte stream. It is therefore advisable to wrap a BufferedReader around any Reader whose read() operations may be costly, such as FileReaders and InputStreamReaders. For example,
BufferedReader in = new BufferedReader(new FileReader( "filename" ));
will buffer the input from the specified file. Without buffering, each invocation of read() or readLine() could cause bytes to be read from the file, converted into characters, and then returned, which can be very inefficient.
Notice that you may wrap in a similar way a BufferedWriter around a Writer, say,
BufferedWriter out = new BufferedWriter(new FileWriter( "filename" ));
Programs that use DataInputStreams for textual input can be localized by replacing each DataInputStream with an appropriate BufferedReader.
There are three major steps in reading or writing files:
In order to input data from a file or to output data to a file, you need to find this file in a storage device, most frequently, on a computer disk, using its unique complete file name, or disk name. The complete name points out where the file is placed within an existing directory tree. The complete name is formed by the file name preceded by names of all the folders/directories containing this file, for instance,
c:/jdk1.1.4/MyPrograms/FileProcessing/SimpleText.txt
Java has standardised on / as the separator regardless of the operating system (the separator is \ in IBM PCs, / in Unix, : in Macs).
We consider a simple example of locating, reading, and printing the following text file SimpleText.txt containing two lines (created in a some way other than a Java program, so the file is a byte file):
Simple text file containing 2 text lines:
1234567890 qwertyuiopasdfghjklzxcvbnm !@#
$%^&*()_+-={}[]|\:";'<>?,./ =============.
The application class FileProcessing that locates, reads, and prints a text file is shown in Figure 22. To locate files, it uses a search window created by the public class FileView in Figure 23. Below, this example is analysed in detail.
For compiling this application, the file FileProcessing.java that contains the class FileProcessing has to be placed in the (sub)directory ...\FileProcessing. The file FileView.java containing the package FileView with the class FileView must be in the subdirectory ...FileProcessing\FileView.
1 import java.io.*;
2 // note that FileView.class must be present in the same folder
3
4 class FileProcessing {
5 public static void main( String [] args ) {
6 try{
7 String fileName = FileView.getName();
8 System.out.println("Chosen file: " + fileName);
9 BufferedReader textFile =
10 new BufferedReader( new FileReader( fileName) );
11 System.out.println( "The contents of " + fileName + " is:");
12 System.out.println();
13 while( true )
14 {
15 int byteRead = textFile.read();
16 if ( byteRead == -1 ) break;
17 System.out.print( (char) byteRead );
18 }
19 System.out.println( "\r*** End of file ***" );
20 textFile.close();
21 }
22 catch( IOException excio ) {
23 System.out.println( "IO exception: "
24 + excio.getClass() + " : " + excio.getMessage() );
25 }
26 }
27 }
Figure 22: Simple program that locates, reads, and prints a text file.
28
29 import java.awt.*;
30
31 public class FileView{
32 public static String getName() {
33 FileDialog fd =
34 new FileDialog( new Frame (), "Find A File To Process");
35 fd.setDirectory(".");
36 fd.show();
37 String fileName = fd.getFile();
38 String fileDirectory = fd.getDirectory();
39 return fileDirectory + fileName;
40 }
41 }
Figure 23: Class FileView forming a search window for locating a file.
Lines 1-5. The application FileProcessing imports the standard Java input/output classes from the package java.io
Lines 6, 21-25. The try - catch construction is used in this program because file readers throw exceptions from the IOException class which is checked by Java compilers. The program gets and prints a class of an exception ioexc caught, by using the method getClass(), and a message sent by this exception, by using the method getMessage(). Of course, in this simple example you have not to be afraid of a run-time crash. Thus, you may simplify the program if just put throws IOException on the main program and avoid the try/catch construction.
Lines 7-8 The program gets the complete file name using a search window created by class FileView in Figure 23, and prints it in the working Java window.
return fileDirectory + File.separator + fileName
to show explicitly the file separator. But, it is not necessary because the name fileDirectory comes with a corresponding separator at the end.
Lines 9-10. Once you get the complete file name, you have to instantiate the appropriate object which will hold information in computer memory about the file. Note that the file itself never comes into the memory unless we read it. This process of obtaining information about a file is called opening the file.
In this example, the program creates a new object textFile from the class Buffered Reader which is constructed from the class FileReader. The byte stream being read from the file with the complete disk name fileName is translated to the character stream by FileReader and then is associated with the BufferedReader object textFile. The class BufferedReader allows the reading of text from a character-input stream, buffering characters so as to provide for the efficient reading of characters, character arrays, and lines. This program uses the default buffer size which is large enough for most purposes, but you may specify another size, too, if necessary.
Note that we are instantiating two objects at the same time here. We do not need the FileReader object later, so we do not introduce a variable which references it. Such a ``double'' instantiation will be used below in most of our examples.
Generally, each read request made of Reader causes a corresponding read request to be made of the underlying character or byte stream. Java's documentation, therefore, advises you to wrap a BufferedReader around any Reader whose read() operations may be costly, such as FileReaders and InputStreamReaders. This advise is used in the program in lines 9-10. In this case, the created object buffers the input from the specified file. Without buffering, each invocation of read() in line 15 could cause bytes to be read, converted into characters, and then returned, which can be very inefficient.
Lines 13-18. This while-loop reads successive bytes from the file. The method read() returns an int value of either the current single byte being read or -1 when the EOF marker is encountered. The characters occupy only the two least significant bytes of the int value so that the int EOF marker differs from the integer value returned for the character value -1. The top bytes of the int -1 will be full of 1 bits, not 0 bits as they are with any character value. Thus, the program can always tell when the end of file has been reached.
In the case of a null file name, the program catches the IOException and prints the following message:
Chosen file: .null IO exception: class java.io.FileNotFoundException : .null
If the above-mentioned file SimpleText.txt is located then the program prints as follows:
Chosen file: C:\jdk1.1.4\myprogs\FileProcessing\SimpleText.txt
The contents of C:\jdk1.1.4\myprogs\FileProcessing\SimpleText.txt is:
1234567890 qwertyuiopasdfghjklzxcvbnm !@#
$%^&*()_+-={}[]|\:";'<>?,./ =============
*** End of file ***
By the way, it is the casting (char) in line 17 that allows the printing of the characters read. If you remove it:
17 System.out.print( byteRead );
the resulting output for the same file SimpleText.txt will be slightly disappointing:
Chosen file: C:\jdk1.1.4\myprogs\FileProcessing\SimpleText.txt The contents of C:\jdk1.1.4\myprogs\FileProcessing\SimpleText.txt is: 4950515253545556574832113119101114116121117... *** End of file ***
To understand this more in details, you may replace line 17 as follows:
17 if( byteRead == (int)'\n' ||
byteRead == (int)'\r') System.out.print( "\r");
System.out.print( byteRead + "," );
and look at the resulting output:
Chosen file: C:\jdk1.1.4\myprogs\FileProcessing\SimpleText.txt The contents of C:\jdk1.1.4\myprogs\FileProcessing\SimpleText.txt is: 49,50,51,52,53,54,55,56,57,48,32,113,119,101,114,116,121,117,... 13, 10,36,37,94,38,42,40,41,95,43,45,61,123,125,91,93,124,92,58,34,59,... *** End of file ***
Now, it is easily seen that the output gives simply the ASCII codes for the characters read (these codes coincide with the Unicode encoding). In particular, 113 is the code for q, 119 is the code for w, 101 is the code for e, 114 is the code for r, and so on. The codes 13 (the carriage return \r) and 10 (the line feed \n) indicate the end of line to break the text into lines in any text editor or during printing (note that this was a DOS file -- Mac text files just have \verb+\r+, character $13$, at the end of lines). But, really, the file is just a continuous sequence of bytes.
Line 20. If you omit the call to close(*), then your file will be closed automatically when the program terminates. But, it is better programming style to always specifically close a file when you have finished using it.
The program in Figure 25 counts the total number of characters and the number of white-space characters in a byte-stream text file containing 8-bit ISO-Latin-1 (that is, ordinary ASCII) characters. This program either takes a filename from the command line:
> java CountSpace SimpleText.txt
or reads characters from its standard input stream, System.in.
Lines 10, 14-15. If the filename is not provided, an InputStreamReader object is created to read from the standard input stream (usually, from the keyboard). If one is provided, an InputStreamReader object is constructed on a FileInputStream object which is an extension of InputStream.
Lines 20-25. The for-loop counts the total number of bytes in the file, and the number of spaces, using the Character class's isWhitespace() and isISOControl() methods. The former method tests which characters arec white space and the latter one allows to detect the end of the input from the standard System.in stream (when you press the key enter).
At the end, the results are printed. If the program is used on itself
> java CountSpace CountSpace.java
then the output is as follows:
758 chars, 281 spaces
Note that this program (as well as other ones) has been tested on an IBM PS and on a Unix-based SGI O2 workstation. You should find if this works on a Mac.
1 import java.io.*;
2
3 class CountSpace {
4 public static void main( String[] args )
5 throws IOException {
6 boolean kbInput;
7 InputStreamReader in;
8 if( args.length == 0 ) {
9 kbInput = true;
10 in = new InputStreamReader( System.in );
11 }
12 else {
13 kbInput = false;
14 in = new InputStreamReader(
15 new FileInputStream( args[0] ) );
16 }
17 int ch;
18 int total;
19 int spaces = 0;
20 for( total = 0; ( ch = in.read() ) != -1; total++ ) {
21 if( kbInput && Character.isISOControl( (char)ch ) )
22 break;
23 if( Character.isWhitespace( (char)ch ) )
24 spaces++;
25 }
26 System.out.println( total + " chars, " +
27 spaces + " spaces" );
28 }
29 }
Figure 25: Simple program that counts characters and white spaces.
Usually, we consider a text file as a collection of text lines even though, as pointed out above, it is a continuous chain of bytes. Therefore, it is often useful to read such a file line by line to process each line independently. This can be done by a standard method readLine() of class java.io.BufferedReader:
public String readLine() throws IOException
which reads a line of text and returns a String containing the contents of the line without any line-termination characters \n, \r, or \r\n. It returns null if there is nothing to read but the end of file and throws an IOException if an I/O error occurs. Several basic methods of the BufferedReader class are presented in Table 3.
Table 3: Basic methods from the public class BufferedReader.
| Method | Description |
| void close() | Close the stream |
| int read() | Read a single character |
| String readLine() | Read a line of text |
| boolean ready() | Tells whether this stream is ready to be read |
| long skip( long n ) | Skip n characters |
Figure 26 shows a simple program that reads text files line by line. Notice that it differs from the program in Figure 22 mainly in lines 13-15 which replace previous lines 15-17 and yield the desired reading mode. The method readLine() in line 13 returns a String result which is the current text line being read from the file. The end-of-line characters are not included in the returned string line.
1 import java.io.*;
2 // Note that FileView.class must be present in the same folder
3
4 class ReadLineTest {
5 public static void main ( String [] args ) {
6 try {
7 String fileName = FileView.getName();
8 BufferedReader textFile =
9 new BufferedReader( new FileReader ( fileName ) );
10 System.out.println("The contents of "+ fileName +" is:");
11 System.out.println();
12 while ( true ) {
13 String line = textFile.readLine();
14 if ( line == null ) break; // The null reference!
15 System.out.println ( line );
16 }
17 System.out.println( "*** End of file ***" );
18 textFile.close();
19 }
20 catch( IOException excio ) {
21 System.out.println( "IO exception: "
22 + excio.getClass() + " : " + excio.getMessage() );
23 }
24 }
25 }
The method readLine() returns a null reference when the end of the file has been reached. Notice that this is NOT an empty string "" which you get by reading a ``blank'' text line.
If the above file SimpleText.txt is located by the program ReadLineTest then the resulting printout is almost the same as for the program FileProcessing:
The contents of C:\jdk1.1.4\myprogs\FileProcessing\SimpleText.txt is:
1234567890 qwertyuiopasdfghjklzxcvbnm !@#
$%^&*()_+-={}[]|\:";'<>?,./ =============
*** End of file ***
The ``*** End of file ***'' is printing on the next line after the last line read because of the println() method. It displays the text lines by supplying the line ends implicitly so that there is no way of telling if the last line in our file has a line end or not. Note that in Figure 22, line 19, the line end is to be inserted explicitly because the print() method displays only characters and the last line in the file SimpleText.txt has really no line end.
The program in Figure 27 illustrates both reading and writing a text file because it simply copies one text file to another. This program locates the input and output files by the same FileView search window as above (lines 8-9).
1 import java.io.*;
2 // Note that FileView.class must be present in this folder
3
4 class CopyFile
5 {
6 static final int BUFFERSIZE = 1024;
7 public static void main( String [] args ) throws IOException {
8 String inFileName = FileView.getName();
9 String outFileName = FileView.getName();
10 copyFile( inFileName, outFileName );
11 }
12 public static void copyFile( String nameIn, String nameOut )
13 throws IOException {
14 BufferedReader input = new BufferedReader(
15 new FileReader ( nameIn ) );
16 BufferedWriter output = new BufferedWriter(
17 new FileWriter ( nameOut ) );
18 char [] buffer = new char [ BUFFERSIZE ];
19 while ( true ) {
20 int nbrRead = input.read( buffer, 0, buffer.length );
21 if ( nbrRead < 0 ) break;
22 output.write( buffer, 0, nbrRead );
23 }
24 input.close();
25 output.close();
26 }
27 }
The method copyFile(), given by lines 12-26, constructs an input buffered file reader to read from a file with a specified name (lines 14-15) and an output buffered file reader to write a file with a specified name (lines 16-17). Notice that f if you supply the name of an output file that already exists, the file will be overwritten!
The program uses an own buffer (see lines 6 and 18) but this is not necessary because of using the buffered reader and writer (so, it is almost just the same if you read and write single characters). The method int read( char buffer[], int off, int len) of class BufferedReader reads up to len characters translated from the bytes of an input file by a FileReader. The method blocks until some input is available. It returns the total number of bytes read into the buffer (here, nbrRead value), or -1 if the end of the file has been reached and there is no more data. In the latter case, the program breaks the while-loop of reading and writing, closes both the files (lines 24-25) and exits. The method void write( char buffer[], int off, int len) of class BufferedWriter writes len bytes from the specified character array, starting at offset off to the output file. Both the read and write methods throw an IOException if an i/o error occurs.
In many scientific applications you need to read text files which contain only numbers (as strings) separated by space characters. The end-of-lines are not significant and possibly may be absent. The number itself may be unsigned or signed integer or real, for example, 10, -235, 35.765, or -19.399. Some data files may be quite long, say, several Gigabytes! In Java, the easiest way of reading such large files is to use the StreamTokenizer class.
This class takes an input stream and parses it into ``tokens'' ignoring completely end-of-line characters. The tokens can be read one at time and converted to numbers if desired. Identifiers, numbers, quoted strings, and various comment styles of C and C++ can be recognised. The basic data fields of this class are as follows:
StreamTokenizer class contains the following methods for processing the stream:
|
has the ``numeric'' attribute. When a word token encountered has the format of a double precision floating-point number, it is treated as a number rather than a word. The ttype field is set to the value TT_NUMBER and the numerical value of the token is put into the nval field. Note that a dot (.) is treated as a number - if it has no digits next to it, the value of the number is 0.
Figure 28 show a program ReadNumbers which reads numbers from a text file using the StreamTokenizer.
1 import java.io.*;
2 // Note that FileView.class must be present in this folder
3
4 class ReadNumbers {
5 public static void main ( String [] args )
6 throws IOException {
7 String fileName = FileView.getName();
8 StreamTokenizer getNumbers =
9 new StreamTokenizer( new FileReader ( fileName ) );
10 getNumbers.parseNumbers();
11 while ( true ) {
12 try {
13 int returnValue = getNumbers.nextToken();
14 if( returnValue == StreamTokenizer.TT_EOF ) break;
15 if( returnValue != StreamTokenizer.TT_NUMBER )
16 throw new IOException ( "Non-number in file" );
17 processNumber( getNumbers.nval );
18 }
19 catch( IOException excio ) {
20 System.out.println( "Out: IO exception: "
21 + excio.getClass() + " : " + excio.getMessage() );
22 }
23 }
24 System.out.println( "*** End of file ***" );
25 }
26 static void processNumber( double number ) {
27 System.out.println("Out: " + number );
28 }
29 }
Lines 8-9. Notice that the constructor StreamTokenizer(InputStream) is deprecated in Java version 1.1 so that you have to create a tokenizer that parses the given character stream using the StreamTokenizer(Reader) constructor.
Line 10. This method call sets the StreamTokenizer up to look for numbers and convert them from strings. Otherwise it will treat everything as words. It is possible to set the StreamTokenizer up for working as a StringTokenizer and presenting the individual words with a special treatment for punctuation. You will find details in the Java documentation.
Lines 13-16. The method newToken() returns an int value of the ttype field describing the token. Here, we take into account only two values: TT_EOF, indicating that the end of the file is reached, and TT_NUMBER, indicating that a string which is a valid number is found and converted to the double value in the field nval.
Line 17, 26-28. The number which was found, converted, and stored in the instance variable nval of the StreamTokenizer, of type double, may be used for a subsequent data processing. Here, we just print it. The numbers are converted to double precision floating-point values, presumably, to obtain maximum compatibility using the least number of instance variables (fields).
Below, three examples of reading text files are presented. The first file to be read, Numbers.txt, contains the following five integers:
10 232 45675 1939 803123
The program reads these number tokens and prints them out as the double-precision floating-point values:
Out: 10.0 Out: 232.0 Out: 45675.0 Out: 1939.0 Out: 803123.0 *** End of file ***
Of course, the input file may contain floating-point number tokens as in the following file Nufloat.txt:
10.54 232.5 45675 .1939 0.803123 1000.32176
This file produces the output (notice that integer and floating-point number tokens are both converted to double precision floating-point values):
Out: 10.54 Out: 232.5 Out: 45675.0 Out: 0.1939 Out: 0.803123 Out: 1000.32176 *** End of file ***
When the input text file Nonumbs.txt contains both number and word tokens:
First 232 45675 1939 Second 803123 1000Mix321ed76
the program throws a new IOException with an user-specified message (see line 16 in Figure 28). The resulting output is as follows:
Out: IO exception: class java.io.IOException : Non-number in file Out: 232.0 Out: 45675.0 Out: 1939.0 Out: IO exception: class java.io.IOException : Non-number in file Out: 803123.0 Out: 1000.0 Out: IO exception: class java.io.IOException : Non-number in file *** End of file ***
Notice that if the word token immediately follows a valid number, this number (here, 1000) is parsed as an individual number token.
Frequently you will need to transmit data of specific types across a stream because character representation of numerical data increases the length of data files markedly. This is because you need at least one byte per digit (or 2 bytes per digit when using the ISO Unicode character set) to represent a number. Also, there must be ``space'' characters to separate successive tokens, and you may need the ``sign'' characters (+ and -) and the ``dot'' character (.) to be used in representing numbers. For instance, the file
-1067899908 -2127897345 +1567509877 +1939899884 -1803123788
contains 59 characters including spaces and signs and occupies 118 bytes in a character stream, but as a set of int values it would occupy only 20 bytes. The larger the range of data values, the longer the ``textual'' representation. Table 4 gives the sizes of the primitive numerical data types in Java used as blocks for building more complicated data types.
| Type | Size
in bytes |
Range of values | Digits per
number |
| byte |
1 |
-128 ... +127 | < 4 |
| short |
2 |
-32,768 ... +32,767 | < 6 |
| int |
4 |
-2,147,483,648 ...
+2,147,483,647 |
< 11 |
| long |
8 |
-9,223,372,036,854,775,808 ...
+9,223,372,036,854,775,807 |
< 20 |
| float |
4 |
-3.40292347E+38 ...
+3.40292347E+38 |
< 15 |
| double |
8 |
-1.79769313486231570E+308 ...
+1.79769313486231570E+308 |
< 25 |
To reduce the length of a file, you may write and read primitive data types. The java.io.DataOutput and java.io.DataInput interfaces define methods to transmit Java primitive types across a stream. A default implementation of each interface is provided by the java.io.DataOutputStream and java.io.DataInputStream classes. A data output stream allows an application to write primitive Java data types to an output stream in a portable machine-independent manner. An application can then use a data input stream to read the data back in.
The interfaces for data input and output are almost mirror images. Table 5 shows the parallel read and write methods for each type. Notice that UTF is "UCS Transformation Format", or an interim 1-3 byte code to operate with both ASCII and Unicode (UCS is the "Universal Character Set"). Unicode characters are transmitted in Unicode-1-1-UTF-8, which is a compact binary form designed to encode 16-bit Unicode characters in 8-bit bytes. The method readUTF() reads in a string and the method writeUTF() writes from a string that has been encoded using a slightly modified format UTF-8.
| Type | Read | Write |
| boolean | readBoolean | writeBoolean |
| char | readChar | writeChar |
| byte | readByte | writeByte |
| short | readShort | writeShort |
| int | readInt | writeInt |
| long | readLong | writeLong |
| float | readFloat | writeFloat |
| double | readDouble | writeDouble |
| String | readUTF | writeUTF |
In addition to these paired methods, there are a few specific DataInput methods for reading bytes into a given buffer (readFully( byte[] buffer ), for reading bytes into a buffer, starting at offset position off and continuing until either len bytes are read or the end of buffer is reached (readFully( byte[] buffer, int off, int len), for skipping n bytes (skip( int n )), etc. The DataOutput interface additionally provides methods for writing a String as a sequence of bytes (writeBytes( String s )) or as a sequence of characters (writeChars( String s )). Reading back strings written by these latter methods must be done using a loop on readChar, since there is no method to read back the same number of characters written by the invocation of writeBytes or writeChars.
For each Data interface there is a corresponding Data stream. Each Data class is an extension of its Filter class, so Data streams can be used to filter other streams. The filtering can be used, for example, to write data to a file by putting a DataOutputStream in front of a FileOutputStream object, and then read it back in by putting a DataInputStream in front of a FileInputStream object.
In addition, the RandomAccessFile class implements both the input and output Data interfaces and can be used to read and write built-in Java data types. This class provides a more sophisticated file processing mechanism than File streams. The "random access" referred to in the name of the class is the ability to set the read/write file pointer to any position in the file and then perform the operation.
1 import java.io.*;
2
3 class ReadData {
4 public static void main( String[] a ) throws IOException{
5 String EOFException = "java.io.EOFException";
6 int[] arInt= {10, 5, 567, 43, 1238};
7 double[] arDouble= {10.0, 5.23, 567.87, 43.77, 1238.8765};
8 String fileName = "test.dat";
9 DataOutputStream putData =
10 new DataOutputStream ( new FileOutputStream (fileName) );
11 for(int k = 0; k < arInt.length; k++ ) {
12 putData.writeInt( arInt[ k ] );
13 putData.writeDouble( arDouble[ k ] );
14 }
15 putData.close();
16 DataInputStream getData =
17 new DataInputStream( new FileInputStream ( fileName ) );
18 System.out.println( "Correct reading: data file "+fileName );
19 while ( true ) {
20 try {
21 int intRead = getData.readInt();
22 double doubleRead = getData.readDouble();
23 System.out.println( "Int: " + intRead +
24 "; Double: " + doubleRead );
25 }
26 catch (EOFException e ) { break; }
27 catch (IOException e ) { throw e; }
28 }
29 System.out.println( "*** End of file ***" );
30 getData.close();
Figure 29: Simple program that writes and reads a data file (part 1).
31 System.out.println( "\nIncorrect reading" );
32 DataInputStream getWrongData =
33 new DataInputStream( new FileInputStream ( fileName ) );
34 while ( true ) {
35 try {
36 double doubleRead = getWrongData.readDouble();
37 int intRead = getWrongData.readInt();
38 System.out.println( "Wr.double: " + doubleRead +
39 "; wr.int: " + intRead );
40 }
41 catch (EOFException e ) { break; }
42 catch (IOException e ) { throw e; }
43 }
44 System.out.println( "*** End of file ***" );
45 getWrongData.close();
46 }
47 }
Figure 30: Simple program that writes and reads a data file (part 2).
Figures 29 and 30 present a simple program which creates first a data file and then reads it. The created data file test.dat contains numbers of two Java primitive types int and double which are interleaved as follows:
| 10 | 10.0 | 5 | 5.23 | 567 | 567.87 | 43 | 43.77 | 1238 | 1238.8765 |
Below, the program is considered in detail.
Lines 9-10. The constructor DataOutputStream creates a
new data output stream putData to write data to the specified
underlying output stream. Here, the underlying output stream is a FileOutputStream
for writing data either to a file with the specified system-dependent name,
or to the specified File object, or to the specified file descriptor.
Lines 11-14. This loop writes the above data file using the method writeInt() to output an int value and the method writeDouble() to output a double value. The class DataOutputStream contains many different methods for writing Java primitive data types, in particular, writeByte(), writeChar(), writeFloat(), writeLong(), etc.
Line 15. The method close() from class FileOutputStream closes this file output stream and releases any system resources associated with this stream.
Lines 16-17. The constructor DataInputStream creates a new data input stream getData to read data from the specified underlying input stream. Here, the underlying input stream is a FileInputStream for reading data either from a file with the specified system-dependent name, or from the specified File object, or from the specified file descriptor.
Lines 19-28. The while-loop initiates the try - catch construction which reads data written to the file test.dat. Notice that the output numbers have to be read in lines 21-22 by the methods readInt() and readDouble() which correspond directly to the output methods in lines 12-13. The program exits the loop when the end of the file is reached by catching the EOFException in lines 26-28. The program prints the numbers read as follows:
Correct reading: data file test.dat Int: 10; Double: 10.0 Int: 5; Double: 5.23 Int: 567; Double: 567.87 Int: 43; Double: 43.77 Int: 1238; Double: 1238.8765 *** End of file ***
This output shows that the file is written and read correctly.
Line 30. The method close() which is, in this case, from class FileInputStream closes the file input stream.
Lines 31-47. This part of the program is designed specially to show that you must be very careful while using the data files. The order of reading the data types from the file must be exactly the same as of writing these types to the file. Otherwise, you cannot predict the result of reading! In our example the order of reading (lines 36-37) is reversed comparing to the right order (see lines 21-22 and 12-13). Therefore, the program reads and prints the following wrong numbers:
Incorrect reading Wr.double: 2.17516225045E-313; wr.int: 0 Wr.double: 1.1141155273E-313; wr.int: 515396076 Wr.double: 1.20370631348E-311; wr.int: -1030792151 Wr.double: 9.1778580772E-313; wr.int: 1546188227 Wr.double: 2.627566059462E-311; wr.int: -1992864825 *** End of file ***
Notice that these errors cannot be detected by a method that reads a particular data type. The method inputs and converts simply as many sequential bytes from the input stream as it is prescribed by this data type (say, 2 bytes for char, 4 bytes for int, 8 bytes for double, etc., see Table 4). Thus, if your application has to use a data input stream then it has to be previously written by a data output stream. You need to know exactly in which order different primitive data types were put into the file to get them later in exactly the same order.
The class File is particularly useful for retrieving information about a file or a directory on a disk. Objects of class File do not actually open a file or provide any file-processing capabilities. But, they can check if a file exists and this is extremely important for any file writing activity. You must remember that
opening an existing file for output using a FileOutputStream or FileWriter object discards the contents of that file without warning!
You may use a File object to determine if the file already exists and, at least, warn the users that they are about to destroy the original contents of the file.
Instances of the class File represent the name of a file or directory on the host file system. A file is specified by a pathname, which is either an absolute pathname or a pathname relative to the current working directory. This class deals with most of the machine-dependent complexities of files and pathnames in a machine-independent fashion.
A File object is initialised by one of three constructors.
|
Method |
Description |
| boolean canRead() | Tests if the application can read from the file |
| boolean canWrite() | Tests if the application can write to this file |
| boolean delete() | Deletes the file (true if successfully) |
| boolean exists() | Tests if this object exists; |
| boolean isAbsolute() | Tests if the object is an absolute pathname |
| boolean isDirectory() | Tests if the object is a directory |
| boolean isFile() | Tests if the object is a ``normal'' file |
| boolean mkdirs() | Creates a directory whose pathname is specified by this object |
| int hashCode() | Computes a hashcode for the file |
| long lastModified() | Returns the time when the object was last modified (the return value is machine-dependent) |
| long length() | Returns the length of the file (in bytes) or 0L if the file does not exist |
| String getAbsolutePath() | Returns the absolute pathname of the object |
| String getName() | Returns the name of the File object. |
| String getPath() | Returns the pathname of the object |
| String [] list() | Returns a list of the files in a directory |
| String parent() | Returns the parent part of the pathname |
| String toString() | Returns a string representation of this object |
1 import java.io.*;
2 // FileView.class must be present in this folder
3
4 public class FileInformation {
5
6 public static void main( String [] args ) {
7
8 // Get a desired file or directory name
9 String fileName = FileView.getName();
10
11 // Represent the file by a File instance
12 File name = new File( fileName );
13
Figure 31: Program for retrieving disk information about a file or a directory.
14 // Print information about the file
15 if ( name.exists() ) {
16 System.out.println(
17 name.getName() + " exists\n" +
18 (( name.isFile())? "is a file\n" :
19 "is not a file\n" ) +
20 (( name.isDirectory())? "is a directory\n" :
21 "is not a directory\n" ) +
22 (( name.isAbsolute())? "is absolute path\n" :
23 "is not absolute path\n" ) +
24 "Last modified: " + name.lastModified() +
25 "\nLength: " + name.length() +
26 "\nPath: " + name.getPath() +
27 "\nAbsolute path:\n" + name.getAbsolutePath() +
28 "\nParent: " + name.getParent() );
29
Figure 32: Part 2 of the program in Figure 31.
30 // Print the contents of the file
31 if ( name.isFile() ) {
32 try {
33 RandomAccessFile r =
34 new RandomAccessFile( name, "r" );
35 System.out.println( "\nFile contents:\n" );
36 do {
37 System.out.println( r.readLine() );
38 } while ( r.getFilePointer() < r.length() );
39 }
40 catch ( IOException e2 ) { }
41 }
42
Figure 33: Part 3 of the program in Figure 31.
43 // Print the contents of the directory
44 else if( name.isDirectory() ) {
45 String dir[] = name.list();
46 System.out.println( "\nDirectory contents:\n");
47 for( int i = 0; i < dir.length; i++ )
48 System.out.println( dir[i] + "\n" );
49 }
50 }
51 else {
52 System.out.println( fileName + " does not exist\n" );
53 }
54 System.exit(0);
55 }
56 }
Figure 34: Part 4 of the program in Figure 31.
Some commonly used public methods of class File are shown in Table 6. Other methods you may find in the Java documentation. The application FileInformation in Figures 31 - 34 illustrates how to use the class java.io.File.
A FileDialog window created by the FileView class in line 9 (see also Figure 23) allows you to enter a file or directory name. Then the application creates a new File object name and assign it to the name entered.
Figure 37: Directory information displayed by FileInformation.
Next, the if-condition in line 15, that is, name.exists(), is tested. If the name typed does not exist on a disk the action proceeds to lines 51-53 and prints that the name you typed does not exist. This is shown in Figure 35.
Otherwise (if the name does exist), the program outputs the name of the file or directory, then outputs the results of testing the File object with isFile, isDirectory, and is Absolute, and prints the values returned by lastModified, length, getPath, getAbsolutePath, and getParent, as shown in Figures 36 and 37.
Finally, if the File object represents a file, the contents of the file is read and printed, too. If the object represents a directory, the contents of the directory are read using File method list in line 45 and printed out.
To read the file, a new RandomAccessFile object r is created and initialised with the File object name in lines 33-34. The file, opened for reading, is read line-by-line with the readLine method (lins 36-38).
In many practical situations, you need to deal with certain kinds of problem, called algorithmic. An algorithmic problem is specified by the precise definition of legal inputs and of desired outputs. Sometimes you need to think deeply to reformulate a practical task as a computational problem. But, this is only a starting step. Next you have to find a proper algorithm for solving the problem and develop an appropriate computer program that implements the algorithm. There exist different possibilities both for stating and solving algorithmic problems and you need to learn how to choose the best way.
Informally, an algorithm is a recipe, or a strictly defined system of rules, prescribing successive steps in solving a computational problem. A computer program is a clearly specified series of computer instructions implementing the algorithm.
``The Concise Oxford Dictionary of Current English'' (Oxford University Press, 1987) defines an algorithm, or algorism, as ``a process or rules for (especially, machine) calculations''. The word algorithm is derived from the surname of Uzbeki mathematician who worked in Persia in the 9th century, Mohammed al-Kuwârizmî, or ``Mohammed from Kuwârizm'', a province now in Uzbekistan (Middle Asia). His treatises on mathematics, translated from Arabic into Latin, had introduced to Europeans for the first time the Indian positional decimal number system and proposed step-by-step rules for adding, subtracting, multiplying, and dividing decimal numbers. It is just the numbers and rules that you learnt at school and use everyday! After translating, the surname became ``Algorismus'' and the computational rules took on this name. Of course, some mathematical algorithms did exist well before the term itself, for example, the Euclidean algorithm. By the way, the term ``algebra'' owes its origin also to the main treatise of al-Kuwârizmî, ``Al-Jabr'', which means the reunion of broken parts. When decimal numbers were introduced into Europe from Persia, the Arabic order of writing (right to left) was kept. Thus numbers have their most significant digits on the left, which forces the addition and multiplication algorithms to behave ``unnaturally'', working from right to left, instead of the ``more natural'' left to right.
Strangely enough, it is very difficult to give a precise (in the mathematical sense) definition of algorithms and programs. The known attempts have resulted in very deep general definitions which are too complex to be used for our purposes. To analyse algorithms in practice, it is quite sufficient to have a restricted definition that describes first a ``typical'' computer and then represents an algorithm as a sequence of basic computing steps which can be implemented in this computer. For simplicity, the computer is assumed to have an unlimited memory space with random access to store real and integer numbers and logical constants (``true'' and ``false''). The computer program consists of a legal sequence of instructions including standard arithmetic unary and binary operations, binary comparisons, branching operations, etc. Table 7 presents a few such well-known operations.
Table 7: Typical algorithmic operations and operands (note that in Java the logical operation AND is denoted &&, the logical OR is ||, and the logical NOT is denoted !).
|
Operation |
Notation |
Operands x,y | Result s |
| Assign | s = x | Real,integer,logical | |
| Add/subtract | s = x+y, s = x-y | Real, integer | |
| Multiply/divide | s = x·y, s = x/y | Real, integer | |
| Boolean | s = x AND y, s = x OR y, s = NOT y, etc. | Logical | Logical |
| Compare | s = (x < y), s = (x <= y ), s = (x == y), etc. | Real, integer | Logical |
Each operation is assumed to take a single time unit (or a computing step) and the number of such steps specifies the running time of a program implementing an algorithm.
When you come across a particular theoretical or applied problem you have to reformulate it as a computational problem and find an efficient solution, that is an efficient algorithm and its efficient software implementation. In so doing, first of all, you need know what means an ``efficiency'' with respect to algorithms and programs.
Usually, the same computational problem can be solved by different algorithms and the most efficient algorithm outperforms other using ones by less (computational) resources to obtain the solution. Basic resources include running or computing time and memory space. You may compare either maximum or average time/space requirements for all the legal instances of input data for a given problem. Any real computer has a limit on the size and the number of data instances it can handle. However, this limit cannot depend on the algorithm because it must give the right answer for each legal instance of input data, even if there is an infinite number of such instances.
You may notice that time/space notions are not exact and obvious when you compare algorithms and programs although you can accurately measure them for each particular computer program. The thing is that the same algorithm can be implemented by very different programs. The program can be written using different programming languages and run on the different computer platforms under different operating systems. In searching for the best algorithm, you need isolate the general features of algorithms from the particular peculiarities of the programs considered.
The time for running an algorithm depends on the number of sequential computing steps. Each step should be ``elementary'' in a sense that it corresponds to a basic computer instruction for manipulating the data and its execution time is bounded above by a constant depending only on the particular implementation used (computer, programming language, etc.). Most modern computers exploit ordinary arithmetic operations, presented partly in Table 7, as basic ``building blocks'' of complex programs. Therefore, it is quite natural to use operations such as additions, subtractions, multiplications, divisions, modulo operations, Boolean operations, comparisons, and assignments as basic computing steps in repesenting algorithms.
Memory space for running an algorithm depends on the number of individual variables (input data, intermediate and output results) to be used simultaneously at each computing step. Such time and space requirements almost always are independent of the programming language or style and characterise the algorithm itself. From here on, we will measure the effectiveness of algorithms and programs only in terms of their time/space requirements; we will assume that these algorithms and programs have been proven to be correct (at least, to within an admissible range of errors in the output data).
Correctness is the most general requirement for algorithms and programs competing for efficiency. An algorithm is correct if it gives valid output results for any legal input data. When you specify a problem, it is necessary to define clearly its domain of definition, that is, the set of legal instances of input data. To show that an algorithm is incorrect, you need only find one instance of input data which leads to an incorrect answer. But, if such instances are not found this does not mean that the algorithm is correct. Generally, you need a formal proof of its correctness for all the legal instances of input data. Such a proof involves a thorough mathematical analysis of the problem itself and of the algorithms and is rather difficult. Also, the software implementation has to be proven to be correct, too.
Therefore, to solve your particular task you have to know
Unfortunately, it is much easier to formulate these steps than to realise them in practice. But this is the way to master computers and programming techniques. In this chapter, we will focus upon the sixth step, called algorithm analysis.
In modern computer science there is a special area, called the theory of algorithms, for studying algorithms in a formal way. This theory clarifies the basic algorithmic notions: provability, correctness, complexity, randomness, computability, etc. It studies whether there exist algorithms for solving certain computational problems and how complex they may be. We will take only the first steps into this domain and, at most, the informal ones.
Of course, there are different sets of elementary computations to be used for building algorithms. "Turing machines", introduced by famous British mathematician Alan M. Turing in 1936, are very well known and involve the most trivial manipulation capabilities. A Turing machine has an infinite tape, or chain, of square cells as a memory and a sensing-and-writing head that can travel along the tape, one cell at a time, as a processor. There is a (finite) alphabet of symbols to be read from or written to the cell, a (finite) set of possible states of the head, and a state-transition diagram containing the instructions that cause changes to take place at each step. During its operation, this machine is allowed only to look at a particular symbol in a current cell on the tape and, depending on a current state, transform that symbol into one of the other available symbols, change the state and move one cell to the left or right. That's all... Nonetheless, the Turing machines are capable of solving any algorithmic problem! Of course, these algorithms are too complex for actual development - if you do not believe, try to construct a state-transition diagram for decimal addition or multiplication - but they do exist in principle. In practice, it is much more convenient to restrict the consideration to more familiar elementary computing steps. (Note that Turing was a matematician working 30 years after the invention of paper-tape data processing machines, but 10 years before the invention of electronic computers).
Now you are ready to search for the most efficient algorithm. It may be an empirical search by inventing or finding competing algorithms, programming them, and trying the programs on different test instances of input data using the available computers. This can work only for very simple problems, otherwise you will only spend much time without a definite result. There is an alternative and much more appealing theoretical approach which you will learn in this paper. It consists in proving the correctness of each algorithm using available mathematical tools and then determining the amounts of time/space resources needed by each algorithm as explicit functions of the size of input data to be processed. We will normally skip the first, ``proving'' step.
There are both practical and theoretical reasons for analysing algorithms.
An algorithm that requires several gigabytes of main computer memory or takes several weeks for processing a single set of input data is hardly likely to be accepted for practical use. And the analysis has to reveal these bottlenecks well before writing and testing the programs or a lot of work will be wasted.
To acquire a deeper understanding of computers, computing, and algorithm performance it is desirable to derive some general bounds on time-memory tradeoffs and use them as a basis for analysing computational efficiency. Here, we only briefly outline main approaches and results in this domain because they involve very complex theoretical studies.
The time-memory tradeoffs are derived in terms of the complexity of a problem. An algorithmic problem is first specified as a function, f. Let B be a basis, or set of Boolean functions such as AND, OR, and NOT. The combinatorial complexity of a function f relative to a basis B, denoted CB(f), is the minimum number of elements from B needed to realise f with a logic curcuit.
Then, the theoretical definition of the complexity of the program uses a ``universal Turing machine'', a sort of general-purpose theoretical computer. The program complexity IU(f) of the function specifying the problem, defined relative to the universal Turing machine U, is the shortest length of a program for computing a function f on the machine. A program is specified as a fixed string whose entries are constants and variables. When the variables are evaluated, it provides a string that is placed on the non-blank portion of the tape of the machine, and from this the function is computed.
From these and similar definitions and a thorough analysis based on them, two upper bounds can be derived in terms of the maximum number of steps T used to compute f at any point and the memory space S measured in bits. Let b denote bits per input word. Then the bounds are as follows
CB(f) <= c1 · T · S;
IU(f) <= c2 · (T·b + S),
where c1 > 0 and c2 > 0 are constants. These bounds can be applied to a general-purpose computer with a memory size of S when S is large. They define lower limits on time-space tradeoffs as indicated in Figure 38 where I* = c2 ·S. The region of time and space below either boundary, shown by hatching, is inaccessible because f cannot be computed at such operating points. The boundaries are moving away from the origin as the problem increases in complexity.
There do exist algorithms that come close to achieving the stated lower bounds on time-space tradeoffs. In practice, time requirements are usually more crucial for algorithms than memory space requirements. But, as the above analysis shows, each algorithm needs some minimum amount of memory to be practicable as regarding the computing time. But, mostly a linear space bound increase causes a linear time bound decrease, in other words, if the memory available is doubled, the time can be halved.. As you will see later, most algorithms have computing times which depend non-linearly on size of input data so that the time is growing much faster than linearly in this size. Therefore, a possibility of linearly improving the time may change little in the overall algorithm performance.
It is worth noting that time and memory space advantages are obtained sometimes at a sacrifice in correctness of an algorithm, say, if the chosen algorithm finds only the approximate desired output values or does not always give the correct output. But, such a way around has to be chosen only if the analysis shows that a correct algorithm is too complex to be implemented and this complexity cannot be reduced in principle.
An informal analysis of the two following very simple problems will show you how to estimate the running times of algorithms without going into programming details, and how to search for ways of reducing these times. Here, we will use only a few mathematical notations which are mostly necessary for describing and analysing the problems. There is a less familiar notation "Big-Oh" which is useful for algorithm analysis but you will become acquainted with it slightly later. The problems to be analysed are as follows:
Let ai be an i-th element of an array a. Here, i = 0, 1, ..., n-1. Obviously, to get the sum s = a0 + a1 + ... + an-1 you need to repeat n times the same amount of elementary computation (addressing an element in memory and addition) for each element in the array. Thus, the running time T(n) is proportional to n:
| T(n) = c ·n. |
Usually, it is said to be linear in n, and such algorithms are called linear. Of course, the factor c is unknown as it depends on a particular computer, programming language, compiler, operating system, etc. But, you may be sure that relative changes in the running time are just the same as the changes in the data size: T(10) = 10 ·T(1) or T(1000) = 1000 ·T(1).
Notice that we call the array items a0, a1, ..., an-1 to match a feature of the programming language Java and some other languages such as C, C++, etc.; these use the index range 0, ..., n-1 instead of the more ordinary 1, ..., n. Of course, this indexing is absolutely equivalent to the ordinary indexing a1, ..., an in our analysis.
The software implementation of this linear algorithm exploits a simple loop (we assume that the integer variable n and the integer array a are initialised and filled beforehand):
...
int sum = 0;
for(int k = 0; k <n ; k++) sum += a[k];
...
The total number of the subsequences is (n-m+1) = (m + 1) and you need to compute the sums of their items s1 = a1 + ... + am, s2 = a2 + ... + am+1, ..., sn-m+1 = an-m+1 + ... + an. From a first glance, we need to compute m+1 sums, each of m items, so that the running time is proportional to m ·(m+1):
|
When n = 20, the linear term is only 10% of T(n)/c. When n = 200, it gives only 1% of T(n)/c. Thus, the quadratic term is the only important one and the running time for large n is proportional to n2, or is quadratic in n:
|
Such algorithms are called quadratic algorithms in terms of
the relative changes of running times with respect to the changes of data
sizes: T(10) = 100 ·T(1) or T(100)
= 10000 ·T(1).
The software implementation of this quadratic algorithm exploits two nested loops (assuming that the variables m and n = 2 ·m and the array a are initialised and filled beforehand):
Let us analyse the above algorithm to see if there exists a less complex solution that excludes, if possible, repeated computations of the innermost loop. It is easily seen that two successive sums sk and sk-1, k > 1, differ only by two elements:
|
Thus you need not sum m items repeatedly after getting the very first
sum s1. Each next sum is formed from the current one
using only two elementary computations (addition and subtraction) so that
T(n) = c ·(m + 2 ·m) = 1.5 ·c ·n. Therefore,
the running time is still linear in n for this, slightly better
organised, computation. In the parentheses, the first m corresponds
to computation of the first partial sum s1 and 2 ·m
reflects that m other sums are computed using only 2 operations
per sum.
The software implementation of this linear algorithm excudes the innermost loop as follows:
... int [] sum = new int[m+1]; sum[0] = 0; for(i = 0; i < m; i++) sum[0] += a[i]; for(k = 1; k <= m; k++) sum[k] = sum[k-1] + a[k+m-1] - a[k-1]; ...
Notice that two simple successive loops, each taking m computational steps (a single step involves one addition in the first loop and one addition and one subtraction in the second loop) are substituted now for the previous nested loop which needed m2+m additions. This is a typical result of algorithm analysis. In most cases, a straightforward, or "brute-force" solution may be replaced by more effective one after a careful analysis of the problem. But you need know that there are no "standard" ways to reach this goal. You have to carry out a thorough investigation of the problem to exclude unnecessary computation by finding relations between the input data and desired outputs. You may exploit all the tools you have learnt (and you will indeed see many examples where these tools have proven their usefulness in practice). But, finding how to implement them in the best way for stating and solving your particular problem is still somewhat of an art. The more the examples and the tools you master, the more you learn this art.
Of course, you may also use this to make a program run slower in order to reduce memory needed. First of all you must implement an algorithm in a clearly written and correct program. Thus you should follow four basic recommendations:
Also, you may be misled by your intuition when estimating the main time-consuming parts of a program. Of course, you may have some working hypotheses about what part has the greatest impact on the overall performance. But changes to increase the efficiency must be based on reliable measurements, rather than on intuition.
You can measure how many times every operator or group of operators is executed by inserting temporary counters like count = count + 1 in a program and by checking time spent in subroutines. This allows the detection of parts of a program that really need to be improved.
Usually, the main trade-off between running time and memory space concerns repetitive computations: if the same input data and the same computations are used at different stages of an algorithm, then the results computed at the first stage can be saved for use in the subsequent stages. Such a tabular approach is especially useful for unary functions y = f(x) of an integer argument x having a relatively small range r = xmax - xmin +1 relative to the number n of data items to be processed. Here, xmax = max{x } and xmin = min{x } denote the maximum and the minimum argument values, respectively. If an auxiliary table containing r values:
|
can be allocated in the main computer memory, then computations of the function which can be rather time-consuming are replaced by simple and fast fetching of the tabulated results.
The above examples show that the running time depends considerably on how deep the loops are nested and how the loop control variables are changing. If the control variable is changing linearly in n (that is, increasing or decreasing by step 1) then the highest level k of nesting specifies the running time as follows:
for(int i1 = 0; i1 < n; i1++)
{
...; \\ Constant number of steps
}
for(int i1 = 0; i1 < n; i1++)
for(int i2 = 0; i2 < n; i2++)
{
...; \\ Constant number of steps
}
for(int i1 = 0; i1 < n; i1++)
for(int i2 = 0; i2 < n; i2++)
for(int i3 = 0; i3 < n; i3++)
{
...; \\ Constant number of steps
}
for(int i1 = 0; i1 < n; i1++)
for(int i2 = 0; i2 < n; i2++)
...
for(int ik = 0; ik < n; ik++)
{
...; \\ Constant number of steps
}
When the control variable is changing non-linearly then you need to estimate the running time which depends on n also non-linearly. In particular, an exponential change of a loop control variable results in a logarithmic running time (we assume that the integer variables n and k are initialised and filled beforehand):
int i = 1;
while( i < n )
{
i *= k;
...; \\ Constant number of steps
}
It is evident that this loop will terminate after m cycles such that km-1 < n <= km. Thus, m-1 < logkn <= m, and T(n) ~ c ·logk n.
Of course, additional conditions that allow for executing the inner loops only for special values of outer control variables will decrease the running time. For instance, can you tell whether the running time for the following loop is quadratic or linear?
int m = 1;
for(int i1 = 0; i1 < n; i1++)
if( i1 == m)
{
m*=(n-1);
for(int i2 = 0; i2 < n; i2++)
{
...; \\ Constant number of steps
}
}
And can you roughly estimate the running time for the following loop?
int m = 2;
for(int i1 = 0; i1 < n; i1++)
{
...; \\ Constant number of steps
if( i1 == m)
{
m*=2;
for(int i2 = 0; i2 < n; i2++)
{
...; \\ Constant number of steps
}
}
In the first example, the running time is linear in n because when n >= 3 the inner loop is executed only twice, for i1 = 1 and i1 = n-1.
In the second example, the inner loop is executed k times where k < log2n <= k+1, namely, for i1 = 2, 4, ..., 2k. Thus, the total running time is T(n) = c1 ·n + c2 ·n ·k ~ c2 ·n ·log2n for large n.
The above informal analysis shows that we need some specific tools to get rid of unspecified constant factors and non-leading terms when comparing the relative running times for different algorithms. We need also some quantitative criteria showing which types of algorithms are most effective in practice to solve a given problem and have to be searched for.
First of all, let us isolate the properties of an algorithm itself from the properties of the particular computer, operating system, programming language, and compiler used for its implementation. You need to use two rather simple concepts to separate both the input data and the algorithm that manipulates the data to get a desired output. These concepts have been briefly outlined above and are as follows:
|
Problem domain |
Meaning of n |
| Sorting | Number of numbers to be sorted |
| Graph/path | Number of vertices or number of edges |
| Image processing | Number of pixels |
| Text processing | Length of a character string |
Different computers, programming languages, and compilers translate steps of the algorithm into different machine language instructions. Thus, the running time of a program implementing the algorithm is represented by the value of c ·f(n) where c is an unspecified constant factor to be found for a particular computer, language, and compiler. But, even if it is still unspecified you are able to answer the following important question:
If the input size increases from n1 to n2, how will the relative running time T(n) change, the computer and compiler being fixed?
The answer is quite straightforward: the relative running time increases
|
times. There is a standard tool in mathematics, namely, the ``Big-Oh'' notation that means ``the order of ...'' or ``roughly proportional to ...''. It allows us to avoid constant factors c and non-leading terms when comparing functions regarding their rates of increase for large argument values. Three supplementary notations, namely, ``Big-Omega'', ``Big-Theta'', and ``Little-Oh'', you will learn next semester. Here, we restrict consideration only to the ``Big-Oh'' notation. Actually, the letter O used here is a capital omicron - all letters used in asymptotic algorithmic notation are Greek letters. However, since the Greek omicron and the English ``O'' are indistinguishable in most fonts, it has become customary to read O() as ``Big Oh'' rather than ``Big Omicron''.
The algorithms are analysed under the assumption that
if the number of computational steps as a function of n required by two algorithms differ only by a constant factor then the algorithms are considered to take essentially the same running time.
The functions that measure the running times of algorithms are positive-valued functions, as the running time T(n) is always positive (T(n) > 0). These functions are defined on the positive integer numbers n giving the input data sizes.
It is as follows:
Let f(n) and g(n) be positive-valued functions defined on the positive integers n. Then function g is defined as O(f) and is said to be of the order of f(n) iff (read: ``if and only if'') there is a real constant c > 0 and an integer n0 such that g(n) <= c · f(n) for all n > n0.
In other words, if g is O(f), then the algorithm with time complexity g runs, for large n , at least as fast, within a constant factor, as the algorithm with time complexity f. Usually the term ``asymptotically'' is used in this context to describe behaviour of functions for sufficiently large values of n. Thus, if g is O(f), then the time complexity of g has an order which is asymptotically less than or equal to the order of the time complexity of f.
Sometimes this is denoted as g(n) = O(f(n)), although you need not think that g is really equal to something called O(f). This notation really means that g is in the set O(f), that is, is a member of the set O(f) of functions which are increasing, in essence, with the same rate if n tends to infinity.
In terms of graphs of these two functions, g(n) is O(f(n)) if and only if there exists a constant c such that the graph of g is at or beneath that of c · f after a certain point, n0, is reached. The O() notation formally captures two ideas that are crucial in comparing algorithms:
Of course, if the constants involved are very large, then the asymptotic behaviour is of no practical interest. In most cases, however, the constants remain fairly small. In terms of the running time of algorithms, we shall use the ``Big-Oh'' definition with g(n) equal to the ``exact'' running time of inputs of size n and f(n) equal to the rough approximation to the running time.
|
Notice that ``Big-O'' hides constant factors so that both the functions 10-10 ·n and 1010 ·n are O(n). We will discuss this later in more detail. Regarding the notation itself, it is of no sense to write something like O(2 ·n) or O(a ·n + b) because this still means O(n). Only the leading term of the function giving the relative rate under n approaching infinity must be shown as the argument of "Big-Oh".
|
Therefore, the leading term of the polynomial P5(n) is n5. Generally, a term with the maximum degree nm is the leading one in a polynomial Pm(n) = am ·nm + am-1 ·nm-1 + . . . + a1 ·n + a0.
|
Generally, mn+k is O(ln); l >= m > 1, because mn+k <= ln+k = lk ·ln for any constant k.
|
Thus, all logarithmic functions have the same rate of increase and we may omit their bases when using the ``Big-Oh'' notation: O(log n).
A function f such that the running time T(n) of a given
algorithm is O(f) is said to measure the time complexity
of the algorithm. An algorithm is called polynomial if its time
complexity T(n) is O(nk) where k is an
arbitrary but fixed degree. Otherwise an algorithm is called exponential.
A computational problem is intractable iff no algorithm with polynomial
time complexity is known for it.
Notice that a problem may be reckoned among the intractable
problems if nobody knows whether it has or does not have a polynomial algorithm.
A lot of supposedly intractable problems are simply not known to be non-polynomial!
It is a major challenge to find a polynomial algorithm for one of them.
Table 9: Relative growth of time complexity as input size increases from n = 5 to n = 625.
| Time complexity | Input size n | |||
| Function | Notation | 25 | 125 | 625 |
| Constant | 1 | 1 | 1 | 1 |
| Logarithmic | log n | 2 | 3 | 4 |
| Log-squared | log2 n | 4 | 9 | 16 |
| Linear | n | 5 | 25 | 125 |
| ``n log n'' | n · log n | 10 | 75 | 500 |
| Quadratic | n2 | 25 | 625 | 15,625 |
| Cubic | n3 | 125 | 15,625 | 1,953,125 |
| Exponential | 2n | 1,048,576 | 2120 | 2620 |
Table 9 shows the relative growth of various functions
f(n) measuring the time complexity as the input size n increases
from 5 to 25, 125, and 625. Among the functions of Table 9,
g is O(f) iff g is listed before f: for instance,
the order of a logarithmic function is less than or equal to the order
of a linear function, and not the reverse.
Table 10: The largest sizes n of input data that can be processed by an algorithm with running time O(f(n)) for various f(n), assuming that when n=10$, the algorithm takes one minute to run.
| Length of time to run algorithm: | ||||||||
| f(n): | one second | one minute | one hour | one day | one week | one year | one decade | one century |
| n | 0 | 10 | 600 | 14,400 | 100,800 | 5.26 ·106 | 5.26 ·107 | 5.26 ·108 |
| nlogn | 1 | 10 | 250 | 3,997 | 23,100 | 883,895 | 7.64 ·106 | 6.72 ·107 |
| n1.5 | 0 | 10 | 153 | 1,275 | 4,666 | 65,128 | 302,409 | 1.40 ·106 |
| n2 | 1 | 10 | 77 | 379 | 1,003 | 7,249 | 22,932 | 72,522 |
| n3 | 2 | 10 | 39 | 112 | 216 | 807 | 1,738 | 3,746 |
| 2n | 4 | 10 | 15 | 20 | 23 | 29 | 32 | 35 |
Table 10 seems to be even more impressive because
it is specially designed to give you a concrete feel for the effect of
the order of an algorithm on the size of problems that can be solved effectively.
These data have been normalised so that all algorithms can solve a problem
of size n = 10 in exactly one minute. Then, your linear algorithm
will process more than 5.25 million data items per year and 100 times more
if you wait a century. But, an exponential algorithm can cope with only
29 data items after a year of running and add only 6 more items after
a century... Suppose you have computers 10,000 times faster (this is approximately
the ratio of a week to a minute). Then you could solve a problem 10,000 times
larger than before if your algorithm were linear (O(n)), 100 times
larger than before if it were O(n2), 21.6 times
larger than before if it were O(n3), but a problem
with only 13 additional input values if the algorithm were exponential
(O(2n)).
Therefore, if your algorithm has a constant (an almost unbelievable
success!), logarithmic, log-square, linear, or even ``n log n''
time complexity you can be happy and start to write a program with no doubt
that it will cope with most practical tasks. Of course, before you jump in happily
you need to check whether the hidden constant c, giving
the computation volume per data item in your case, is sufficiently small.
Unfortunately, order relations can be drastically misleading: for instance,
two linear functions 0.0001 · n and 1010 ·
n are of the same order O(n) but somehow you are not advised
to claim the algorithm with the second time complexity as your big success...
Therefore, you should follow a simple rule:
Roughly estimate a computational volume per data item for the algorithms after comparing their time complexities in a ``Big-Oh'' sense!
You may estimate the computation volume simply by counting the number of elementary (unary and binary) arithmetic operations such as addition, subtraction, multiplication, division, raising to a power, comparison, etc., per data item.
But, in any case it is clear that you should be VERY careful
even with simple polynomial (say, quadratic or cubic) and especially with
exponential algorithms. If the running time is 1 s per 5 data items
in all cases you will wait about 12 days (1,048,576 s)
for processing only 5 times more items by the exponential algorithm (you
may estimate yourself whether it is practical to wait until 125 items will
be processed...).
In practice, usually you cannot implement quadratic and cubic algorithms if the input size n exceeds a few thousand or a few hundred, respectively, and exponential algorithms should be avoided whenever possible. You need memorise the second rule:
Even most ingenious programming cannot make an inefficient algorithm fast!
Thus, it is better to spend more time finding an efficient algorithm and to content yourself with a less elegant software implementation than to spend time writing most elegant implementation of an inefficient algorithm.
Features of the ``Big-Oh''notation will be familiar to those who are familiar with calculus rules for derivatives. But these features are much simpler because complicated computational problems are described in terms of sums, products, and constant multiplies of elementary functions. In an informal way, the features are as follows.
Let us consider these features more formally using the following notation:
x denotes a function x(n) of n and y
denotes a function y(n) of n. Then z = x + y
is the sum of the functions: z(n) = x(n)+y(n) for every value
of n, and z = x · y denotes the product function:
z(n) = x(n) · y(n) for every n. Note that (x ·
y)(n) refers to the product of the values of two functions at n
and not to the value at n of the composition x(y(n)) of the
two functions.
The basic arithmetic of ``Big-Oh'' is governed by the following relations that are easily proven using its definition:
More specific cases follow directly from these relations:
| n1 + n2 + . . . + nr is O(nr). |
The ``Big-Oh'' notation is a useful way to analyse algorithms. In particular, it allows us:
The goal to be pursued in the study of the computational complexity of an algorithm is to show that its running time is O(f(n)) for some function f, and there can be no algorithm with a running time O(g(n)) for any function g that grows slower than f when n approaches infinity. You should try to provide both an ``upper bound'' and a ``lower bound'' on the worst-case running time.
To provide upper bounds, it is often sufficient to count and analyse how frequently the basic computational operations are performed (see, for example, section 3.2 above). Proving lower bounds is a difficult matter: you must carefully construct a formal mathematical model of computer, such as the Turing model, and determine which fundamental operations must be performed by any algorithm to solve a problem. Here, we will not touch upon this. But, when the analysis shows that the upper bound of an algorithm matches its lower bound, then you need not try to invent a faster algorithm and can concentrate on its implementation.
However, you must be extremely careful when interpreting results expressed by the ``Big-Oh'' notation, for the following reasons:
There are many algorithms for which is difficult to specify a worst-case input. But even the worst-case input is known, the inputs actually encountered in practice may lead to much lower running times. You will see below that the most widely used fast sorting algorithm, quickSort, has a worst-case running time of O(n2), but the running time for inputs encountered in practice is O(n·log n).
There is another approach to studying the performance of algorithms that examines the average case. Below, our consideration is restricted to the simplest case when the inputs to the algorithm can be precisely specified, namely, to sorting algorithms operating on an array of n random integers. In this case, you can calculate the average number of times each operation is executed, and estimate the average running time of the program by multiplying each operation frequency by the time required for the operation and adding them together.
Generally, this approach has the following difficulties:
Fortunately, few would argue against the use of an input data model such as ``randomly ordered file'' for a sorting algorithm. This model does make it possible to derive an average-case behaviour of some sorting methods.
As you will see later, a great many algorithms are based on the following principle:
The running time of such algorithms is determined by the size and number of the subproblems and the cost of the decomposition as a recurrence relation defined ``in terms of itself''. Let T(n) be the running time for n input data items. The following equations give an example of a recurrence relation:
| T(n) = 2 · T(n-1) + 1; T(1) = 1. |
The equation T(1) = 1 is called the base or an initial condition for the recurrence. Notice that a recurrence relation in computer science is called a difference equation in engineering.
Generally, when a function can be formulated as a recurrence, you may easily find the value of any particular term of the function by substituting known values to generate successive terms until the desired term is produced. In the above example, T(2) = 2 ·1 + 1 = 3, T(3) = 2 ·3 +1 = 7, T(4) = 2 ·7 + 1 = 15, and so on.
Of greater interest, partially because computation may be made easier, but primarily because the growth of T(n) as a function of n is more apparent, is the development of a closed form expression for T(n) (that is, what is traditionally called a ``formula''). For the above example, the closed form expression T(n) = 2n-1 can be guessed by inspecting the first few terms of the sequence. But in the general case, a more systematic approach is clearly needed. If you are not afraid of mathematics, you may learn, at least, two such general methods, namely, the method of characteristic roots and the method of generating functions: see B. M. E. Moret and H. D. Shapiro, ``Algorithms from P to NP. Volume 1: Design & Efficiency''. The Benjamin/Cummings Publ. Co: Redwood City, 1991, pp.61-82. Below, you will find a much simpler ``telescoping'' method which allows the obtaining of closed forms for many important recurrences that describe the performance of sorting and searching algorithms.
This relation arises when a recursive program loops through the input to eliminate one item:
| T(n) = T(n-1) + n; n > 1; T(1) = 1. |
To solve such a recurrence, let us ``telescope'' it by applying it to itself, as follows:
| T(n) | = | T(n-1) + n |
| T(n-1) | = | T(n-2) + (n-1) |
| T(n-2) | = | T(n-3) + (n-2) |
| . . . | . . . | . . . |
| T(2) | = | T(1) +2. |
By summing left and right columns and cancelling the similar terms, we obtain that
| T(n) = T(1) + 2 + ... + (n-2) + (n-1)+n = n · (n+1)/2 |
This relation arises for a recursive program that halves the input in one step:
| T(n) = T(n/2) + 1; n > 1; T(1) = 0. |
Let us assume that n = 2m so that the recurrence is always well-defined (note that m = log2n). Then, the recurrence telescopes as follows:
| T(2m) | = | T(2m-1) + 1 |
| T(2m-1) | = | T(2m-2) + 1 |
| T(2m-2) | = | T(2m-3) + 1 |
| . . . | . . . | . . . |
| T(2) | = | T(1) +1 |
so that T(2m) = m, i.e. T(n) = log2n. Generally, n/2 is assumed as integer division, and the precise solution for general n depends on properties of the binary representation of n. But, T(n) is about log2n for all n. This recurrence is usually called the repeated halving principle.
This relation arises for a recursive program that halves the input after examining every item in the input:
| T(n) = T(n/2) + n; n > 1; T(1) = 1. |
Under the assumption that n = 2m, the recurrence telescopes as follows:
| T(2m) | = | T(2m-1) + n |
| T(2m-1) | = | T(2m-2) + n/2 |
| T(2m-2) | = | T(2m-3) + n/4 |
| . . . | . . . | . . . |
| T(2) | = | T(1) + 1 |
so that T(n) = n + n/2 + n/4 + ... + 1 ~ 2 · n. For general n, the precise solution again involves the binary representation of n.
This relation arises for a recursive program that makes a linear pass through the input and splits it into two halves:
| T(n) = 2 · T(n/2) +n; n > 1; T(1) = 0. |
Under the same assumption that n = 2m, the recurrence telescopes as follows:
|
so that
|
|||||||||||||||||||||||||||||||||
Therefore T(n)/n = T(1)/1 + m = log2n, so that T(n) = n·log2n. This recurrence is prototypical of many standard ``divide-and-conquer'' algorithms.
You must neither overestimate nor underestimate the practical possibilities of an algorithm analysis. Many existing algorithms have been subjected to detailed mathematical analyses and performance studies far more complex than we will discuss in this paper. And it is on the basis of such studies that these algorithms have been recommended for practical use.
Of course, not all algorithms are worthy of such intense study, nor should you suppose that a rough complexity analysis will result immediately in an efficient practical program. But computational complexity gives you a powerful tool for suggesting basic design ideas upon which important new methods can be based.
To check if an algorithm analysis is correct, you can code the program and see whether the empirically observed running time matches the one predicted by the analysis. But notice that it can be very difficult to differentiate O(n) programs from O(n log n) programs using purely empirical evidence. Also, ``Big-Oh'' analysis is not appropriate for small amounts of input and hides the constants which may be crucial for a particular task. For instance, an algorithm with a running time 2n log n would be less efficient than another algorithm having a running time 1000n only when log n > 500, and such amounts of input data simply cannot be met in practice.
Large constants have to be taken into account when an algorithm is very complex, or when you must discriminate between cheap or expensive access to input data items, or when there may be lack of sufficient memory for storing large data sets, etc. But even when constants and lower-order terms are considered, the performance predicted by your analysis may differ from the empirical results. For instance, you will see later that the fastest known sort, Quicksort, has O(n2) worst-case running time but it is almost impossible to encounter this case in practice.
Worst-case bounds are usually easier to obtain than average-case
boundss. Note that sometimes it is very difficult to define what
``average'' means. Thus, you can use worst-case analysis to obtain some
meaningful estimates of possible algorithm performance. Also, this analysis
can frequently suggest how to analyse the average case.
But you must remember that both recurrences and asymptotic Big-Oh notation are just mathematical tools used to model certain aspects of the behaviour of algorithms. Like all models, they are not universally valid. Therefore, the mathematical model and the real program may exibit wildly divergent behaviour.
Data sorting takes a big part of computing time. Thus, it is very important to know the most effective sorting algorithms. Unfortunately, there is no absolutely best algorithm to be recommended in every case. Moreover, it is an open question which algorithm is the best in a particular situation because its efficiency may depend on many causes, for instance,
It is obvious that sorting should be easier if the data are partially pre-sorted.
Usually the items to be sorted are constructed in such a way that each item is labelled by a specific integer key. Sorting rearranges a unordered array of the keys in an ascending order. In other words, the final array (a0, a1, ..., an-1) of the keys is arranged as follows: a0 <= a1 <= ... <= an-1; for instance,
| (25,8,2,91,70,50,20,31,15,65) --> (2,8,15,20,25,31,50,65,70,91). |
In this section we will restrict our consideration to sorting integer arrays. But if an array contains arbitrary countable items with the integer keys, then the sorting algorithms and programs are very similar. In this latter case you need a particular Java interface (an ultimate abstract class that consists of public abstract methods and public static final fields only) to define the items to be sorted. You define a class to implement the interface by providing definitions for all the abstract methods in the interface.
To sort any items, you must have a definition of an ordering relation between the items of a given array. Generally, such a relation specifies how to place any pair of items x and y in a given fixed order (x,y). Usually, the ordering relation is denoted ``less than or equal to'' ( <= ).
It is evident that integer or real numbers are ordered by their values, for instance, 5 <= 5 <= 6.4 <= 22.7 <=... You know, also, the alphabetic order such as a <= b <= c <= d <= ... <= z (of course, this depends on local alphabets and differs for different countries). The alphabetic order can be extended to the lexicographic order such as a <= b <= c <= cat <=catty <=cut <= d <=... <= z <= zz ... The telephone book uses lexicographic order.
The ordering relation on an array A = {a,b,c,...} has the following features which are obvious for numbers or alphabetical characters:
Under an ordering relation, an array A has a linear order if, for any pair of its elements a and b, either a <= b or b <= a. In this case, it is possible to arrange all the elements in a chain where each next element is ``greater than'' the preceding neighbour.
This sorting splits the array onto an unordered and ordered part and sequentially contracts the unordered part, one element per stage. At the beginning of each stage i = 1, ..., n-1 the unordered and the ordered part contain n-i and i elements, respectively:
| ordered part | unordered part |
| a0, ..., ai-1 | ai, ...,an-1. |
The first element ai of a current unordered part is removed and placed in the correct position in the ordered part by exhaustive backward search along the already ordered elements, starting from the largest one, until it reaches an element with a lower or equal values).
In the routine, presented in Figure 39, the outer loop at line 7 increases by 1 the border i between the unordered and ordered parts. Here, i ranges from 1 to n-1 where n is the size of the array a to sort. The basic action of insertion sorting is to arrange for elements in positions 0 through k = i-1 to be sorted.
1 /**
2 * Sorting an integer array a[] by simple insertion
3 */
4 public static void insertionSort( int[] a ) {
5 int i, tempi, k;
6
7 for( i = 1; i < a.length; i++ ) {
8 tempi = a[ i ];
9 k = i - 1;
10 while( k >= 0 && tempi < a[k] ) {
11 a[ k+1 ] = a[ k ];
12 k--;
13 }
14 a[ k+1 ] = tempi;
15 }
16 }
When the inner while-loop at line 10 in Figure 39 starts, the elements in array positions 0 through i-1 are already sorted. The loop extends this to positions 0 to i by moving the sorted data one position up until the right position for inserting a current element ai is found. Table 11 shows the basic actions of the insertion sort in a particular case.
Table 11: Example
of the insertion sort
| i | C | M | Data to be sorted | |||||||||
| 25 | 8 | 2 | 91 | 70 | 50 | 20 | 31 | 15 | 65 | |||
| 1 | 1 | 1 | 8 | 25 | 2 | 91 | 70 | 50 | 20 | 31 | 15 | 65 |
| 2 | 2 | 2 | 2 | 8 | 25 | 91 | 70 | 50 | 20 | 31 | 15 | 65 |
| 3 | 1 | 0 | 2 | 8 | 25 | 91 | 70 | 50 | 20 | 31 | 15 | 65 |
| 4 | 2 | 1 | 2 | 8 | 25 | 70 | 91 | 50 | 20 | 31 | 15 | 65 |
| 5 | 3 | 2 | 2 | 8 | 25 | 50 | 70 | 91 | 20 | 31 | 15 | 65 |
| 6 | 5 | 4 | 2 | 8 | 20 | 25 | 50 | 70 | 91 | 31 | 15 | 65 |
| 7 | 4 | 3 | 2 | 8 | 20 | 25 | 31 | 50 | 70 | 91 | 15 | 65 |
| 8 | 7 | 6 | 2 | 8 | 15 | 20 | 25 | 31 | 50 | 70 | 91 | 65 |
| 9 | 3 | 2 | 2 | 8 | 15 | 20 | 25 | 31 | 50 | 65 | 70 | 91 |
Possible runtime exception: by the way, the same program but with the order of the conditions in line 11 (see Figure 40) may give you the run-time exception ``IndexOutOfBoundsException'' and, if a catch block is not provided for a standard exception, cause an abnormal program termination, with an error message. Why?
1 /**
2 * Simple insertion: wrong programming
3 */
4 public static void insertionSort( int[] a ) {
5 int i, tempi, k;
6
7 for( i = 1; i < a.length; i++ ) {
8 tempi = a[ i ];
9 k = i - 1;
10 while( tempi < a[ k ] && k >= 0 ) {
11 a[ k+1 ] = a[ k];
12 k--;
13 }
14 a[ k+1 ] = tempi;
15 }
16 }
Figure 40: Simple insertion sorting giving a standard run-time exception.
The average complexity of insertion sorting can be estimated by finding the average number of comparisons in line 11 and data moves in line 12. Let us consider a stage i of the outer loop in line 7 (see Figure 39). At the very beginning of this stage, i elements of the initial array are already sorted and the next (i+1)-st element a[i] has to be included into the sorted part. There are i-1 positions 1,2,...,i-1 between the sorted elements and two more positions 0 and i at the ends of this part, in total, i+1 possible positions for the next element. To place the next element into the position i, i-1, ..., 1 you need, respectively, 1, 2, ..., i comparisons at line 11 and 0, 1, ..., i-1 moves at line 12, but only i comparisons and i moves to place it into the position 0.
A new element will be placed into a position which depends on its value with respect to the values of the already sorted elements. In total, there are 1 + 2 + ... i + i comparisons if placing the (i+1)-st element to all the possible positions. Therefore, an average number Ei of comparisons for placing it into the right position at stage i is as follows:
|
||||||||||||||||||||
Here, you have to recall that the sum of integers from 1 to i
is given by the Gauss formula 1+2+...+i = [(i ·(i+1))/
2].
If there are n elements then the outer loop in line 7 (Figure 39) performs n-1 stages with i = 1,2, ..., n-1. Then the total average number E of comparisons during the sorting is as follows:
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
where Hn ~ ln n + 0.577 when n tends
to infinity is called the n-th harmonic number.
Therefore, the average number of comparisons for sorting n integer keys by simple insertion is about n2/ 4. Similarly, it is obvious that the average number of data moves is also O(n2) so that the overall time complexity of this algorithm is O(n2). This means that this algorithm is not very practical for large n.
An inversion in an array a1,..., an of numbers is any ordered pair of positions (i,j) such that i < j but ai > aj. For instance, the sequence (3,2,5) has only one inversion corresponding to the pair (3, 2), the sequence (3,2,5,1) has four inversions corresponding to the pairs (3,2), (3,1), (2,1), and (5,1), and so on. Table 12 shows the numbers Ii of inversions for each element ai of the array in Table 11 with respect to all the preceding elements j = 1, ..., i-1.
Table 12: Number of inversions for an array element with respect to all preceding elements
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| ai | 25 | 8 | 2 | 91 | 70 | 50 | 20 | 31 | 15 | 65 |
| Ii | 0 | 1 | 2 | 0 | 1 | 2 | 4 | 3 | 6 | 2 |
You may notice that the total number of inversions in an array to be sorted I = I1 + I2 + ... + In is equal to the total number of times M when line 11 in Figure 39 is executed. Also, the total number of comparisons C in line 10 is equal to the total number of inversions plus n-1. For the initial array in Tables 11 and 12 I = 21 and the insertion sorting takes C = 30 comparisons and M = 21 data moves at lines 13 and 15 of the inner while-loop, in total, 51 operations.
Swapping two neighbours that are out of order removes exactly one inversion, and a sorted array has no inversions. Thus, if the array has I inversions, the algorithm has to do I implicit swaps of the neighbours along the array. Since there are O(n) other operations in the algorithm, the running time of the insertion sort is O(n+I) where I is the number of inversions in the original array.
Notice that for all arrays for which the number of inversions is O(n), the algorithm runs in linear time. But, it can be proven that the average number of inversions is O(n2). The proof is rather easy if there are no duplicate elements in the array and is based on a simultaneous analysis of the original array a and the reverse ar of this array (that is, the array in reverse order). Any ordered pair (i,j) represents an inversion in exactly one of a and ar. The total number of these pairs is given by the binomial coefficient:
|
Thus, an average array has half this amount, or n ·(n-1)/ 4. Because each swap of neighbours removes only one inversion, the number of such swaps required is directly proportional to n2. This lower bound shows that an efficient sorting algorithm must eliminate more than just one inversion between neighbours per exchange.
This algorithm proposed in 1959 by D. Shell improves insertion sorting substantially. It is one of the simplest but not the fastest of the known algorithms which are faster than insertion sorting.
The main idea of Shellsort is to first compare keys that are far apart, then keys that are less far apart, and so on, gradually shrinking toward the usual insertion sort. Shellsort uses a special sequence ht > ... > h2 > h1 =1 called the increment sequence that defines gaps between the elements to be sorted at each stage. Any increment sequence will work but some choices are better than others. After a stage that uses some increment h we will have ai-h <= ai for every i = h, h+1, ..., n-1. In other words, all elements spaced h apart are sorted.
It can be proved that an hk-sorted array remains hk-sorted after being then hk-1-sorted. Thus, the sorting done by early stages is not undone by later stages. Also, because the increment h1 = 1, the algorithm is guaranteed to sort the array.
The increment sequence proposed originally by D. Shell starts from an increment gap = n/2 and then halves it until reaching gap = 1. The routine shown in Figure 41 implements Shellsort with another, more efficient increment sequence suggested by G. Gonnet and based on dividing the increment gap by 2.2.
1 /**
2 * Shellsort with a sequence suggested by G.Gonnet
3 */
4 public static void shellSort( int[] a ) {
5 for( int gap = a.length / 2; gap > 0;
6 gap = ( gap == 2 )? 1 : (int) (gap / 2.2 ) )
7 for( int i = gap; i < a.length; i++ ) {
8 tempi = a[i];
9 k = i;
10 while( k >= gap && tempi < a[ k - gap ] ) {
11 a[ k ] = a[ k - gap];
12 k -= gap;
13 }
14 a[ k ] = tempi;
15 }
16 }
Figure 41: Shellsort implementation successive divisions of gaps by 2.2 which gives excellent performance in practice.
Time complexity of Shellsort depends heavily on the choice of increment sequences so that in general the algorithm analysis is very complicated. Except for the most trivial increment sequences, the average-case analysis is still an open problem. The worst and the average cases for the original Shell's increments can be proved to be O(n2) and O(n3/2), respectively. Thus, on average, Shellsort with these increments gives a significant improvement over insertion sort.
A minor change to the increment sequence, namely, ``odd gaps only'' (when gap divided by 2 is even then make it odd by adding 1), can be proven to give a worst-case running time of at most O(n3/2). An average performance with these increments is unknown although computer simulations gave its estimate as O(n5/4).
The third sequence used in Figure 41 has no theoretical basis but performs well in practice. The running time is below O(n5/4). Notice that the complicated code at line 6 ensures that gap >= 1. For the array in Table 13, the number of comparisons at line 10 is C = 30 and the number of data moves at line 11 is M = 9 so that the total number of operations (39) is lower than for insertion sort. But the larger the input data size n, the higher the speed of Shellsort comparing to the insertion sort, say, about 13.5 times for n = 1000, 70 times for n = 8000, and 415 times for n = 64000 in a particular computer simulation.
More improvement is possible, for instance,
Some of these sequences have theoretical backing, but no known sequence markedly improves the routine in Figure 41.
The performance of Shellsort is quite acceptable in practice up to a moderately large input data size (say, for n in the tens of thousands) and the simplicity of the code makes it the algorithm of choice in these cases. Notice that this simplicity does not mean that the algorithm analysis is also simple; in fact, Shellsort is a fine example of a very simple algorithm with an extremely complex analysis.
Table 13: Example
of Shellsort
| gap | i | C | M | Data to be sorted | |||||||||
| 5 | 25 | 8 | 2 | 91 | 70 | 50 | 20 | 31 | 15 | 65 | |||
| 5 | 1 | 0 | 25 | 50 | |||||||||
| 6 | 1 | 0 | 8 | 20 | |||||||||
| 7 | 1 | 0 | 2 | 31 | |||||||||
| 8 | 1 | 1 | 15 | 91 | |||||||||
| 9 | 1 | 1 | 65 | 70 | |||||||||
| 2 | 25 | 8 | 2 | 15 | 65 | 50 | 20 | 31 | 91 | 70 | |||
| 2 | 1 | 1 | 2 | 25 | |||||||||
| 3 | 1 | 0 | 8 | 15 | |||||||||
| 4 | 1 | 0 | 25 | 65 | |||||||||
| 5 | 1 | 0 | 15 | 50 | |||||||||
| 6 | 3 | 2 | 2 | 20 | 25 | 65 | |||||||
| 7 | 2 | 1 | 15 | 31 | 50 | ||||||||
| 8 | 1 | 0 | 65 | 91 | |||||||||
| 9 | 1 | 0 | 50 | 70 | |||||||||
| 1 | 2 | 8 | 20 | 15 | 25 | 31 | 65 | 50 | 91 | 70 | |||
| 1 | 1 | 0 | 2 | 8 | |||||||||
| 2 | 1 | 0 | 8 | 20 | |||||||||
| 3 | 2 | 1 | 8 | 15 | 20 | ||||||||
| 4 | 1 | 0 | 20 | 25 | |||||||||
| 5 | 1 | 0 | 25 | 31 | |||||||||
| 6 | 1 | 0 | 31 | 65 | |||||||||
| 7 | 2 | 1 | 31 | 50 | 65 | ||||||||
| 8 | 1 | 0 | 65 | 91 | |||||||||
| 9 | 2 | 1 | 65 | 70 | 91 | ||||||||
From a historical viewpoint, this algorithm is one of the first computer sorting methods; it was proposed by John von Neumann in 1945! This algorithm exploits a recursive divide-and-conquer approach offering the better bound O(n log n) for its running time, at least theoretically, than the bounds claimed for Shellsort. It consists of separating an initial array into two parts whose sizes are as nearly equal as possible, sorting these parts by recursive calls, and then merging the solutions for each part, preserving the order. More fully, Mergesort involves three steps:
To claim that this algorithm has a time complexity O(n log n), it is sufficient to show that the merging of two sorted groups can be done in linear time O(n). This merge, used in most external sorting algorithms, takes two input arrays a and b of length na and nb, respectively, and forms an output array c of length nc = na + nb.
Let pa, pb, and pc denote counters that point to current positions in the arrays a, b, and c. Initially they are set to the beginning of their respective arrays (pa = 0, pb = 0, pc = 0). The smaller of a[pa] and b[pb] is copied to the current entry c[pc], and the appropriate counters (that is, pc and either pa or pb) are advanced. When either input array is exhausted, the rest of the other array is copied to c.
1 /**
2 * Merges two sorted arrays into a sorted array
3 * a[na], b[nb] --> c[nc].
4 * Doesn't check that c.length = a.length + b.length
5 */
6 public static void simpleMerge(
7 int[] a, int[] b, int[] c ) {
8 int pa = 0;
9 int pb = 0;
10 int pc = 0;
11
12 // Main loop
13 while( pa < a.length && pb < b.length )
14 if( a[ pa ] < b[ pb ] )
15 c[ pc++ ] = a[ pa++ ];
16 else
17 c[ pc++ ] = b[ pb++ ];
18
19 // Copy the rest of the first array
20 while( pa < a.length )
21 c[ pc++ ] = a[ pa++ ];
22
23 // Copy the rest of the second array
24 while( pb < b.length )
25 c[ pc++ ] = b[ pb++ ];
26 }
Figure 42 shows an implementation of a simple merging. Notice that the routine does not check whether the array c has the proper dimension nc >= na + nb. If this condition is violated you may get the standard run-time exception ``IndexOutOfBoundsException''... If the sorted array a contains (2,8,25,70,91) and b contains (15,20,31,50,65), then they are merging into the sorted array c = (2,8,15,20,25,31,50,65,70,91) as follows.
The process continues as follows: comparing a[3] = 70 and b[2] = 31, a[3] = 70 and b[3] = 50, and a[3] = 70 and b[4] = 65 results, respectively, in c[5] = (b[2] = 31), c[6] = (b[3] = 50), c[7] = (b[4] = 65) at line 17. Because the array b is exhausted, the rest of the array a is then copied to c at lines 20-21: c[8] = (a[3] = 70) and c[9] = (a[4] = 91).
Because each comparison advances the counter pc, thus limiting the number of comparisons to nc = na+nb, the time needed to merge two sorted arrays is linear. Therefore, a divide-and-conquer algorithm that uses a linear merging procedure will run in O(n log n) worst-case time. This running time will also be the average-case and best-case times because the merging step is always linear.
A straightforward implementation of Mergesort is given in Figures
43
and 44. Here, public mergeSort
simply declares a temporary array and calls a
recursive private mergeSort
with the boundaries of the array. The merge routine follows the
above description of the simple merging procedure. It uses the first half
of the array (indexed from left to centre) as a,
the second half (indexed from centre + 1 to right) as
b, and the temporary as c. After merging, the temporary is
copied back to the original array.
1 /**
2 * Internal method that makes recursive calls:
3 * a[] integer array to be sorted
4 * tmpArray[] array to place the merged data
5 * left left-most index of the sub-array
6 * right right-most index of the sub-array
7 */
8 private static void mergeSort(
9 int[] a, int[] tmpArray, int left, int right) {
10 if( left < right ) {
11 int centre = (left + right) / 2;
12 mergeSort( a, tmpArray, left, centre);
13 mergeSort( a, tmpArray, centre + 1, right);
14 merge( a, tmpArray, left, centre + 1, right );
15 }
16 }
17
18 /**
19 * Mergesort algorithm
20 * a[] integer array to be sorted
21 */
22 public static void mergeSort( int[] a ) {
23 int[] tmpArray = new int[ a.length ];
24 mergeSort( a, tmpArray, 0, n-1 );
25 }
1 /**
2 * Merging two sorted halves of a sub-array
3 * a[n] integer array
4 * tmpArray[n] array to place the merged data
5 * leftPos left-most index of the sub-array
6 * rightPos index of the start of the 2nd half
7 * rightEnd right-most index of the sub-array
8 */
9 private static void merge( int[] array, int[] tmpArray,
10 int leftPos, int rightPos, int rightEnd ) {
11 int leftEnd = rightPos - 1;
12 int tmpPos = leftPos;
13 int leftBeg = leftPos;
14 // Main loop
15 while( leftPos <= leftEnd && rightPos <= rightEnd )
16 if( array[ leftPos ] < array[ rightPos ] )
17 tmpArray[ tmpPos++ ] = array[ leftPos++ ];
18 else
19 tmpArray[ tmpPos++ ] = array[ rightPos++ ];
20 // Copy the rest of the first half
21 while( leftPos <= leftEnd )
22 tmpArray[ tmpPos++ ] = array[ leftPos++ ];
23 // Copy the rest of the second half
24 while( rightPos <= rightEnd )
25 tmpArray[ tmpPos++ ] = array[ rightPos++ ];
26 // Copy tmpArray back
27 for( tmpPos=leftBeg; tmpPos<=rightEnd; tmpPos++ )
28 array[ tmpPos ] = tmpArray[ tmpPos ];
29 }
Although the running time of Mergesort is O(n log n), it is not used for sorting data in the computer memory because it needs extra linear memory for the temporary storage of merged data, and extra work for copying to the temporary array and back. It is possible to avoid this copying by switching the roles of array and tmpArray at alternate levels in the recursion but at the expense of complicating the routines. There is also a non-recursive implementation of Mergesort. However, the algorithms of choice for serious internal sorting applications are Quicksort or Heapsort. An average-case running time of Quicksort is O(n log n), and Heapsort has O(n log n) running time even in the worst case. In practice, generally, Heapsort is slightly slower than Quicksort but much simpler in implementation.
This algorithm, invented by C. A. R. Hoare in 1961, is also based on the divide-and-conquer idea. Unlike sorting by merging, the non-recursive part of Quicksort constructs the sub-instances rather than combining their solutions. At the first step, this algorithm chooses one of the items in the array to be sorted as the pivot. The array is then partitioned on either side of the pivot: the elements greater than the pivot are moved so as to be placed on its right, whereas all the others are moved to its left. If now the two sections of the array on either side of the pivot are sorted independently by recursive calls of the algorithm, the final result is a completely sorted array, no subsequent merge step being necessary.
The basic Quicksort is recursive and consists of the following four steps:
The first step takes account of the possibility that the array might be an empty set (this is important because the recursive calls could generate empty subsets). The choice of a pivot at the second step is crucial because some choices are much better than others (you will see below that the wrong choice might lead to O(n2) time complexity and the right pivot should be chosen in such a way as to balance the sizes of the two subsets to be sorted). One more problem to be analysed is what to do with elements equal to the pivot for preserving the O(n log n) efficiency of sorting.
The correctness of the algorithm is easily established by induction. Let us assume that Quicksort sorts correctly all subsets of n-1 elements. Let a = (a0,..., an-1) be an arbitrary array of n elements. Let a0 be the pivot and i be the pivot position after partition. If the following three conditions hold then, by the induction assumption, Quicksort sorts correctly the left and right groups so that all the array a is sorted correctly.
But, these conditions are evident directly from the partitioning principle.
The best case for Quicksort is that the pivot partitions the array into two equal-sized groups and that this happens at each stage of the recursion. The worst case is the opposite, if the pivot happens to be the smallest or the largest element. Then one of two groups is empty and the second group contains all the elements except for the pivot. We will then have to recursively call Quicksort on this second group. Let T(n) be the running time for sorting n elements. Suppose also that the time for partitioning an array at the first stage is c ·n. Then, for n > 1 the running time satisfies the following equation:
|
By ``telescoping'', or summing left and right parts of the equation T(i) = T(i-1) + c ·i for i = 1, ..., n and cancelling the equal terms, you obtain that
|
||||||
Thus, in the worst case T(n) is O(n2).
To estimate the average-case efficiency of Quicksort, let T(n)
denote an average running time for sorting n elements. At the first
stage Quicksort does no more than c ·n operations
to exhaust all the elements of the array. Then it has to sort two subsets,
size of i and n-1-i, respectively. Therefore, the
average running time for sorting n elements is equal to the linear
time for the partitioning step plus the average time for sorting i
and n-1-i elements. Here, i varies from 0 to n-1.
Let us assume that all these values of i may be met as the final pivot position in the sorted array. Then, the average time of each recursive call is equal to the average, over all possible subset sizes, of the average running time of recursive calls on sorting the subsets so that
|
||||||||||||||||||||||||||
Let us rewrite the above equation as
|
and subtract from it the like equation for (n-1) · T(n-1):
|
After rearranging terms and dropping the insignificant constants you obtain
|
or, what is the same,
|
By summing left and right parts of the equation T(i) / (i+1) for i = 2, 3, ..., n and cancelling the equal terms, we obtain
|
Therefore, the average-case T(n) is O(n log n).
The above analysis shows that we need a choice ensuring that the worst case does not occur. A wrong way is to use the first or the last element as the pivot (that is, the elements a[low] or a[high] in Figure 45). If the input array is already pre-sorted in ascending or descending order, then such a choice gives an extreme element and this behaviour will continue recursively. As a result, we would get quadratic running time when, in fact, we can do nothing! Thus, never use the first or last element as the pivot in Quicksort.
A reasonable choice for the pivot is the middle element of array a[middle] where middle = |_(low+high)/2_|. Here, |_z_| denotes the ``floor'' of a floating-point number z, or the integer obtained by discarding the fractional part of z (for instance, |_5.00_| = 5 and |_5.99_| = 5). When the input is already sorted, this gives the perfect pivot in each recursive call. You could construct an input sequence that results in a quadratic behaviour for this choice strategy but the chance of running into such a case in practice is astronomically small.
The awkward notation |_z_| for representing the greatest integer that is equal to or less than the floating-point number z is used here because today's web browsers have rather limited possibilities in displaying special symbols. Thus, we use >= to denote ``greater than or equal to'', <= to denote ``less than or equal to'', != to denote ``not equal to'', and |-z-| to represent the least integer that is equal to or greater than the number z. In the printed text of this handout you will find more usual mathematical symbols.
Both the above choices are passive as we try to avoid the degenerate cases that arise from nonrandom inputs. Instead, we may use an active choice for the pivot which behaves better than average passively chosen one. The best active choice is the median of the array to be sorted that partitions the array into two equal or almost equal subarrays of size |_n/2_| and n-|_n/2_|, respectively. But, the computation of the median will slow down Quicksort considerably. So we need a good estimate of the median which can be obtained without spending too much time.
It has been shown that a small improvement can be obtained by choosing as the pivot the median of the leftmost, middle, and rightmost elements of the array to be sorted (that is, the median of a[low], a[middle], and a[high]). Notice that for already-sorted arrays, the middle element is kept as the pivot and this is the best case.
The simplest strategy is to swap the pivot with the last element a[high] of the array to be sorted. (Notice that the better strategy, used below in the Java implementation, is to swap the pivot with the second-to-the-last element a[high-1] because, by the median-of-three construction, the last element is already greater than or equal to the pivot and can be placed just to the right of the pivot). Then, all the elements smaller than the pivot are moved to the left part of the array and the elements larger than the pivot are moved to the right part of the array. Table 14 exemplifies the partitioning of a 10-element array. Here, low = 0 , middle = 4, and high = 9. The pivot p = 65, obtained as the median of a[0] = 25, a[4] = 70, and a[9] = 65, is boldfaced.
Table 14: Example
of pivot positioning in Quicksort
( low = 0 , middle
= 4, and high = 9; the pivot
p = 65 is boldfaced.)
| Data to be sorted | ||||||||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | <-- Indices | ||
| 25 | 8 | 2 | 91 | 65 | 50 | 20 | 31 | 15 | 70 | i | j | Condition |
| 25 | 8 | 2 | 91 | 15 | 50 | 20 | 31 | 65 | 70 | swap(p, a[high-1]) | ||
| 25 | 31 | 65 | 0 | 7 | a[i] < p; i++; p > a[j] | |||||||
| 8 | 31 | 65 | 1 | 7 | a[i] < p; i++; p > a[j] | |||||||
| 2 | 31 | 65 | 2 | 7 | a[i] < p; i++; p > a[j] | |||||||
| 91 | 31 | 65 | 3 | 7 | a[i] >= p; p > a[j]) | |||||||
| 31 | 91 | 65 | 3 | 7 | swap(a[i],a[j]); i++;j-- | |||||||
| 15 | 20 | 65 | 4 | 6 | a[i] < p; i++; p > a[j]) | |||||||
| 50 | 20 | 65 | 5 | 6 | a[i] < p; i++; p > a[j] | |||||||
| 20 | 65 | 6 | 6 | a[i] < p; i++; p > a[j] | ||||||||
| 65 | 7 | 6 | i > j; break | |||||||||
| 25 | 8 | 2 | 15 | 31 | 50 | 20 | 65 | 91 | 70 | swap(a[i], p = a[high-1]) | ||
The array is searched simultaneously from left to right, looking for an element larger than the pivot, and from right to left, looking for an element smaller than the pivot. Let i and j be two counters, initialised at position low and high - 1, respectively. In Table 14 the search for a large element stops at a[3] = 91 and the search for a small element stops at a[7] = 31. To correctly place these two elements, the algorithm swaps them.
Then, the search continues until the counters have crossed positions in the array. At this point, all elements but the pivot are correctly placed in the array and we need to swap the pivot with the current element a[i] which is clearly larger than the pivot. The subarrays (25,8,2,15,31,50,21) and (91,70) of the elements that are smaller and larger than the pivot, respectively, are to be sorted then by recursive calls of quickSort.
It is very important to correctly handle the cases when the array elements are equal to the pivot. There are four variants as either counter i or j can be stopped if the pivot is equal to the current array element. But in the case when all elements in the array are identical, only if both i and j stop does the partition create two nearly equal subsets and the running time is O(n log n). Three other variants lead, for such arrays, to the worst-case bound O(n2).
An implementation of Quicksort is given in Figures 45 and 46. This program is optimised by taking into account that the median of the first, middle, and last elements can be found by sorting them in the array. As a result, the element in the first position is guaranteed to be smaller than or equal to the pivot, and the element in the last position is guaranteed to be larger than or equal to the pivot. Therefore,
Also, the program tests the size of the subset to be sorted because for small arrays a simple insertion sort will probably be faster than the recursive Quicksort. Here, the cutoff is ten elements but, in practice, it is machine-dependent, and you need to adapt this value experimentally.
1 /** Quicksort algorithm: a[] an integer array to be sorted
2 */
3 private static void quickSort( int[] a, int low, int high ){
4 int CUTOFF = 10;
5 if ( low + CUTOFF > high )
6 insertionSort( a, low, high );
7 else {
8 // Sort low, middle, high to choose a pivot
9 int middle = ( low + high ) / 2;
10 if( a[ middle ] < a[ low ] )
11 swapElements( a, low, middle );
12 if( a[ high ] < a[ low ] )
13 swapElements( a, low, high );
14 if( a[ high ] < a[ middle ] )
15 swapElements( a, middle, high );
16 // Place the pivot into the next-to-rightmost place high-1
17 swapElements( a, middle, high - 1 );
18 int pivot = a[ high - 1 ];
19 // Begin partitioning
20 int i, j;
21 for( i = low, j = high - 1; ; ) {
22 while( a[ ++i ] < pivot );
23 while( pivot < a[ --j ] );
24 if( i < j )
25 swapElements( a, i, j );
26 else
27 break;
28 }
29 // Restore pivot
30 swapElements( a, i, high - 1 );
31 // Sort small elements
32 quickSort( a, low, i - 1 );
33 // Sort large elements
34 quickSort( a, i + 1, high );
35 }
36 }
37 public static void quickSort( int[] a ) {
38 quickSort( a, 0, a.length - 1 );
39 }
Figure 45: Quicksort: median-of-three, partitioning, cutoff of small arrays
40 private static void swapElements( int[] a, int i, int j )
41 {
42 int temp = a[ i ];
43 a[ i ] = a[ j ];
44 a[ j ] = temp;
45 }
46 private static void insertionSort( int[] a, int low, int high)
47 {
48 int i, tempi, k;
49 if(low > high || low < 0 || high >= a.length ) {
50 low = 0;
51 high = a.length - 1;
52 }
53 for( i = low + 1; i <= high; i++) {
54 tempi = a[i];
55 k = i - 1;
56 while( k >= low && tempi < a[k] ) {
57 a[k+1] = a[k];
58 k--;
59 }
60 a[k+1] = tempi;
61 }
62 }
Figure 46: Methods used in the basic Quicksort routine in Figure 45.
In Figure 45, the public method quickSort() declared at lines 37-39 is merely a driver that calls the private recursive quickSort() method. Below, we discuss only the implementation of the recursive method.
Lines 4-6. The program tests for small subarrays and calls an insertion sort (this private method, given in Figure 46, differs from the public method in Figure 39 only in that it works with a subset). The insertion sorting is done when the subarray size is below a specified value given by the constant CUTOFF. Otherwise, the recursive procedure in lines 7-35 is used.
Lines 9-18. Here, the program sorts the low, middle, and high elements in place, and takes their median (that is, the middle element after this sorting) as the pivot. The pivot is swapped with the element in the next to last position at lines 17-18.
Lines 20-28. This is the partitioning phase. The counters i and j are initialised to 1 past their true initial values because the prefix increment and decrement operators at lines 22-23 will immediately adjust them before the array accesses. You must be careful when implementing these comparisons. For instance, the following almost similar code:
21' for( i = low + 1, j = high - 2; ; ) {
22' while( a[ i ] < pivot ) i++;
23' while( pivot < a[ j ] ) j--;
is incorrect. Why?
When the first while-loop at line 22 exits, i will be indexing an element that is greater than or possibly equal to the pivot. Similarly, when the loop at line 23 ends, j will be indexing an element that is less than or possibly equal to the pivot. If i and j are not crossed, these elements are swapped and the scanning is continued. Otherwise, the scan is terminated and the pivot is restored at line 30. The sort is finished by making two recursive calls at lines 32 and 34.
It is the simplicity of basic operations in the inner loop that makes this sort ``quick''. But, you may notice that the program implementation was guided by the algorithm analysis performed prior to the coding.
You studied this algorithm last year with respect to tree-like
data structures and, in the best case, you remember its Pascal implementation.
Here, we will analyse its performance and implement it in Java.
This algorithm, invented by J. W. J. Williams in 1964, exploits a special binary tree structure called heap to obtain an O(n log n) worst-case sorting. This is as good as can be achieved by a comparison-based algorithm as we will see later.
A complete binary tree is defined as a tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right. This tree has no missing nodes. An example of a complete binary tree of ten items is shown in Figure 47. Notice that had the node J been a right child of E, the tree would not be complete because of a missing node. Note that a complete binary ntree need not be a binary search tree.
Figure 47: A complete binary tree and its array
representation.
Recall that |_z_| denotes the floor of z, or the largest integer that is less than or equal to z. The height (longest path length) of a complete binary tree of n nodes is at most |_log n_|. This is because a complete tree of height h has between 2h and 2h+1-1 nodes. In this tree, each leaf has height h or h-1 and each leaf of height h is placed on the left to any leaf of height h-1.
It is very easy to store a level-order traversal of a complete binary tree in a linear array as shown in Figure 47. Although both Java and some other languages like C or C++ use indices 0 to n-1 for the array positions 1 to n, respectively, it is more convenient to describe the array representation of the tree in terms of the node numbers and the array positions changing from 1 to n. Therefore, when we speak about a position p in an array a we consider an array element a[i] with the Java index i = p-1.
In terms of positions, the node in position p has the parent node in position |_p/2_|, the left child is in position 2·p, and the right child is in 2·p + 1. For a leaf node q, the child position 2 ·q extends past the number of nodes n that are in the tree: 2 ·q > n. In Figure 47, the node 1 is the root (it has no parent node) which has the left child 2 and the right child 3; the nodes 2 and 3 have the left child 4 and 6 and the right child 5 and 7, respectively; the node 4 has the left child 8 and the right child 9, and the node 5 has only the left child 10. It is evident that the nodes 6, ..., 10 are the leaves of this tree.
A heap consists of a complete binary tree of given height h that has numerical keys associated with its nodes and possesses the following feature:
Thus, the root of the heap has the maximum key. An example of the heap is presented in Figure 48. Of course, you can also build the heap assuming that the key of the parent node is less or equal to the key of any child node. In this case, the root will have the minimum key.
The heap-order property is very promising because easy access to the maximum key is provided. Also, it takes logarithmic time to insert a new element into the heap. First, the new key must be placed in the next available location among the leaves: if there were k elements in the heap, you need to create the next position k+1. If the inserted key does not violate the heap order, you need not to do anything else. Otherwise, you swap the new key with its parent, and such a bubbling, or percolating up is repeated toward the root until the heap order is restored. The time to do this is at most O(h) where h is the heap height, so it is at most O(log n).
Let us, for instance, insert the 11-th element, 75, into the heap in Figure 48. This process takes three following steps:
The array representing the tree changes as follows (below, the new element is boldfaced and the elements that are moved for restoring the heap order are in italic and underlined):
| Position | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Array at step 1 | 91 | 65 | 70 | 31 | 8 | 50 | 25 | 20 | 15 | 2 | 75 |
| Array at step 2 | 91 | 65 | 70 | 31 | 75 | 50 | 25 | 20 | 15 | 2 | 8 |
| Array at step 3 | 91 | 75 | 70 | 31 | 65 | 50 | 25 | 20 | 15 | 2 | 8 |
The maximum element can be deleted from a heap in a similar manner.
It occupies the root of the tree, that is, the array position 1. When the
maximum is removed, a hole is created at the root. Since the heap becomes
now one smaller, then the last node must be eliminated and its key must
be put in the hole. Then you need to restore the heap order, and this can
be done by moving the hole down the tree. In so doing, the root is compared
with both its children and is swapped with the larger child if one of them
is greater. This process is repeated again, for any new position of
the hole until the heap order is restored. It is easy to see that it also
takes logarithmic time in the worst case. Such a process is called percolate
down. Because we percolate down the previous leaf key it is not surprising
that the process rarely terminates more than one or two levels early, so
the operation is logarithmic in average, too.
As a simple example, let us now delete the maximum element, 90, from the heap in Figure 48. This process takes the three following steps:
The array representing the tree changes as follows (below, the new element is boldfaced and the elements that are moved for restoring the heap order are in italic and underlined):
| Position | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| Array at step 1 | 2 | 65 | 70 | 31 | 8 | 50 | 25 | 20 | 15 |
| Array at step 2 | 70 | 65 | 2 | 31 | 8 | 50 | 25 | 20 | 15 |
| Array at step 3 | 70 | 65 | 50 | 31 | 8 | 2 | 25 | 20 | 15 |
You may use either the percolation up or the percolation down
algorithm to convert
a complete tree that does not have heap order into a heap. It is evident
that n insertions, starting from a single element, could do this
in O(n log n) time. But these insertions do more
work than we require, since they maintain heap order after every insertion.
We need heap order only at the last instant.
An alternative way is to view the heap as a recursively defined structure like ``left subheap'' <-- root --> ``right subheap''. We would recursively call the ``heapifying'' procedure on the left and right subheaps. At this point, we are guaranteed that the heap order is established everywhere except at the root. Now, by percolating the root down we can establish heap order everywhere.
The recursion guarantees that when we percolate down the key at
position p, all the descendants of node p have been processed
by their own call to a percolation-down procedure, recursively. Moreover,
recursion is not necessary if we call this procedure on nodes in reverse
level order. In this case, at the point the node p is processed,
all its descendants will have been processed by a prior call to the
percolation-down
procedure. Notice that you need not percolate down a leaf node. Thus,
you can start at the highest-numbered non-leaf node.
Method percDown( int[] a, int index, int size) that implements the percolation down is shown in Figure 49. This method percolates down an element of an integer array a. Parameters index and size specify the index i of the element to be percolated down (it is one smaller than the position p: p = i+1) and the size n of the (sub)array, respectively. The previous analysis leads to incredibly simple code for converting a given array into a heap (see also lines 7-9 in Figure 49):
for( index = a.length / 2 - 1; index >= 0; index-- )
percDown( a, index, a.length );
The basic processing time of the method percDown is spent in the for-loop at lines 23-38, Figure 49. Let m be the largest number of trips round this loop that can be caused by calling percDown(a, i, n). Let pt denote the value of the child position childPos just before execution of the t-th trip round the loop. Obviously, p1 = p = i+1. Also, if 1 < t <= m, then at the start of the (t-1)-st trip round the loop we have pt >= 2 ·pt-1. Consequently,
|
Thus, 2m-1 <= n/p, which implies that m <= 1 + log(n/p).
The total number of trips round the for-loop when constructing a heap can now be bounded above by the following sum:
|
where k = |_n/2_| and
|
To simplify the last expression, let us decompose it into sections corresponding to powers of 2:
|
so that
|
It is easy to see that for any d >= 0
|
and
|
To obtain the right-hand inequality, you need to prove that
|
This can be proved by mathematical induction but you could try first to see how you might have discovered it yourself.
Because k = |_n/2_| implies that k+1 <= logn and k-1 > log(n/8), we obtain that S(k,n) <= 3·n. Therefore, |_n/2_| + 3 ·n trips round the for-loop in percDown are enough to construct a heap, so that this can be done in a linear time O(n).
Let T(h) stand for the time needed to build a heap of height at most h in the worst case. Assume h>1. In order to construct the heap, the algorithm first transforms each of the two subtrees attached to the root into heaps of height at most h-1. Notice that the right subtree could be of height h-2. The algorithm then percolates the root down a path whose length is at most h, which takes a time O(h) in the worst case. We thus obtain the asymptotic recurrence:
|
It is easy to conclude that T(h) is O(2h). But a heap containing n elements is of height h = |_log2n_|. Hence it can be built in at most T(|_log2n_|) steps, which is O(n) since 2|_log2n_| <= n.
The sorting algorithm consists of two steps:
Thus, we have an O(n log n) worst-case sorting.
Notice that after each deletion of the maximum, the heap shrinks by 1. Thus the array cell that was last in the heap can be used to store the element that was just deleted. Under this strategy, the array will contain, after the last deletion, the elements (keys) in the increasing sorted order. If you want the array in decreasing sorted order, you have to change the heap ordering property so that the parent has a smaller key than the child does. Thus we have a min heap instead of the above max heap.
Figure 49 presents a Java implementation of Heapsort. Here, the for-loop at lines 8-9 builds a heap from a given integer array a and the for-loop at lines 11-14 deletes each current maximum element by swapping it with the current last position in the array to be excluded from the heap. The swapping method swapElements is given at lines 40-45 in Figure 46.
5 public static void heapSort( int [] a ) {
6 int index;
7 // Build a heap
8 for( index = a.length / 2 - 1; index >= 0; index-- )
9 percDown( a, index, a.length );
10 // Delete the maximum (heap root) and restore the heap
11 for( index = a.length - 1; index >= 1; index-- ) {
12 swapElements( a, 0, index );
13 percDown( a, 0, index );
14 }
15 }
// Percolating down after changing an element a[index]
// within a heap a[0],...,a[size-1] of integers
20 private static void percDown( int[] a, int index, int size ){
21 int childPos; // a position is one greater an array index
22 int parentPos = index + 1;
23 for( childPos = parentPos * 2; childPos < size;
24 childPos = parentPos * 2 ){
25 if( a[ parentPos - 1 ] < a[ childPos - 1 ] ||
26 a[ parentPos - 1 ] < a[ childPos ] ) {
27 if( a[ childPos - 1 ] < a[ childPos] ) {
28 swapElements( a, parentPos - 1, childPos );
29 parentPos = childPos + 1;
30 }
31 else {
32 swapElements( a, parentPos - 1, childPos - 1 );
33 parentPos = childPos;
34 }
35 }
36 else
37 break;
38 }
39 if( childPos == size &&
40 a[ parentPos - 1 ] < a[ childPos - 1 ])
41 swapElements( a, parentPos - 1, childPos - 1 );
42 }
As an example, Table 15 presents the successive steps of sorting the input array a[10]={65, 31, 20, 91, 15, 2, 8, 50, 25, 70} by Heapsort. Here, the moved keys are shown in italic and underlined, and the sorted items are boldfaced. The implementation of Heapsort is simple because the basic operations follow the heap operations of percolating down and deleting maximum.
| Position | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| Initial array | 65 | 31 | 50 | 91 | 2 | 70 | 25 | 20 | 15 | 8 |
| Building max heap: | 91 | 65 | 70 | 31 | 8 | 50 | 25 | 20 | 15 | 2 |
| Deleting max 1: | 2 | 65 | 70 | 31 | 8 | 50 | 25 | 20 | 15 | 91 |
| Restoring heap 1-9: | 70 | 65 | 50 | 31 | 8 | 2 | 25 | 20 | 15 | 91 |
| Deleting max 2: | 15 | 65 | 50 | 31 | 8 | 2 | 25 | 20 | 70 | 91 |
| Restoring heap 1-8: | 65 | 31 | 50 | 15 | 8 | 2 | 25 | 20 | 70 | 91 |
| Deleting max 3: | 20 | 31 | 50 | 15 | 8 | 2 | 25 | 65 | 70 | 91 |
| Restoring heap 1-7: | 50 | 31 | 25 | 15 | 8 | 2 | 20 | 65 | 70 | 91 |
| Deleting max 4: | 20 | 31 | 25 | 15 | 8 | 2 | 50 | 65 | 70 | 91 |
| Restoring heap 1-6: | 31 | 20 | 25 | 15 | 8 | 2 | 50 | 65 | 70 | 91 |
| Deleting max 5: | 2 | 20 | 25 | 15 | 8 | 31 | 50 | 65 | 70 | 91 |
| Restoring heap 1-5: | 25 | 20 | 2 | 15 | 8 | 31 | 50 | 65 | 70 | 91 |
| Deleting max 6: | 8 | 20 | 2 | 15 | 25 | 31 | 50 | 65 | 70 | 91 |
| Restoring heap 1-4: | 20 | 8 | 2 | 15 | 25 | 31 | 50 | 65 | 70 | 91 |
| Deleting max 7: | 15 | 8 | 2 | 20 | 25 | 31 | 50 | 65 | 70 | 91 |
| Restoring heap 1-3: | 15 | 8 | 2 | 20 | 25 | 31 | 50 | 65 | 70 | 91 |
| Deleting max 8: | 2 | 8 | 15 | 20 | 25 | 31 | 50 | 65 | 70 | 91 |
| Restoring heap 1-2: | 8 | 2 | 15 | 20 | 25 | 31 | 50 | 65 | 70 | 91 |
| Deleting max 9: | 2 | 8 | 15 | 20 | 25 | 31 | 50 | 65 | 70 | 91 |
Data selection is closely related to data sorting: in the latter case one arranges an array in an ascending or descending order whereas in the former one has to find only the kth smallest item. Given an array of n items, you can sort it and then select the desired item. But one may hope that if the rank k is fixed (say, the median, or n/2-th smallest item) then selection would require less information than sorting and be a faster process.
The program quickSelect in Figure 50 that solves the selection problem in linear time, on average, is obtained by a small change of quickSort. When this algorithm terminates, the k-th smallest element is in its correct position k-1 in the array.
1 // internal selection: k-th smallest item to a[k-1]
2 private static void
3 quickSelect( int[] a, int low, int high, int k ){
4 int CUTOFF = 10;
5 if ( low + CUTOFF > high )
6 insertionSort( a, low, high );
7 else {
8 // Sort low, middle, high to choose a pivot
9 int middle = ( low + high ) / 2;
10 if( a[ middle ] < a[ low ] )
11 swapElements( a, low, middle );
12 if( a[ high ] < a[ low ] )
13 swapElements( a, low, high );
14 if( a[ high ] < a[ middle ] )
15 swapElements( a, middle, high );
16 // Place the pivot into a rightmost place
17 swapElements( a, middle, high - 1 );
18 int pivot = a[ high - 1 ];
19 // Begin partitioning
20 int i, j;
21 for( i = low, j = high - 1; ; ) {
22 while( a[ ++i ] < pivot );
23 while( pivot < a[ --j ] );
24 if( i < j ) swapElements( a, i, j );
25 else break;
26 }
27 // Restore pivot
28 swapElements( a, i, high - 1 );
29 // Selection by recursion (the only changed part!)
30 if( k < i )
31 quickSelect( a, low, i - 1, k );
32 else if( k > i )
33 quickSelect( a, i + 1, high, k );
34 }
35 }
36 public static void quickSelect( int[] a, int k ) {
37 quickSelect( a, 0, a.length - 1, k );
38 }
Figure 50: Quickselect: median-of-three, partitioning, cutoff of small arrays
The basic Quickselect is recursive and consists of the following four steps (the three first steps are very similar to the original Quicksort) to be executed for a subarray (a[low], a[low+1], ..., a[high]) in a given array a. Here, 0 <= low <= high <= n-1 where n is the number of elements in a.
The first step takes account of the possibility that the array might contain a single element (this is important because the recursive calls could generate such subsets).
To estimate the average-case efficiency of Quickselect, let T(n) denote the average running time for selecting the k-th smallest element among n elements. At the first stage Quickselect does no more than c ·n operations to exhaust all the elements of the array. Then it has to select in one of two subsets, size of i and n-1-i, respectively. Therefore, the average running time for selecting among n elements is equal to the linear time for the partitioning step plus the average time for selecting among i or n-1-i elements. Here, i varies from 0 to n-1.
Let us assume that all these values of i may be met as the final pivot position in the sorted array. Then, the average time of each recursive call is equal to the average, over all possible subset sizes, of the average running time of recursive calls on sorting the subsets so that
|
||||||||||||||||||||||||||
Let us rewrite the above equation as
|
and subtract from it the like equation for (n-1)·T(n-1):
|
After rearranging terms and dropping the insignificant constants you obtain
|
Therefore, the average-case T(n) is O(n).
If you compare the above sorting algorithms then the average and the worst time complexity are in the best cases about O(n log n). But you have no chance of inventing a new algorithm with a better lower bound because it can be proven that there are no such sorting algorithms based on comparing the pairs of items.
This is one of the most fundamental theorems in the algorithm analysis (recall that n!, or ``n factorial'' is the product 1 ·2 ·...·n and let |-z-| denote the ``ceiling'', or the least integer value which is greater than or equal to the floating-point number z):
Any algorithm that sorts by comparing only pairs of elements must use at least |-log(n!)-| comparisons in the worst case (that is, for some ``worst'' input sequence) and in the average case.
To prove it, let us notice that any sorting of n items by pairwise comparisons can be represented by n-element decision tree. A simple example of such a tree for n = 3 elements (a1, a2, a3) is given in Figure 51. Each internal vertex of the tree represents a comparison, or decision, made by an algorithm at a particular step. In Figure 51, i:j denotes a comparison between the elements ai and aj. Two downward edges give two possible results of the comparison. Leaves show the sorted arrays obtained by the algorithm (in Figure 51, ijk denotes the array (ai, aj, ak)). Because any of the n! permutations of n arbitrary items a1, a2, ..., an may be obtained as the output of the sort, the decision tree for n elements sorted by pairwise comparisons must have at least n! leaves.
The length of a path from the root to a leaf is equal to the number of comparisons needed to obtain the sorted array which is represented by the leaf. Therefore, the longest path given by the height of the tree specifies the number of comparisons in the worst case. In particular, because the height of the three-element tree in Figure 51 is equal 3, then for sorting 3 elements you need no more than 3 comparisons.
To estimate the worst-case complexity of sorting n items, let us find the height h of the n-element decision tree having n! leaves. First, by mathematical induction we can prove that any decision tree of height h has at most 2h leaves:
Therefore, the lower bound for the least value h such that 2h >= n! is as follows:
|
By using the Stirling's approximation
|
you may obtain a more exact lower bound:
|
In other words, the decision tree for sorting by pairwise comparisons
is of height at least h >= n logn - 1.44 n
so that the worst-case complexity of each such sorting algorithm is at
least
O(n log n).
Let us regard the possible input arrays as any permutations of 1, 2, ..., n. This is possible because only the relative order of the input items is of interest for sorting, not their actual values. Thus, the number of possible inputs is the number n! of different arrangements, or permutations, of n items. Let Pi be the number of permutations that are consistent with the results after the algorithm has processed i comparisons. In other words, let Pi be the number of permutations which are still not eliminated after processing i comparisons. Let h be the number of comparisons processed when the sort terminates.
The following assertions hold:
The action of the sorting algorithm is thus to go from the state P0, in which all n! permutations are possible, to the final state Ph, in which only one permutation is possible, with the restriction that there exists an input such that in each comparison, only half of the permutations can be eliminated. By the halving principle:
|
||||||||
we obtain that P0 = 2h. Therefore, at least |-log(n!)-| comparisons are required for that input so that
|
The lower average-case bound of sorting complexity is also O(n log n). To prove this, let us use again the model of n-element decision tree. We assume that any permutation of n elements has the same chance to be input for sorting. Also, each of the possible n! leaves of the decision tree can be reached with the same chance. Then, the average number of comparisons is equal to the average height of these n! leaves.
Let us prove that each n-element decision tree has an average height at least log(n!) >= n logn by mathematical induction. Let H(D,k) denote the sum of heights for all leaves of a decision tree D with k leaves and let H(k) = min{H(D,k)} be the minimum sum of heights for all the decision trees with k leaves. If we prove that H(k) >= k logk, then the same relation will be valid also for the average height of any decision tree with k leaves.
|
(because the link to the root of D adds 1 to each height of a leaf in D1 and D2). The minimum height among all the heights H(D,k) is as follows:
|
By the induction assumption, H(k1) >= k1 log k1 and H(k2) >= k2 log k2 so that
|
It is easily shown (for example, by symmetry consideration) that the minimum is reached for k1 = k2 = k/2. Therefore,
|
Because each n-element decision tree D has at least n! leaves, then H(n!) >= n! log(n!) and the average height of each n-element decision tree is equal at least
|
Therefore, each sorting by pairwise comparisons has the average-case
complexity at least
O(n log n).
Data searching is a fundamental operation which you may meet in a great many computational tasks: retrieving some particular piece or pieces of information from a large database storing previously collected information. Usually, this information is divided up into records and each record has a key for use in searching. The goal of the search is to find all records with keys matching a given search key. The purpose of the search is usually to access information within the record (not merely the key) for processing.
A static search accesses static data which is not allowed to change. When a data structure A of records has integer keys, the static searching problem can be formulated as follows:
Given an integer search key X, return either the data associated with X in A, or an indication that X is not present, without altering the array A. If X occurs more than once, return any occurrence.
An alternative search that allows insertions and deletions of the stored
data can be called a dynamic search.
Simple examples of static searching are: looking up a person in the telephone book, looking up a word in an English language dictionary. If the data structure is an array, it is obvious that the efficiency of searching depends on whether the array being searched is sorted. In the case of the telephone book, you find the desired number fast by name. But it is hopeless for you to search by phone number unless you have a special ``number --> name'' dictionary.
If you have an unsorted input array, only a linear sequential search can be used. It is stepping through the array sequentially, record by record, until a match is found. The complexity of the algorithm is O(n) in the worst case and the average case, both for successful and unsuccessful search.
An unsuccessful search has to examine each item in the array, so the time complexity is O(n) (notice, that for such a search the worst case coincides with the average case). The worst-case successful search requires the examination of each item, too. On average, only half of the array has to be searched, but n/2 is still O(n).
The routine in Figure 52 demonstrates a sequential search for a particular integer key in a given integer array a. You may easily rewrite this routine to examine any Comparable objects with integer fields as search keys. The routine returns the position in the array if the search is successful or throws an ItemNotFound exception otherwise.
1 /**
2 * Sequential search in an integer array a[]
3 * Returns index where an item is found or
4 * throws an ItemNotFound exception
5 */
6 public static int sequentialSearch( int[] a,
7 int key) throws ItemNotFound {
8 for( int i = 0; i < a.length; i++ )
9 if( a[ i ] == key ) return i;
10 throw
11 new ItemNotFound( ``SequentialSearch fails'' );
12 }
Sequential searching is easily adapted to use a linked-list representation for the records (hopefully you have not forgotten this data structure which you learnt last year). One reason for using a linked list is that, for a sorted list the search is more efficient; since the list is sorted, a search can be terminated when a record with a key not smaller than the search key is found. Sorted order is easy to maintain by inserting each new record where an unsuccessful search for it terminates. It is not difficult to show that a sequential search implemented for a sorted list uses about n/2 comparisons for both successful and unsuccessful search on the average. Thus, such a search still has O(n) average-case and worst-case complexity.
If the set of records is large but sorted in ascending order of key values, then the total search time can be significantly reduced using a binary search. Binary search implements the ``divide-and-conquer'' paradigm. Let an array of n records be ordered so that the keys satisfy:
|
Given a search key key, it is necessary to find if there is a corresponding record in the array (a successful search) or to detect that it is not present in the array (an unsuccessful search). Binary search is as follows:
1 /**
2 * Binary search in an integer array a[]
3 * Returns index where an item is found or
4 * throws an ItemNotFound exception
5 */
6 public static int binarySearch( int[] a ,
7 int key) throws ItemNotFound {
8 int low = 0;
9 int high = a.length - 1;
10 int middle;
11
12 while( low <= high ) {
13 middle = ( low + high ) / 2;
14
15 if( a[ middle ] < key )
16 low = middle + 1;
17 else if( a[ middle ] > key )
18 high = middle - 1;
19 else
20 return middle;
21 }
22 throw
23 new ItemNotFound( "BinarySearch fails" );
24 }
Figure 53 shows a Java implementation of binary search. In any loop iteration, it keeps track of low and high, which delimit the part of the array in which a desired item, if present, must reside. Initially, the range is from 0 to n-1 (the total array). If low becomes larger than high, then the item is absent. In this case an exception is thrown (instead, it may return, say, -1). Otherwise, the halfway point middle of the range is computed (rounded down if the range has an even number of elements), and the search key key is compared with the item in position middle, that is, with a[ middle ]. The following three-way comparison is used:
In Figure 53, lines 15 to 18 alter the possible range, essentially cutting it in half. By the repeated halving principle, the number of iterations will be O(log n). Therefore, binary search has logarithmic time complexity.
Figure 54 illustrates a binary search for the key 42 in the 16-element array. At the first iteration, this search key is compared with the element a[ 7 ] = 53 in the middle position |_(0+15)/2_| = 7. Because 42 < 53, the second iteration explores the first half of the array with positions 0, ..., 6. The search key is compared with the element a[ 3 ] = 33 in the middle position |_(0+6)/2_| = 3. Because 42 > 33, the third iteration explores the second half of the current subarray with positions 4, ..., 6. The comparison with the element a[ 5 ] = 49 in the middle position |_(4+6)/2_| = 5 shrinks the search range to a single item, a[ 4 ] = 42, as in this moment low = high = middle = 4. Because this element is equal to the search key, the algorithm returns the position found (that is, 4). By the way, consider which result will be obtained if the search key is 41.
Figure 55: Binary tree representation of the sorted
array using the binary search.
The sequence of comparisons made by the binary search algorithm is predetermined: the specific sequence used depends on n and on the value of the search key. The comparison structure can be simply described by a binary tree representing a given array. Hopefully, you are familiar with the tree structures so that here it is sufficient to only review the basic terminology.
A tree consists of a set of nodes and a set of directed edges (or branches) connecting pairs of nodes.
A rooted tree contains one node distinguished as the root.
The defining property of an arbitrary tree is that every node c, except the root, is connected by an edge from exactly one node p, called a parent, and c is one of P's children.
The root has no parent.
Nodes having no children are called leaves.
A unique path traverses from the root to each node, the number of edges along it being the path length.
The depth of any node in a tree is the length of the path from the root to the node (thus, the depth of the root is 0 and the depth of any child is 1 more than the depth of its parent).
The height of a node is the length of the path from the node to the deepest leaf (the height of a parent is 1 more than the height of its maximum-height child).
The height of a tree is equal to the height of the root.
The defining property of a binary tree is that each node has at most two children (they are usually referred to as the left and the right child).
For binary searching, each node also contains a record with a key value, and each comparison for a node results in two subtrees having this node as a parent node: the left subtree contains all records with smaller keys and the right subtree contains all records with larger or equal key values. Such a binary tree has a special name: a binary search tree and we will consider it in more detail later, in Section 6. Here, we only show that a binary search is more easily analysed by representing a sorted array as a binary (search) tree.
For such a representation,
the middle element m0 = |_(n-1)/2_|
of the sorted array is considered as the root. The lower subrange 0, ...,
m0-1 and the upper subrange m0+1, ...,
n-1 are associated with the left and the right branches and their
middle elements
mleft,1 = |_(m0-1)/2_| and mright,1
= |_(n + m0)/2_| are considered as the left child
and the right child of the root, respectively. The process of building
such child pairs is repeated until all the elements are associated with
the nodes. The middle element of a current subrange becomes the left child
if its value is less than the parent value or the right child otherwise.
Figure 55 shows such a binary search tree built for the 16 sorted keys in Figure 54. The key value (a[7]=53) is the root of the tree. The lower (0..6) and the upper (8..15) subranges of the search result in two children of the root: the left child a[3]=33 and the right child a[11]=81. All the other nodes are built in a similar way.
Such a representation allows us to interpret a binary search as a pass through the tree from the root to the desired key. If a leaf is reached but the key is not found, then the desired key is not present in the array. Notice that the number of nodes in the unique path from the root to the given key is equal to the number of comparisons made by binarySearch to find this key.
Let us assume, for simplicity, that there are n = 2k-1 items in the sorted array (here, k is some positive integer value). In this case, the binary tree is complete, that is, each internal node has two (left and right) children, the height of the tree is equal to k-1, and each tree level l contains 2l nodes, for l = 0 (root), 1, ..., k-1 (leaves).
The number of comparisons to find a given search key is one more than its level in the tree. Therefore, in the worst case we need to pass through the tree from the root to a leaf, that is, to do k = log2(n+1) comparisons, and the complexity of binary search is O(log n).
The average-case number of comparisons can be computed in a slightly more complex way which involves sums of finite series. Let Ci be one more the level of the search key i in the tree, that is, be equal to the number of comparisons for finding this search key. Suppose all the keys i = 0, ..., n-1 have the same chance of being met. Then, the average number of comparisons is
|
Because we assume that the binary tree is complete and n = 2k-1, there exist 2l nodes of level l. Therefore, the sum S can be rewrited as follows:
|
(because the tree contains one root, 2 children of level 1, 22 children of level 2, and so on, up to 2k-1 leaves of level k-1). This finite series has the following sum:
Sk-1 = 1 + (k-1) ·2k, that can be easily proven by mathematical induction:
Sk = 1 + (k-1) ·2k + (k+1) ·2k = 1 + k ·2k+1.
Therefore,
|
and the average-case complexity of binary search is O(log n), too.
You can slightly speed up binary search by removing the test for
a successful search (lines 19-20 in Figure 53)
from the inner loop and by shrinking the range down to one item in all
cases. Then, a single test outside the loop determines if the item is present
in the array or is not found (see Figure 56).
In this method, if the desired element is not larger than the element in
the middle position, then it is in the range low - middle.
When the loop is broken, the subrange is 1 (that is, low = high),
and it is possible to test if there is a match.
1 /**
2 * Faster binary search in an integer array a[]
3 * Returns index where an item is found or
4 * throws an ItemNotFound exception
5 */
6 public static int binarySearch( int[] a ,
7 int key) throws ItemNotFound {
8 if( a.length == 0 )
9 throw new ItemNotFound( "Zero-length array" );
10
11 int low = 0;
12 int high = a.length - 1;
13 int middle;
14
15 while( low < high ) {
16 middle = ( low + high ) / 2;
17
18 if( a[ middle ] < key )
19 low = middle + 1;
20 else
21 high = middle;
22 }
23 if( a[ low ] == key )
24 return low;
25 throw new ItemNotFound( "BinarySearch fails" );
26 }
In the accelerated method, the number of iterations is always |_log n_| because the range is always shrunk in half, if necessary, by rounding down. Thus, the number of comparisons that are used is always |_log n_| + 1.
For small n, say, n < 6,
a binary search is even less efficient than a sequential search. But,
for larger n, a binary search notably outperforms a sequential
one due to its logarithmic time complexity. One improvement possible in
binary search is to try to guess more precisely where the desired key may
sit in the array (rather than blindly using the middle element at each
step). You behave in a similar way when looking up a number in the telephone
directory: if the name to be found begins with ``B'', you look near the
beginning, but if it begins with ``Y'', you look near the end.
A static searching method that exploits this idea and is sometimes faster than binary search is called an interpolation search. It can be practical if two assumptions are satisfied:
These assumptions are quite restrictive, so you might never use an interpolation
sort. But, this algorithm shows that there is more than one way to solve
a problem and that no algorithm is the best in all situations.
The interpolation search requires only a simple modification to the binary search in Figure 53 that computes the midpoint of the range to specify the new place to search:
|
The computation of the middle of the range can be considered as adding half the size of the range to the left endpoint. Interpolation search simply replaces 1/2 in the above formula by an estimate of a relative position, where the desired key might be, based the values available:
|
if high > low. If the key sought were in the middle of the range between low and high, then r = 1/2 and the next item to access:
|
would be appropriate, but otherwise, assuming that the key values are evenly distributed in the range, the next item
|
might be a better guess.
It is possible to prove that, under the assumption that the keys are uniformly distributed, the average-case complexity of interpolation search is O(log log n). More precisely, this search uses fewer than log log n comparisons for both successful and unsuccessful search. The proof of this fact is quite complicated so that it is beyond the scope of this paper.
But you must take into account that in the worst case, where the keys are not uniformly distributed, the running time could be linear (O(n)) and every item might be examined. For instance, take the ten following keys in the range [0, ..., 100]:
|
and the search key is 20. Because these keys are not uniformly distributed, the interpolation search has to examine sequentially all the positions (indices in the array) 1, 2, ..., 8 as the next ones until the desired position 9 is found. In the table below, the low and the high ends of the current search range are shown in italic, and the computed next position is boldfaced:
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | next |
| Step 1 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 20 | 100 | 1= 0 + |-[(20-10)/( 100-10)] ·9-| |
| Step 2 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 20 | 100 | 2= 1 + |-[(20-11)/( 100-11)] ·8-| | |
| Step 3 | 12 | 13 | 14 | 15 | 16 | 17 | 20 | 100 | 3= 2 + |-[(20-12)/( 100-12)] ·7-| | ||
| Step 4 | 13 | 14 | 15 | 16 | 17 | 20 | 100 | 4= 3 + |-[(20-13)/( 100-13)] ·6-| | |||
| Step 5 | 14 | 15 | 16 | 17 | 20 | 100 | 5= 4 + |-[(20-14)/( 100-14)] ·5-| | ||||
| Step 6 | 15 | 16 | 17 | 20 | 100 | 6= 5 + |-[(20-15)/( 100-15)] ·4-| | |||||
| Step 7 | 16 | 17 | 20 | 100 | 7= 6 + |-[(20-16)/( 100-16)] ·3-| | ||||||
| Step 8 | 17 | 20 | 100 | 8= 7 + |-[(20-17)/( 100-17)] ·2-| | |||||||
| Step 9 | 20 | 100 | return value: 8 | ||||||||
Thus, the time complexity of interpolation search does depend heavily on the distribution of the keys over the range. Also, there are extra computations to find the next positions. As a result, interpolation search should be considered only for large and sufficiently uniform arrays and for such applications where comparisons are particularly expensive or where very high access costs are involved (say, searching in an external disk memory).
You studied these trees last year and also have met them just in the previous Section 5 where they have been used for analysing binary search performance. Here, we analyse the time performance of operations with this simple data structure. This structure makes it possible to convert a static binary search into an efficient dynamic binary tree search which allows for inserting and deleting data items. In a binary search, we used binary trees only to describe the sequence of comparisons and to facilitate performance analysis. In a binary tree search, this data structure is actually constructed (by linking the data items) and used for the search. Below, we will not consider a Java implementation of a binary search tree itself and operations with this structure because, if necessary, you can find the detailed description of this software in the recommended textbook by Mark A. Weiss.
As in the previous section, an item, or element, of an array of records is searched for by its (numerical) key. For simplicity sake, we assume that each record contains only its integer key so that the search is for a given integer within a particular integer array. The more general case of Comparable items you will find in the textbook by Mark A. Weiss.
A binary search tree is a binary tree that satisfies the following search order property:
For every node x in the tree, the values of all the keys in the left subtree are smaller than the key in x and the values of all the keys in the right subtree are larger than the key in x.
It is quite simple to ensure that binary search trees built by successively inserting new nodes satisfy this defining property.
Figure 57: Binary trees: only the leftmost tree
is a binary search tree.
In Figure 57, only the leftmost tree is a binary search tree; the two other trees are not (because key 2 does not belong in the right subtree of key 3 in the middle tree and keys 11 and 12 do not belong in the left subtree of key 10 in the rightmost tree).
The above search order property means that all the items can be put into sorted order by a particular traversal of the tree. Notice that the property does not allow duplicate items (for exact duplicates, you should have one item and attach the number of duplicates to it).
Basic operations to be performed with a binary search tree are as follows:
Figure 58: Examples of find and insert
operations in the binary search tree.
It is obvious that the first operation (find) resembles a
usual binary search: starting at the root, it branches repeatedly either
left or right, depending on the result of a comparison. Let us find the
key 8 within the leftmost tree in Figure 57. In
so doing, we start at the root 10 and go left (because 8 <
10). This takes us to 3, so we go right (8 >
3) to 5. Then we go right again (8 > 5)
and encounter 8. To find 7, we repeat just the same path. But, when we
are at 8, we would go left - and there is no such link so that we encounter
a null reference. Thus, 7 is not found. Figure 58
illustrates both examples and shows that 7 can be inserted at the point
at which the unsuccessful search terminates.
In other words, the find and the insert operations are somehow complementary. The operation find returns the desired node containing the matched item if the search has been successful. Otherwise it can throw a user-defined new exception ``ItemNotFound'' or simply return null. The operation insert creates and returns a new node in a binary search tree if the search has been unsuccessful. Otherwise it can throw a user-defined new exception ``DuplicateItem'' or call a user-supplied method doIfEqual(). Both these new exception classes you have met before, in Section 1 (see Figure 19).
The findMin and findMax operations are extremely simple
in a binary search tree. A findMin starts at the root and
repeatedly branches left as long as a left child exists. The stopping
point is the smallest element. A findMax is similar, except for
branching to the right.
Notice that the sort operation is very simple when binary search
trees are used, due to the defining property of these trees: the root of
the tree plays the role of a pivot element in Quicksort (no larger keys
to the left and no smaller keys to the right). Specifically, a
recursive traversal of the tree like Quicksort (that is, ``first visit the
left subtree, then visit the root, then visit the right subtree'') will
sort the items.
The running times of all the above operations are quite dependent on the shape of trees. In the best case, the tree could be shaped like Figure 59, with about log n depth (that is, number of edges between the root and each leaf). But the worst case shown in Figure 60 has the depth about n. Thus, just as in Quicksort, you may expect logarithmic search/insert running times on the average and linear running time in the worst case.
The operation remove is most complex one because the removal of an internal node may disconnect parts of the tree. The reattachment of the tree must maintain the binary search tree property and also should not make the tree unnecessarily deeper as the depth of the tree specifies the running time of the tree operations.
Let parent(x) denote the parent of a node with key x. Let lchild(x) and rchild(x) be the left child and the right child of the node with key x, respectively. The following operation is usually implemented to remove the node with key k:
|
||||||
Thus, the operations removeMin and removeMax are not complex because the affected nodes are either leaves or have only one child.
Figure 61 illustrates this operation.
Figure 61: Removal of the node with key 10 from
the given binary search tree.
Although this approach seems asymmetric and rather ad hoc, various suggested modifications give no differences in practical applications.
If you need to find the k-th smallest element for an arbitrary
K, a binary search tree allows this, too. In so doing, we must
keep track of the size of each node in the tree. The size of a node is
defined as the number of its descendants including itself.
For simplicity, the findKth operation is explained below as a recursive one although it can be implemented without recursion. Suppose the K-th smallest element (1 <= K <= n) has to be found in a binary search tree with n nodes. There are three possible cases, depending on the relation of K and the size of the left subtree, which is denoted SL (the size of subtree is equal to the size of its root):
Figure 62 illustrates this approach (here, the sizes of the nodes are given in italic). The root node contains the 6th smallest element, and its left subtree possesses the size SL = 5. Also, the 4th smallest element, 3, has the size 3 of its left subtree, and the 9th smallest element, 10, that must be the 3rd smallest element in the right subtree (3 = 9-5-1) has the size 2 of its left subtree.
It is easy to maintain the node sizes during tree changes. The insert operation increases by 1 the size of each node on the path to the insertion point, and the inserted node has the size 1. The removeMin operation decreases by 1 the size of each node on the path to the minimum. During the remove operation, the size of all nodes on the path to the node that is physically removed are also decreased by 1. Thus, maintenance needs only a small computational overhead.
The cost of each operation is proportional to the number of nodes accessed during the operation. Figures 59 and 60 suggest that if the tree is perfectly balanced (in terms of relative sizes of left and right subtrees), then the best search time is logarithmic O(log n). But, in practice the tree may be heavily unbalanced as in Figure 60 where all n nodes are on the path to the deepest node. So in the worst case the search time is linear O(n).
Let us estimate the average-case performance under the assumption that each tree is created by random insert sequences but with no remove operations. Figures 63, 64, and 65 show results of inserting four items 1, 2, 3, 4 into an empty binary search tree. Because only relative ordering is important, this corresponds to any keys such that
|
Figure 63: Binary search trees obtained by inserting
permutations of 1,2,3,4 (a).
Figure 64: Binary search trees obtained by inserting
permutations of 1,2,3,4 (b).
Figure 65: Binary search trees obtained by inserting
permutations of 1,2,3,4 (c).
There are 4! = 24 possible insertion orders presented in italic in Figures 65 - 63. Notice that some trees result from several insertion sequences and the more balanced trees in Figure 64 are more frequent than unbalanced ones. To prove the latter statement, let us define the total internal path length of a binary tree as the sum of the depths of its nodes. The average depth of a node, obtained by dividing the total internal path length by the number n of nodes in the tree, gives the average cost of a successful search in the tree. The average-case cost involves the computation of the average total internal path length where the average is taken over all input permutations assuming that they are equally likely.
We are going to prove that the total internal path length of a binary search tree is O(n log n) on the average. Let T(n) be the average total internal path length for trees with n nodes. It is obvious that T(1) = 0. An n-node tree contains an i-node left subtree, a root at depth 0, and a (n-i-1)-node right subtree where 0 <= i < n. By assumption, each value of i is equally likely. For a given i, T(i) is the average total internal path length of the left subtree with respect to its root and T(n-i-1) is the like total path length in the right subtree. Because the root of the tree contributes 1 to the path length of each of the other n-1 nodes in the tree, the following recurrence holds:
|
or, after averaging,
|
Just the same recurrence we had for the average-case Quicksort analysis in Section 4, so that an average total internal path length is O(n log n) and, therefore, the average-case time complexity of the find operation is O(log n).
It is easily shown in a similar way that the average-case complexity of the insert operation is also O(log n). There are no general theoretical estimates for the remove operation although it has been shown that n2 pairs of random insert/remove combinations in a random binary search tree result in an expected depth of O(n½). In practice, it can be assumed that, for random input, all operations are about O(log n). But the worst-case performance in a binary search tree with n keys can be O(n), and this is completely unacceptable in practical applications.
With Quicksort, we tried to eliminate the worst cases by choosing a random pivot and relying then on the small probabilities of encountering bad cases. Fortunately, for binary tree searching there exists a general technique that guarantees that the worst case cannot occur. This technique, called balancing, is based on additional structural conditions that do not allow the nodes to get too deep and excludes, therefore, the worst cases.
Balanced binary search trees are more complicated than the standard binary search trees so that insert and remove operations take usually more time on average. But due to their balanced structure, both the average-case and the worst-case complexity are about O(log n) (in other words, their total internal path lengths are close to the optimal n log n).
An AVL tree is a binary search tree with the additional balance property that, for any node in the tree, the height of the left and right subtrees can differ by at most 1. The height of an empty subtree is -1.
This (historically first) balanced binary search tree was proposed in 1962 by G. M. Adelson-Velskii and E. M. Landis. Its balance condition is quite easy to maintain, and it ensures that the depth of the tree is O(log n). Notice that the strict balance condition of the same heights for the left and right subtrees is too restrictive to maintain when inserting new items. The AVL-balance condition is weaker but still strong enough to guarantee logarithmic depth.
To prove this, let us show that an AVL tree of height h has at
least ch nodes for some constant
c > 1. Then the maximum depth of an
n-item tree is given by logcn. Really, an AVL
tree of height h has at least Fh+3-1
nodes (here, Fi is the i-th Fibonacci number).
You may recall that these numbers are defined as follows: F0
= 0, F1 = 1, and Fi = Fi-1
+ Fi-2, and that Fi ~ fi
· 5-½ where f = (1 + 5½)/2
~ 1.618 is the well-known ``golden ratio''.
The proof is rather straightforward. Let Sh be the size of the smallest AVL tree of height h (it is obvious that S0 = 1 and S1 = 2. The smallest AVL tree of height h has subtrees of height h-1 and h-2 because at least one subtree has height h-1 and height of the second subtree can differ by at most 1 (the balance condition). These subtrees must also be the smallest AVL (sub)trees, so Sh = Sh-1 + Sh-2 + 1. It can be easily shown by mathematical induction that Sh = Fh+3-1 (as S0 = F3-1 and Si+1 = (Fi+3 - 1) + (Fi+2 - 1) + 1 = Fi+4 - 1). Therefore, for each AVL tree with n nodes
|
so that the height of an AVL tree with n nodes satisfies
|
(here, as before, log stands for log2). So the worst-case height is at most 44% more than the minimum possible for binary trees. Although there are no theoretically established estimates, in practice the average-case depth of a randomly constructed AVL tree is very close to log n.
As a result, all searching operations in an AVL tree have logarithmic worst-case performance. But the insert and remove operations that change the tree are rather complex because they must restore the balance if it was destroyed by inserting or deleting a node. This can be done by a special rotation of the tree that switches the roles of the parent and child while maintaining search order. But such a balancing is not computationally efficient (see details in Section 18.4 of the textbook of Mark A. Weiss), so that in practical application other (and better) balanced search trees are implemented, in particular, top-down 2-3-4 trees and their binary tree representation by red-black trees, 2-3 trees, bottom-up 2-3-4 trees, and AA-trees.
A red-black tree is a binary search tree with the following ordering properties:
Because every path from the root to a leaf contains b black nodes, then there are at least 2b-1 black nodes in the tree. To prove this relation by induction, notice that it is valid for b = 1 because in this case the tree contains either the (black) root node only or the (black) root and one or two red children. Let the assumption be valid for all red-black trees with b black nodes in every path. If a tree contains b+1 black nodes in every path and has two black children of the root, then the tree contains at least 2 ·(2b-1) + 1 = 2b+1 - 1 black nodes. If there is a red child of the root, it has necessarily only black children, so that the total number of the black nodes can be even larger.
Because there cannot be two consecutive red nodes on a path, the height of a red-black tree is at most 2·log(n + 1), and the search operation is logarithmic (O(log n)). If you use such a search to find a key in an array of 500,000 records, it will be found by comparing against only about 20 other keys. In a bad case, you may need about 40 comparisons, but no more. Each comparison involves very little overhead, so a very fast search is assured.
A precise average-case performance analysis is yet to be done but there are convincing results of partial analyses and simulations that allow to state the following properties:
The real significance of the red-black trees is that their worst-case performance is achieved at very little cost. But a software implementation of the insert and, especially, remove operations is a rather tricky process due to a host of possible rotations. A simple but competitive balanced search AA-tree is considered as the method of choice if deletions are needed. The AA-tree adds one extra condition to the red-black tree: left children may not be red. This restriction greatly simplifies the red-black tree remove operation.
The B-tree, proposed in 1972 by R. Bayer and E. McCreight, is a popular structure for implementing ordered databases on external memory such as disk units. You must take into account that the previous ``Big-Oh'' analysis is not valid here because it assumes that all operations are equal with respect to time complexity. This is not true when disk i/o is involved: typically, one disk access is worth 200,000 instructions, so that it is the number of disk accesses that dominate the running time. If you have to work with large databases of many millions of records, then even the logarithmic worst-case performance of searching, say, in a red-black tree, is unacceptable. You need a search with a very small number of disk accesses, such as three or four, even if the computations involved are reasonably complex (as the instructions are essentially free).
A binary tree search cannot solve the problem because even optimal tree height is log2 n. To have less height, we need more branching: an optimal m-ary search tree that allows m-way branching has height that is roughly logm n:
| n | 105 | 106 | 107 | 108 | 109 |
| |-log2n-| | 17 | 20 | 24 | 27 | 30 |
| |-log10n-| | 5 | 6 | 7 | 8 | 9 |
| |-log100n-| | 3 | 3 | 4 | 4 | 5 |
| |-log1000n-| | 2 | 2 | 3 | 3 | 3 |
Therefore, m-way branching lowers the optimal tree height
by a factor of log2m (for instance, approximately by the
factor 6.6 if m = 100).
A multiway search tree of order 4 is exemplified in
Figure 66.
Note that searching and traversal in a multiway search tree are simple
generalisations of the corresponding operations for binary search trees.
In a binary tree, the comparison of the search key with a single key in a node
chooses which of two branches to take, or to stop in this
node. In an m-ary search tree, at most m-1 keys are used
to decide which branch to take. The major difference is that the data records
are associated only with leaves (some B-trees relax this condition),
so that the worst-case and average-case
searches involve the tree height and the average leaf depth, respectively.
Searching for a key x in the tree shown in Figure 66
is governed by given thresholds. For instance, at the root the search goes
left if x < 4, down if 4 <= x
< 10, and right if x >= 10. The
like comparisons are repeated at every node until the record with the desired
key is found at a leaf or its absence in the database is detected. Let
x = 17. First, the search goes right from the root (as 17 >
10), then goes to the third child of the right internal node (as
17 <= 17 < 20), and finally finds the
desired record in this leaf.
A B-tree of order m is defined as an m-ary balanced tree with the following properties:
B-trees are usually named after their allowable branching factors, that is, |-m/2-|-m. For example, 2-3 trees are B-trees with m = 3, 6-11 trees are B-trees with m = 11, and so on.
Figure 67: B-tree of order m = 4 with storage
size l = 7: 2..4 children per node and 4..7 data items per leaf.
An example of a B-tree of order 4 is shown in Figure 67. Notice that all nonleaf nodes have between |-4/2-| = 2 and 4 children and thus between 1 and 3 keys. Parameter l specifies the number of data items (or records) associated with a leaf. Because in this example l = 7, each leaf has between |-7/2-| = 4 and 7 data items.
Requiring nodes to be at least half full guarantees that the B-tree does not degenerate into a simple binary or ternary tree when m >= 8. You may encounter other definitions of B-trees (mostly with minor changes) but the above one is one of the most popular forms. The first three defined conditions make it possible to allocate a fixed amount of memory to each node (first of all, space for m links and m-1 keys), yet be sure of wasting less than half of it, except possibly in the root. The last two conditions ensure a very well-balanced tree.
B-trees of order m = 3, or 2-3 trees, have only two or three children per node and are useful for implementing ordered symbol tables in internal computer memory (RAM). B-trees on disk units may have m = 256 or more, chosen so that one node fits neatly into one disk block. This makes for a very shallow tree, which allows for a 8-fold or more decrease in the number of nodes examined (and hence the number of disk accesses) as compared to a binary tree search. In each particular case, parameters m and l must be chosen based on the size of a disk block and of the items to be stored.
For instance, suppose one disk block holds 8,192 bytes, each key uses 32 bytes, and each branch is given by the number of another block which is a 4-byte integer. In a B-tree of order m, each nonleaf node contains m-1 keys and m branches, in all, 32m-32+4m = 36m-32 bytes. The largest value for m for which 36m-32 <= 8,192 is m = 228. Let one data item (data record) contain 256 bytes. Then, l = 32 records can fit in a block. In this case, each leaf addresses from 16 to 32 data items, and each internal node, except the root, branches in at least |-228/2-| = 114 ways. Suppose the database size is 10,000,000 records. The number of leaves is at most n = 10,000,000/32 = 312,500 leaves, so that in the worst case leaves would be on level |-log114312,500-| + 1 = |-2.67-| + 1 = 4.
Generally, a search or an insertion in a B-tree of order m with
n data items is guaranteed to require fewer than |-logm/
2n-| disk accesses, a constant number for practical
purposes as long as m is not small. It may be even less if the root
and the first tree level are stored in main memory, so over the long run
disk accesses would be needed only for level 3 or deeper. Notice that a
three-level B-tree with m = 228 can handle up to 2283,
or over 11.85 million, entries. If, in the above example, each key uses
only 4 bytes, then m = 1024, and the three-level tree can handle
over a billion entries (note that there are only 4 billion different
4-byte keys so the full tree would have a large proportion of the
possible keys).
Data insertion in a B-tree is simple if the corresponding leaf is not already full. In the latter case, the leaf is split into two leaves, both having the minimum number of data items needed, and the parent has to be updated. If necessary, such a splitting is propagated up until a parent that does not need to be split is found or the root is reached. Only in the very rare case that the root has to be split, does tree gain height and a new root with two children (namely, parts of the split previous root) is created. Data deletion is also simple until the leaf is empty and it is necessary to combine the neighbours to form a full leaf. But, although the program code is certainly not simple, all these changes are well controlled. Moreover, an algorithm analysis that is beyond the scope of our paper shows that additional disk writes for these operations are so rare that both insertions, deletions, and retrievals of data have only about logm/2 n disk accesses in the worst case.
import java.awt.*;
import java.awt.event.*;
import java.util.*;
import java.io.*;
import Methods.*; // package with SortMeth class(sort methods)
import Assigns.*; // package with TestMeth class(sort methods;
// you should insert your own program here)
public class TestBench extends Frame
implements ActionListener {
static public TextArea textarea; // to display messages
static public TextField textArraySize; // to input parameters
static public TextField textShrink; // input combSort param
static public TextField textPowerN; // input power N
static private Panel westPanel; // to place textarea
static private Panel northPanel; // input param components
static private Panel eastPanel; // to place graphic panel
static private Panel upperNorthPanel; // place input of params
static private Panel downNorthPanel; // for complexity params
static private Panel coverEastPanel; // to place graphic canvas
static private Panel southButtonBoxPanel;// place control buttons
static private Canvas graphicCanvas; // draw timing graphs and
static private Canvas supplemCanvas; // their fitting curves
static private Graphics mg; // graphics object
static private int itemsToSort; // data size to sort
static public int [] inputData = new int[100]; // data to sort
static public int [] dataToSort = new int[100];
static private double xPoints [] = new double[10]; // size N
static private double yPoints [] = new double[10]; // sort time(N)
static private double yApprox [] = new double[10]; // fit a*F(N)+b
static private double yFuncN [] = new double[10]; // F(N)=N*N,...
static private int xDrawPoints[] = new int [10]; // x-coord (draw)
static private int yDrawPoints[] = new int [10]; // y-coord (draw)
static private int yDrawApprox[] = new int [10]; // y-fitted value
static private double yApproxMin; // bounds for fitting data
static private double yApproxMax;
static private boolean onlyClearCanvas = true; // clear 2 canvas?
static private boolean inAnApplet = true; // does window exist?
static private boolean isApproxData = false; // fit time data?
static private boolean isLogN = false; // is factor logN in F(N)?
static private double powerN; // is N^(powerN) in F(N)
static private int test = 0; // current test number
static private int minTime; // min and max sort time
static private int maxTime;
static private double combShrink; // SHRINK param for CombSort
static private double minX; // coord bounds to draw
static private double maxX; // time curves
static private double minY;
static private double maxY;
static private final int wOval = 4; // dot size to draw a curve
static private final int hOval = 4;
static private final int dataSizeMin = 100; // min size to sort
static private final int defaultSize = 10000; // default size N
static private final int bigIntValue = 2000000000;
static private final int widthPrintedChar = 6; // print char size
static private final int heightPrintedChar = 8;
static private final int heightGraphics = 300; // Canvas size
static private final int widthGraphics = 400;
static private final int heightTextarea = 20; // Textarea size
static private final int widthTextarea = 40;
static private final double numRange = 10000.; // rand num scale
static private final double precPrint = 100.; // print precision
static private final double defaultShrink = 1.1; // default SHRINK
static private Label graphTitleLabel; // graph title
static private Label dataSizeLabel; // data size label
static private Label combShrinkLabel; // SHRINK parameter label
static private Label powerNlabel; // power of N label
static private Checkbox insertLogN; // to insert logN in F(N)
static private Choice choice; // to choose sort method
static private MenuBar menubar; // menu bar
static private Menu dataSource; // menu (data source)
static private Menu help; // help menu
static private MenuItem file; // data source:file
static private MenuItem form; // data source:rand numbs
static private MenuItem quit; // quit program
static private MenuItem about; // information about program
// Class constructor
public TestBench( String title ) {
super( title ); // Set frame title.
// Detect window activate/close events
this.addWindowListener ( new WindowAdapter() {
public void windowActivated( WindowEvent e ) {
show();
}
public void windowClosing( WindowEvent e ) {
dispose();
System.exit(0);
}
});
startingData(); // Set starting values to draw graphs
// default font
this.setFont( new Font( "SanSerif", Font.PLAIN, 12 ) );
// create the menubar and tell the frame about it.
menubar = new MenuBar();
this.setMenuBar( menubar );
// create the file menu and add to menubar.
dataSource = new Menu( "DataSource" );
menubar.add( dataSource );
// create three items for data menu, set their labels,
// shortcuts, action commands and listeners, add them
// to menu. Frame itself is the action listener
file = new MenuItem( "File", new MenuShortcut( KeyEvent.VK_F ) );
file.setActionCommand( "file" );
file.addActionListener( this );
dataSource.add( file );
form = new MenuItem( "Form", new MenuShortcut( KeyEvent.VK_O ) );
form.setActionCommand( "form" );
form.addActionListener( this );
dataSource.add( form );
quit = new MenuItem( "Quit", new MenuShortcut( KeyEvent.VK_Q ) );
quit.setActionCommand( "quit" );
quit.addActionListener( this );
dataSource.add( quit );
// create Help menu; add an item; add to menubar
// display Help menu in a special reserved place.
help = new Menu( "Info" );
menubar.add( help );
menubar.setHelpMenu( help );
// create and add an item to the Help menu
about = new MenuItem( "About", new MenuShortcut( KeyEvent.VK_A ) );
about.setActionCommand( "about" );
about.addActionListener( this );
help.add( about );
// contents of the frame ( layout: north,(west,center,east),south )
this.setLayout( new BorderLayout( 5, 5 ) );
// panels to contain components (northPanel contains 2 subpanels)
northPanel = new Panel( new BorderLayout() );
this.add( northPanel, "North" );
upperNorthPanel = new Panel( new FlowLayout( FlowLayout.LEFT, 5, 5));
northPanel.add( upperNorthPanel, "North" );
downNorthPanel = new Panel( new FlowLayout( FlowLayout.LEFT, 5, 5));
northPanel.add( downNorthPanel, "South" );
eastPanel = new Panel( new FlowLayout( FlowLayout.LEFT, 5, 5));
this.add( eastPanel, "East" );
westPanel = new Panel( new FlowLayout( FlowLayout.LEFT, 5, 5));
this.add( westPanel, "West" );
// a south panel to contain buttons at the bottom of the window
southButtonBoxPanel = new Panel(new FlowLayout(FlowLayout.LEFT,5,5));
this.add( southButtonBoxPanel, "South" );
// fill the upperNorthPanel and handle events on the TextField
textArraySize = new TextField( 10 );
dataSizeLabel = new Label( "Enter array size:" );
upperNorthPanel.add( dataSizeLabel );
upperNorthPanel.add( textArraySize );
dataSizeLabel.setVisible( true );
textArraySize.setText("");
textArraySize.setVisible( true );
// get an integer array size itemsToSort from the textfield
// ( itemsToSort == N in the complexity function F(N) )
textArraySize.addActionListener( new ActionListener( ){
public void actionPerformed( ActionEvent e ) {
try {
itemsToSort =
Integer.parseInt( ((TextField)e.getSource()).getText() );
inputData = new int[ itemsToSort ];
}
catch (NumberFormatException exc) {
textarea.append( "Invalid number! Set size = " +
defaultSize + "\r" );
itemsToSort = defaultSize;
inputData = new int[ itemsToSort ];
}
catch (OutOfMemoryError err) {
textarea.append( "Too big array! Set size = " +
defaultSize + "\r" );
itemsToSort = defaultSize;
inputData = new int[ itemsToSort ];
}
finally {
textArraySize.setText( "" );
textArraySize.setText( Integer.toString( itemsToSort ) );
int sortMax = -bigIntValue;
int sortMin = bigIntValue;
// form random array to sort
for ( int i = 0; i < itemsToSort; i++ ) {
inputData[ i ] =
(int)Math.round( numRange * Math.random() );
if ( sortMax < inputData[ i ] ) sortMax = inputData[ i ];
if ( sortMin > inputData[ i ] ) sortMin = inputData[ i ];
}
}
}
} );
// get double parameter of combSort from its textfield
// and assign it to the SHRINK field of the class TestMeth
textShrink = new TextField( 10 );
combShrinkLabel = new Label( " Enter SHRINK (CombSort): " );
upperNorthPanel.add( combShrinkLabel );
upperNorthPanel.add( textShrink );
textShrink.setText( "" );
textShrink.addActionListener( new ActionListener( ) {
public void actionPerformed( ActionEvent eparam ) {
try {
combShrink = ( Double.valueOf (
( (TextField) eparam.getSource() ). getText() )
).doubleValue();
if( combShrink <= 1. ) combShrink = defaultShrink;
}
catch (NumberFormatException exc) {
textarea.append( "Invalid parameter! Set SHRINK = " +
defaultShrink + "\r" );
combShrink = defaultShrink;
}
finally {
textShrink.setText( "" );
TestMeth.SHRINK = combShrink;
textShrink.setText( Double.toString( combShrink ) );
}
}
} );
// get double power N for fitting obtained time curve
// by F(N) = a * (N^powerN or (N^powerN) * logN) + b
textPowerN = new TextField( 10 );
powerNlabel = new Label( "Enter power of N:" );
downNorthPanel.add( powerNlabel );
downNorthPanel.add( textPowerN );
powerNlabel.setVisible( true );
textPowerN.setText("");
textPowerN.setVisible( true );
textPowerN.addActionListener( new ActionListener( ){
public void actionPerformed( ActionEvent e ) {
try {
powerN =
( Double.valueOf ( ( (TextField) e.getSource() ).
getText() ) ).doubleValue();
}
catch (NumberFormatException exc) {
textarea.append( "Invalid number!\r" );
powerN = 1.;
}
finally {
textPowerN.setText("");
textPowerN.setText( Double.toString( powerN ) );
}
}
} );
// button to insert or delete logN factor of F(N)
insertLogN = new Checkbox("Log N", false );
downNorthPanel.add (insertLogN );
ItemListener checkbox_listener = new ItemListener() {
public void itemStateChanged( ItemEvent e ) {
isLogN = ((Checkbox)e.getItemSelectable()).getState();
}
};
insertLogN.addItemListener( checkbox_listener );
// create dropdown list (option menu) of sorts to be tested
choice = new Choice();
choice.add( "InsertionSort" );
choice.add( "BubbleSort" );
choice.add( "CombSort" );
choice.add( "ShellSort" );
choice.add( "MergeSort" );
choice.add( "QuickSort" );
choice.add( "HeapSort" );
southButtonBoxPanel.add( choice );
southButtonBoxPanel.add( new Label(
"<--Sorting methods to test " ) );
// handle events of the sort method choice
choice.addItemListener( new ItemListener() {
public void itemStateChanged( ItemEvent e ) {
boolean allRight = true;
onlyClearCanvas = true;
paint( mg ); //redraw graphics in the window
onlyClearCanvas = false;
graphTitleLabel.setText( " Time graphs (in ms) ");
long timeTest = 0;
int dataSize = itemsToSort;
double factor = 0.;
if ( dataSize >= dataSizeMin ) {
factor = 1.0;
minTime = bigIntValue;
maxTime = 0;
// set off time graph fitting by F(N) =
// a * ( N^powerN or (N^powerN)*logN ) + b
isApproxData = false;
// text output to the left textarea
textarea.append( "\r\r******** Test " + test + ": "+
(String)e.getItem() + " ********\r" );
if( ((String)e.getItem()).equals("CombSort") )
textarea.append(
"-------- SHRINK = " + TestMeth.SHRINK + "\r" );
if( ((String)e.getItem()).equals("QuickSort") )
textarea.append(
"-------- CUTOFF = "+ SortMeth.CUTOFF + "\r" );
test++;
// sorting data arrays of different size; when
// xPoints.length = 10 then N, 0.9*N, 0.8*N, ..., 0.1*N
double decrement = 1. / (double)xPoints.length;
for ( int i = xPoints.length-1; i >= 0; i-- ) {
dataSize = (int) ( (double) itemsToSort * factor );
try {
dataToSort = new int[ dataSize ];
for ( int j = 0; j < dataSize; j++ )
dataToSort[ j ] = inputData[ j ];
// get time taken by chosen sorting method
// for random array of size dataSize
timeTest = testSortingMethod( (String)e.getItem() );
factor -= decrement;
// fill x- and y-data for drawing time curve
xPoints[ i ] = (double)dataSize;
yPoints[ i ] = (double)timeTest;
if ( minTime > timeTest ) minTime = (int)timeTest;
if ( maxTime < timeTest ) maxTime = (int)timeTest;
textarea.append(
" Array["+dataSize+"]: time " + timeTest + "ms\r");
}
catch ( OutOfMemoryError err ) {
textarea.append(
"Insufficient memory size! Stop testing\r" );
allRight = false;
break;
}
}
if ( allRight ) {
if ( minTime > timeTest ) minTime = (int)timeTest;
if ( maxTime < timeTest ) maxTime = (int)timeTest;
textarea.append("Min time " + minTime + "ms; max time "
+ maxTime + "ms.\r");
graphTitleLabel.setText(
"Time graphs (in ms): "+ (String)e.getItem() );
graphicCanvas.setVisible( true );
supplemCanvas.setVisible( true );
}
else
textarea.append( "Try smaller data arrays!\r" );
}
else {
textarea.append( "Too small array [" + dataToSort.length
+ "] to test sorts\r" );
textarea.append( "Try larger data arrays!\r" );
}
}
} );
// create multi-line text area in the westPanel panel
textarea = new TextArea( heightTextarea, widthTextarea);
westPanel.add( textarea );
// create graphics panel coverEastPanel and canvas:
// graphicCanvas to draw time curve and fitting curve &&
// supplemCanvas to draw x-coord numerical values
coverEastPanel = new Panel( new BorderLayout() );
coverEastPanel.setBackground( Color.cyan );
coverEastPanel.setForeground( Color.black );
graphTitleLabel = new Label(
" Time graphs (in ms) ", Label.CENTER );
coverEastPanel.add( "North", graphTitleLabel );
graphicCanvas = new Canvas();
graphicCanvas.setSize( widthGraphics, heightGraphics );
graphicCanvas.setBackground( Color.cyan );
graphicCanvas.setForeground( Color.black );
coverEastPanel.add ( "Center", graphicCanvas );
supplemCanvas = new Canvas();
supplemCanvas.setSize(
widthGraphics, 2 * (heightPrintedChar + 4) );
supplemCanvas.setBackground( Color.cyan );
supplemCanvas.setForeground( Color.black );
coverEastPanel.add ( "South", supplemCanvas );
eastPanel.add ( coverEastPanel );
onlyClearCanvas = true;
paint( mg ); // draw graphics
// create pushbuttons and add to the southButtonBoxPanel
// Quit - to quit program; Graphics - to draw time curve,
// Approx - to fit time curve and to draw fitting curve
Button buttonQuit = new Button( "Quit" );
Button graphics = new Button( "Graphics" );
Button approx = new Button( "Approx" );
southButtonBoxPanel.add( buttonQuit );
southButtonBoxPanel.add( graphics );
southButtonBoxPanel.add( approx );
// handle events on the buttons
ActionListener buttonListener = new ActionListener() {
public void actionPerformed( ActionEvent e ) {
if ( (
(Button)e.getSource()).getLabel().equals("Quit") ) {
inAnApplet = false;
dispose();
System.exit(0);
}
else if ( (
(Button) e.getSource() ).getLabel().equals("Graphics") ) {
coverEastPanel.setVisible( true );
paint( mg ); // draw the time curve
}
else if ( (
(Button) e.getSource() ).getLabel().equals("Approx") ) {
coverEastPanel.setVisible( true );
isApproxData = true;
// printing chosen fitting function
if ( isLogN ) {
if ( powerN == 1. )
textarea.append( "Complexity f(N) = N log N\r" );
else
textarea.append( "Complexity f(N) = N^(" + powerN
+ ") log N\r" );
}
else {
if ( powerN == 1. )
textarea.append( "Complexity f(N) = N \r" );
else
textarea.append( "Complexity f(N) = N^(" + powerN
+ ") \r" );
}
// form function F(N) = N^(powerN) if isLogN = false
// or F(N) = N^(powerN) * log N if isLogN = true and
// put F(N) values to the array yFuncN[*]
for( int i = 0; i < xPoints.length; i++ ) {
double currentN = (double) xPoints[ i ];
yFuncN[ i ] = Math.pow( currentN, powerN );
if( isLogN ) yFuncN[ i ] *= Math.log( currentN );
}
// parameters of the Least Square Error approximation
// yApprox(.) = coeffA * yFuncN(.) + coeffB
// giving the best fit to yPoints(.)
double sy = 0.;
double syfN = 0.;
double sfN = 0.;
double sffN = 0.;
for( int i = 0; i < xPoints.length; i++ ) {
sy += yPoints[ i ];
syfN += ( yPoints[ i ] * yFuncN[ i ] );
sfN += yFuncN[ i ];
sffN += ( yFuncN[ i ] * yFuncN[ i ] );
}
double sn = (double) xPoints.length;
double coeffB = sy / sn;
double coeffA = 0.;
double det = sffN * sn - sfN * sfN;
if ( det > 0. ) {
coeffA = ( syfN * sn - sy * sfN ) / det;
coeffB -= coeffA * (sfN / sn);
}
else {
textarea.append( "Singular data to be approximated\r" );
coeffA = coeffB = 0.;
}
textarea.append("LSE-approximated time curve:\r");
textarea.append(" Time(N) = A * f(N) + B\r");
textarea.append(" where A = " + coeffA + ";\r");
textarea.append(" B = " + coeffB + ".\r");
yApproxMin = bigIntValue;
yApproxMax = 0.;
for( int i = 0; i < xPoints.length; i++ ) {
yApprox[ i ] = coeffA * yFuncN[ i ] + coeffB;
if ( i == 0 )
yApproxMin = yApproxMax = yApprox[ 0 ];
else {
if ( yApproxMin > yApprox[ i ] )
yApproxMin = yApprox[ i ];
if ( yApproxMax < yApprox[ i ] )
yApproxMax = yApprox[ i ];
}
}
double printMin = (double)
( (int)( precPrint * yApproxMin ) ) / precPrint;
double printMax = (double)
( (int)( precPrint * yApproxMax ) ) / precPrint;
textarea.append("Approximating time:\r");
textarea.append(" min time " + printMin +
"ms; max time " + printMax +"ms.\r");
paint( mg ); // draw fitting curve
}
}
};
buttonQuit.addActionListener( buttonListener );
graphics.addActionListener( buttonListener );
approx.addActionListener( buttonListener );
}
//Method to draw graphics
public void paint( Graphics mg ) {
Graphics g = graphicCanvas.getGraphics();
Dimension size = graphicCanvas.getSize();
// clear graphicCanvas
g.setColor( Color.cyan );
g.fillRect(0,0,size.width-1,size.height-1);
Graphics dg = supplemCanvas.getGraphics();
Dimension downsize = supplemCanvas.getSize();
// clear supplemCanvas
dg.setColor( Color.cyan );
dg.fillRect(0,0,downsize.width-1,downsize.height-1);
if ( onlyClearCanvas ) return;
if ( itemsToSort <= dataSizeMin ) return;
if ( test <= 0 ) return;
// prepare xy-coordinats for drawing
minX = minY = (double) bigIntValue;
maxX = maxY = 0.;
for ( int i = 0; i < xPoints.length; i++ ) {
if ( minX > xPoints[ i ] ) minX = xPoints[ i ];
if ( minY > yPoints[ i ] ) minY = yPoints[ i ];
if ( maxX < xPoints[ i ] ) maxX = xPoints[ i ];
if ( maxY < yPoints[ i ] ) maxY = yPoints[ i ];
}
if ( isApproxData ) {
if ( minY > yApproxMin ) minY = yApproxMin;
if ( maxY < yApproxMax ) maxY = yApproxMax;
}
// scaling data to draw time curve
double factorX = 0.;
double factorY = 0.;
if ( maxX > minX )
factorX = (double)( size.width - 1 ) / (maxX - minX);
if ( maxY > minY )
factorY = (double)( size.height - 1 ) / maxY;
for ( int i = 0; i < xPoints.length; i++ ) {
xDrawPoints[ i ] =
(int) ( ( xPoints[ i ] - minX ) * factorX );
yDrawPoints[ i ] =
(int) ( yPoints[ i ] * factorY );
if( isApproxData ) yDrawApprox[ i ] =
(int) ( yApprox[ i ] * factorY );
}
// draw rectangle around the graph
g.setColor( Color.white );
// left vertical
g.drawLine( 0, 0, 0, size.height - 1 );
g.drawLine( 1, 0, 1, size.height - 1 );
// upper horizontal
g.drawLine( 0, 0, size.width - 1, 0 );
g.drawLine( 0, 1, size.width - 1, 1 );
// right vertical
g.drawLine( size.width - 1, 0,
size.width - 1, size.height - 1 );
g.drawLine( size.width - 2, 0,
size.width - 2, size.height - 1 );
// down horizontal
g.drawLine( 0, size.height - 1,
size.width - 1, size.height - 1 );
g.drawLine( 0, size.height - 2,
size.width - 1, size.height - 2 );
// draw x-regular/y-irregular coordinate grid
g.setColor( Color.white );
for( int i = 0; i < xDrawPoints.length; i++ ) {
g.drawLine( xDrawPoints[ i ], 0,
xDrawPoints[ i ], size.height - 1 );
g.drawLine( 0, size.height - 1 - yDrawPoints[ i ],
size.width-1,
size.height - 1 - yDrawPoints[i] );
}
// print time values along y-axis
g.setColor( Color.blue );
for ( int i = 0; i < xDrawPoints.length; i++ ) {
String stringY = Integer.toString( (int)yPoints[ i ] );
char [] coordY = stringY.toCharArray();
int posY = size.height - 1 - yDrawPoints[ i ];
if ( posY - heightPrintedChar < 0 )
posY = heightPrintedChar + 1;
g.drawChars( coordY, 0, coordY.length, 1, posY);
}
// indicate x-positions in supplemCanvas canvas
dg.setColor( Color.white );
for ( int i = 0; i < xDrawPoints.length; i++ ) {
if ( i%2 == 0 )
dg.drawLine( xDrawPoints[ i ],
downsize.height/2 - heightPrintedChar,
xDrawPoints[ i ], 0 );
else
dg.drawLine( xDrawPoints[ i ],
downsize.height - 1 - heightPrintedChar,
xDrawPoints[ i ], 0 );
}
// print data array sizes along x-axis
dg.setColor( Color.blue );
for ( int i = 0; i < xDrawPoints.length; i++ ) {
String stringX = Integer.toString( (int)xPoints[ i ] );
char [] coordX = stringX.toCharArray();
int offsetX = coordX.length * widthPrintedChar;
int posX = xDrawPoints[ i ] - offsetX/2;
if ( posX < 0 ) posX = 0;
if ( posX + offsetX > downsize.width - 1 )
posX = downsize.width - 1 - offsetX;
if ( i%2 == 0 )
dg.drawChars( coordX, 0, coordX.length, posX,
downsize.height/2 );
else
dg.drawChars( coordX, 0, coordX.length, posX,
downsize.height - 1 );
}
// draw time curve
g.setColor( Color.black);
for ( int i = 0; i < xDrawPoints.length; i++ )
g.fillOval( xDrawPoints[ i ] - wOval/2,
size.height - 1 - yDrawPoints[ i ] - hOval/2,
wOval, hOval);
for ( int i = 1; i < xDrawPoints.length; i++)
g.drawLine( xDrawPoints[ i-1 ],
size.height - 1 - yDrawPoints[ i-1 ],
xDrawPoints[ i ],
size.height - 1 - yDrawPoints[i] );
// draw fitting (approximating) curve
if ( isApproxData ) {
g.setColor( Color.red );
for ( int i = 0; i < xDrawPoints.length; i++ )
g.fillOval( xDrawPoints[ i ] - wOval/2,
size.height - 1 - yDrawApprox[ i ] - hOval/2,
wOval, hOval);
for( int i = 1; i < xDrawPoints.length; i++)
g.drawLine( xDrawPoints[ i-1 ],
size.height - 1 - yDrawApprox[ i-1 ],
xDrawPoints[ i ],
size.height - 1 - yDrawApprox[i] );
}
coverEastPanel.setVisible( true );
}
// action listener method that menu items invoke
public void actionPerformed( ActionEvent e ) {
String command = e.getActionCommand();
if ( command.equals( "quit" ) ) {
inAnApplet = false;
dispose();
System.exit(0);
}
else if ( command.equals( "file" ) ) {
try {
FileDialog d =
new FileDialog( this, "Open File", FileDialog.LOAD );
// display file dialog window and block until answered
d.show();
String fileName = d.getDirectory() + "/" + d.getFile();
textarea.append( "File: "+fileName+"\r" );
try {
inputData = readFileData ( fileName );
}
catch ( FileNotFoundException exc ) {
textarea.append( "No such data file!\r" );
}
finally {
d.dispose(); // dispose file dialog window
}
}
catch ( NullPointerException exc1 ) {
textarea.append( "FileDialog cancelled!\r" );
}
}
else if ( command.equals( "form" ) ) {
textArraySize.setText("");
textArraySize.setVisible( true );
}
else if ( command.equals( "about" ) ) {
textarea.append("\r\r********************************\r");
textarea.append("* *\r");
textarea.append("* TEST-BENCH FOR SORT METHODS *\r");
textarea.append("* (Paper 415.231) *\r");
textarea.append("* *\r");
textarea.append("* (c)1998 G. Gimel'farb *\r");
textarea.append("* *\r");
textarea.append("* Dept. of Computing Science *\r");
textarea.append("* University of Auckland *\r");
textarea.append("* *\r");
textarea.append("********************************\r\r");
}
}
// read data to sort from text file
public static int[] readFileData ( String fileName )
throws FileNotFoundException,
NullPointerException {
StreamTokenizer getNumbers =
new StreamTokenizer( new FileReader ( fileName ) );
getNumbers.parseNumbers();
inputData = new int[ 10 ];
itemsToSort = 0;
int sortMin = bigIntValue;
int sortMax = -bigIntValue;
int numIOExcs = 0;
final int maxIOExc = 10;
while ( true ) {
try {
int returnValue = getNumbers.nextToken();
if ( returnValue == StreamTokenizer.TT_EOF ) break;
if ( returnValue != StreamTokenizer.TT_NUMBER )
throw new IOException ( "Non-number in file" );
if ( itemsToSort == inputData.length )
inputData = resize( inputData, inputData.length*2 );
int dataval = (int) Math.round( getNumbers.nval );
if( sortMin > dataval ) sortMin = dataval;
if( sortMax < dataval ) sortMax = dataval;
inputData[ itemsToSort++ ] = dataval;
}
catch ( IOException exc ) {
numIOExcs++;
textarea.append( "["+numIOExcs+"]: "+ exc.getClass() +
" : " + exc.getMessage() +"\r" );
}
}
textarea.append( "Done reading\r" );
textarea.append( "Array["+itemsToSort+"]: min/max= "+
sortMin+"/"+sortMax+"\r" );
// if no data items read, create random inputData[ 500 ]
if ( itemsToSort == 0 ) {
itemsToSort = 500;
inputData = new int [500];
for ( int i = 0; i < inputData.length; i++ )
inputData[ i ] =
(int) Math.round( numRange * Math.random() );
return inputData;
}
else
return resize( inputData, itemsToSort );
}
// resize int [] array and return new resized array
public static int[] resize( int[] array, int newSize ) {
int [] original = array;
int numToCopy = Math.min( original.length, newSize );
array = new int [ newSize ];
if ( newSize > 0 )
for( int i = 0; i < numToCopy; i++ )
array[ i ] = original [ i ];
return array;
}
// test chosen sort method and get running time in millisecs
public static long testSortingMethod ( String method ) {
long timeStart = 0;
long timeFinish = 0;
if ( method == "InsertionSort" ){
timeStart = System.currentTimeMillis();
SortMeth.insertionSort( dataToSort );
timeFinish = System.currentTimeMillis();
} else
if ( method == "BubbleSort" ){
timeStart = System.currentTimeMillis();
TestMeth.bubbleSort( dataToSort );
timeFinish = System.currentTimeMillis();
} else
if ( method == "CombSort" ){
if ( combShrink <= 1. ) combShrink = defaultShrink;
TestMeth.SHRINK = combShrink;
timeStart = System.currentTimeMillis();
TestMeth.combSort( dataToSort );
timeFinish = System.currentTimeMillis();
} else
if ( method == "ShellSort" ){
timeStart = System.currentTimeMillis();
SortMeth.shellSort( dataToSort );
timeFinish = System.currentTimeMillis();
} else
if ( method == "MergeSort" ){
timeStart = System.currentTimeMillis();
SortMeth.mergeSort( dataToSort );
timeFinish = System.currentTimeMillis();
} else
if ( method == "QuickSort" ){
timeStart = System.currentTimeMillis();
SortMeth.quickSort( dataToSort );
timeFinish = System.currentTimeMillis();
} else
if ( method == "HeapSort" ){
timeStart = System.currentTimeMillis();
SortMeth.heapSort( dataToSort );
timeFinish = System.currentTimeMillis();
}
// for any case: check if the output data is sorted
// if not - print error message in the West textarea
boolean errcheck = false;
for ( int i = 1; i < dataToSort.length; i++ )
if( dataToSort[ i ] < dataToSort[ i - 1 ] ) errcheck = true;
if ( errcheck ) {
textarea.append( "\r\r Wrong sorting! \r" );
textarea.append( "SHRINK=" + TestMeth.SHRINK +
"; gap=" + TestMeth.gap + "\r\r");
for( int i = 0; i < dataToSort.length; i++ ) {
textarea.append( dataToSort [i] + ": ");
if ( (i+1)%8 == 0 ) textarea.append ( "\r" );
}
}
return timeFinish - timeStart;
}
// dummy data to start with for visualising graphics
private void startingData() {
for ( int i = 0; i < 10; i++ ) {
xPoints[ i ] = (defaultSize/10) * (i + 1);
yPoints[ i ] = (defaultSize/1000) * (i + 1);
}
}
// main method to start the test bench and leave forever
public static void main ( String[] args ) {
TestBench f = new TestBench("Sorting TestBench" );
f.pack();
f.show();
}
}
package Methods;
/*
*
* Sorting methods
*
*/
public class SortMeth
{
static public int CUTOFF = 10;
public static void insertionSort(int [] a) {
int i, tempi, k;
for( i = 1; i < a.length; i++ ) {
tempi = a[i];
k = i - 1;
while( k >= 0 && tempi < a[k] ) {
a[k+1] = a[k];
k--;
}
a[k+1] = tempi;
}
}
public static void shellSort(int [] a) {
int i, tempi, k, gap;
for( gap = a.length/2; gap > 0;
gap = (gap == 2) ? 1 : (int)(gap/2.2) )
for( i = gap; i < a.length; i++ ) {
tempi = a[i];
k = i;
while( k >= gap && tempi < a[k-gap] ) {
a[k] = a[k-gap];
k -= gap;
}
a[k] = tempi;
}
}
//-------------------------------------------------
// Mergesort algorithm
// a[] an integer array to be sorted
//-------------------------------------------------
public static void
mergeSort( int [] a)
{
int []tmpArray = new int[ a.length ];
mergeSort( a, tmpArray, 0, a.length - 1 );
}
private static void mergeSort( int [] a,
int [] tmpArray, int left, int right) {
if( left < right ) {
int centre = (left + right) / 2;
mergeSort( a, tmpArray, left, centre);
mergeSort( a, tmpArray, centre + 1, right);
merge( a, tmpArray, left, centre + 1, right );
}
}
private static void merge( int [] a, int [] tmpArray,
int leftPos, int rightPos, int rightEnd ) {
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int leftBeg = leftPos;
// Main loop
while( leftPos <= leftEnd && rightPos <= rightEnd )
if ( a[ leftPos ] < a[ rightPos ] )
tmpArray[ tmpPos++ ] = a[ leftPos++ ];
else
tmpArray[ tmpPos++ ] = a[ rightPos++ ];
// Copy the rest of the first half
while( leftPos <= leftEnd )
tmpArray[ tmpPos++ ] = a[ leftPos++ ];
// Copy the rest of the second half
while( rightPos <= rightEnd )
tmpArray[ tmpPos++ ] = a[ rightPos++ ];
// Copy tmpArray back
for( tmpPos=leftBeg; tmpPos<=rightEnd; tmpPos++ )
a[ tmpPos ] = tmpArray[ tmpPos ];
}
public static void quickSort( int [] a ) {
quickSort( a, 0, a.length - 1 );
}
private static void quickSort( int [] a,
int low, int high) {
if ( low + CUTOFF > high )
insertionSort( a, low, high );
else {
// Sort low, middle, high
int middle = ( low + high ) / 2;
if ( a[ middle ] < a[ low ] )
swapElements( a, low, middle );
if ( a[ high ] < a[ low ] )
swapElements( a, low, high );
if ( a[ high ] < a[ middle ] )
swapElements( a, middle, high );
// Place pivot at position high - 1
swapElements( a, middle, high - 1 );
int pivot = a[ high - 1];
// Begin partitioning
int i, j;
for ( i = low, j = high - 1; ; ) {
while( a[ ++i ] < pivot );
while( pivot < a[ --j ] );
if ( i < j )
swapElements( a, i, j );
else
break;
}
// Restore pivot
swapElements( a, i, high - 1 );
// Sort small elements
quickSort( a, low, i - 1 );
// Sort large elements
quickSort( a, i + 1, high );
}
}
private static void swapElements( int [] a,
int i, int j ) {
int temp = a[ i ];
a[ i ] = a[ j ];
a[ j ] = temp;
}
private static void insertionSort(int [] a,
int low, int high) {
int i, tempi, k;
if ( low > high || low < 0 || high >= a.length ) {
for ( i = 1; i < a.length; i++ ) {
tempi = a[ i ];
k = i - 1;
while( k >= 0 && tempi < a[k] ) {
a[ k + 1 ] = a[ k ];
k--;
}
a[ k+1 ] = tempi;
}
}
else {
for ( i = low + 1; i <= high; i++ ) {
tempi = a[i];
k = i - 1;
while( k >= low && tempi < a[k] ) {
a[ k + 1 ] = a[ k ];
k--;
}
a[k+1] = tempi;
}
}
}
public static void heapSort( int [] a ) {
int index;
// build heap
for ( index = a.length / 2 - 1; index >= 0; index-- )
heapify( a, index, a.length );
for( index = a.length - 1; index >= 1; index-- ) {
swapElements( a, 0, index ); // removeMax
heapify( a, 0, index );
}
}
private static void heapify( int [] a,
int index, int size ) {
int childPos;
// data item position = index + 1
int parentPos = index + 1;
for ( childPos = parentPos * 2; childPos < size;
childPos = parentPos * 2 ) {
if ( a[ parentPos - 1 ] < a[ childPos - 1 ] ||
a[ parentPos - 1 ] < a[ childPos ] ) {
if ( a[ childPos - 1 ] < a[ childPos] ) {
swapElements( a, parentPos - 1, childPos );
parentPos = childPos + 1;
}
else {
swapElements( a, parentPos - 1, childPos - 1 );
parentPos = childPos;
}
}
else break;
}
if ( childPos == size &&
a[ parentPos - 1 ] < a[ childPos - 1 ] )
swapElements( a, parentPos - 1, childPos - 1 );
}
}
package Assigns;
/**
*
* Sorting method to be tested
*
*/
public class TestMeth
{
public static double SHRINK;
public static int gap;
public static void bubbleSort(int [] a) {
boolean isSwap = true;
int currentTop = a.length;
while( isSwap ) {
isSwap = false;
for( int j = 1; j < currentTop; j++ )
if ( a[ j - 1 ] > a[ j ] ) {
swapElements( a, j - 1, j );
isSwap = true;
}
currentTop--;
}
}
public static void combSort(int [] a) {
boolean isSwap = true;
int currentTop = a.length;
gap = (int) ( (double) a.length / SHRINK );
while( isSwap || gap > 1 ) {
isSwap = false;
for( int j = gap; j < currentTop; j++ )
if ( a[ j - gap ] > a[ j ] ) {
swapElements( a, j - gap, j );
isSwap = true;
}
if ( gap > 1 )
gap = (int) ( (double) gap / SHRINK );
else {
gap = 1;
currentTop--;
}
}
}
private static void
swapElements( int [] a,
int i, int j )
{
int temp = a[ i ];
a[ i ] = a[ j ];
a[ j ] = temp;
}
}