Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  


AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml

AspAutocadCDot netExcelFox proHtmlJava
LinuxMathcadPhotoshopPhpSqlVisual studioWindowsXml

Sorting and searching: Arrays

java

+ Font mai mare | - Font mai mic



DOCUMENTE SIMILARE

Trimite pe Messenger
The “visitor” pattern
The Component Class
Class access
Returning an array
Multiple threads: Inheriting from Thread
EJB3 Fundamentals
Read-only classes
switch
Handling Text, Dialogs, And Lists
Initializing the base class


Sorting and searching

Java 1.2 adds utilities to perform sorting and searching for arrays or Lists. These utilities are static methods of two new classes: Arrays for sorting and searching arrays, and Collections for sorting and searching Lists.

Arrays

The Arrays class has an overloaded sort( ) and binarySearch( ) for arrays of all the primitive types, as well as for String and Object. Here’s an example that shows sorting and searching an array of byte (all the other primitives look the same) and an array of String:




//: Array1.java

// Testing the sorting & searching in Arrays

package c08.newcollections;

import java.util.*;

public class Array1

return new String(buf);

}

// Create a random array of Strings:

public static

String[] randStrings(int length, int size)

public static void print(byte[] b)

public static void print(String[] s)

public static void main(String[] args)

} ///:~

The first part of the class contains utilities to generate random String objects using an array of characters from which random letters can be selected. randString( ) returns a string of any length, and randStrings( ) creates an array of random Strings, given the length of each String and the desired size of the array. The two print( ) methods simplify the display of the sample arrays. In main( ), Random.nextBytes( ) fills the array argument with randomly-selected bytes. (There are no corresponding Random methods to create arrays of the other primitive data types.) Once you have an array, you can see that it’s only a single method call to perform a sort( ) or binarySearch( ). There’s an important warning concerning binarySearch( ): If you do not call sort( ) before you perform a binarySearch( ), unpredictable behavior can occur, including infinite loops.

Sorting and searching with Strings looks the same, but when you run the program you’ll notice something interesting: the sorting is lexicographic, so uppercase letters precede lowercase letters in the character set. Thus, all the capital letters are at the beginning of the list, followed by the lowercase letters, so ‘Z’ precedes ‘a’. It turns out that even telephone books are typically sorted this way.

Comparable and Comparator

What if this isn’t what you want? For example, the index in this book would not be too useful if you had to look in two places for everything that begins with ‘A’ or ‘a’.

When you want to sort an array of Object, there’s a problem. What determines the ordering of two Objects? Unfortunately, the original Java designers didn’t consider this an important problem, or it would have been defined in the root class Object. As a result, ordering must be imposed on Objects from the outside, and the new collections library provides a standard way to do this (which is almost as good as defining it in Object).

There is a sort( ) for arrays of Object (and String, of course, is an Object) that takes a second argument: an object that implements the Comparator interface (part of the new collections library) and performs comparisons with its single compare( ) method. This method takes the two objects to be compared as its arguments and returns a negative integer if the first argument is less than the second, zero if they’re equal, and a positive integer if the first argument is greater than the second. With this knowledge, the String portion of the example above can be re-implemented to perform an alphabetic sort:

//: AlphaComp.java

// Using Comparator to perform an alphabetic sort

package c08.newcollections;

import java.util.*;

public class AlphaComp implements Comparator

public static void main(String[] args)

} ///:~

By casting to String, the compare( ) method implicitly tests to ensure that it is used only with String objects – the run-time system will catch any discrepancies. After forcing both Strings to lower case, the String.compareTo( ) method produces the desired results.



When you use your own Comparator to perform a sort( ), you must use that same Comparator when using binarySearch( ).

The Arrays class has another sort( ) method that takes a single argument: an array of Object, but with no Comparator. This sort( ) method must also have some way to compare two Objects. It uses the natural comparison method that is imparted to a class by implementing the Comparable interface. This interface has a single method, compareTo( ), which compares the object to its argument and returns negative, zero, or positive depending on whether it is less than, equal to, or greater than the argument. A simple example demonstrates this:

//: CompClass.java

// A class that implements Comparable

package c08.newcollections;

import java.util.*;

public class CompClass implements Comparable

public int compareTo(Object o)

public static void print(Object[] a)

public String toString()

public static void main(String[] args)

} ///:~

Of course, your compareTo( ) method can be as complex as necessary.

Lists

A List can be sorted and searched in the same fashion as an array. The static methods to sort and search a List are contained in the class Collections, but they have similar signatures as the ones in Arrays: sort(List) to sort a List of objects that implement Comparable, binarySearch(List, Object) to find an object in the list, sort(List, Comparator) to sort a List using a Comparator, and binarySearch(List, Object, Comparator) to find an object in that list. This example uses the previously-defined CompClass and AlphaComp to demonstrate the sorting tools in Collections:

//: ListSort.java

// Sorting and searching Lists with 'Collections'

package c08.newcollections;

import java.util.*;

public class ListSort

} ///:~

The use of these methods is identical to the ones in Arrays, but you’re using a List instead of an array.

The TreeMap must also order its objects according to Comparable or Comparator.



At the time of this writing, a Collections.stableSort( ) had been announced, to perform a merge sort, but it was unavailable for testing.






Politica de confidentialitate



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 373
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2022 . All rights reserved

Distribuie URL

Adauga cod HTML in site