Søgning/sortering i Java

Opgaver

Der er som bekendt ingen grund til, at man skal opfinde den dybe tallerken, hver gang man skal bruge den - således er det også med søgning og sortering. Derfor er binær søgning og sortering implementeret i Java's standard-biblioteker én gang for alle. (Java bruger en forbedret implementation af quicksort, som er beskrevet af Jon L. Bentley og M. Douglas McIlroy i artiklen "Engineering a Sort Function" fra "Software-Practice and Experience", nr. 23 (11), s.1249-65 (nov. 1993)).

De findes i klassen java.util.Arrays i form af en lang række binarySearch- og sort-metoder, der er overloadede for alle primitive typer, samt Object.

1. Søgning

java.util.Arrays har følgende statiske metoder, der foretager en binær søgning:

int binarySearch( byte[]   array, byte   key )
int binarySearch( short[]  array, short  key )
int binarySearch( int[]    array, int    key )
int binarySearch( long[]   array, long   key )
int binarySearch( float[]  array, float  key )
int binarySearch( double[] array, double key )
int binarySearch( char[]   array, char   key )
int binarySearch( Object[] array, Object key )
int binarySearch( Object[] array, Object key, Comparator c )

De syv metoder, der arbejder med de primitive typer kræver nok ikke nærmere forklaring - pånær den værdi der returneres - den er nemlig lidt speciel. Normalt vil man blot lade metoder som disse returnere -1 såfremt key ikke findes i array'et, men man har her valgt at udnytte de negative tal til at give mere information. Hvis metoderne retunerer et negativt tal betyder det stadig at key ikke findes, men ved at bruge følgende formel:

index = - ( returværdi + 1 )

får man det index hvor værdien i givet fald skulle have været, såfremt den altså havde været i array'et; hvilket den som nævnt ikke er.

Denne fortolkning af returværdien gælder også for de to sidste metoder. Begge disse metoder søger efter et objekt. Den første anvender interfacet Comparable i forbindelse med sammenligninger, og det er derfor en precondition, at objekterne i array'et, såvel som key, alle implementerer dette interface. Comparable-interfacet er beskrevet i kapitlet: "Polymorfi".

Den sidste af metoderne anvender en Comparator til at sammenligne objekterne. Vi vil vente med at se på dette interface til senere i kapitlet, da det også anvendes i forbindelse med sortering.

2. Sortering

java.util.Arrays har følgende statiske metoder, der udfører en quicksort:

void sort( byte[] array )
void sort( byte[] array, int fromIndex, int toIndex )
void sort( short[] array )
void sort( short[] array, int fromIndex, int toIndex )
void sort( int[] array )
void sort( int[] array, int fromIndex, int toIndex )
void sort( long[] array )
void sort( long[] array, int fromIndex, int toIndex )
void sort( float[] array )
void sort( float[] array, int fromIndex, int toIndex )
void sort( double[] array )
void sort( double[] array, int fromIndex, int toIndex )
void sort( char[] array )
void sort( char[] array, int fromIndex, int toIndex )
void sort( Object[] array )
void sort( Object[] array, Comparator c )
void sort( Object[] array, int fromIndex, int toIndex )
void sort( Object[] array, int fromIndex, int toIndex, Comparator c )

I forhold til array-typerne er der to udgaver af hver. Én der sorterer hele array'et, og én der sorterer en del af array'et. Sidst nævnte tager start- og slut-index som extra parametre.

3. java.util.Comparator

Interfacet: java.util.Comparator har følgende erklæring:

Comparator.java

public interface Comparator {

  int compare( Object obj1, Object obj2 );
  boolean equals( Object obj );
}

Den første af de to metoder er nok ikke overraskende, da vi allerede i kapitlet: "Klasser" så hvorledes compareTo-metoden returnerer et heltal; hvis værdi beskriver ordningen mellem de to parametre (der henvises til dette kapitel vedr. betydningen af returværdien). De eneste forskelle er, at metoden kun hedder: compare, og at begge de objekter der skal sammenlignes optræder som parametre til metoden.

Den anden metode er lidt overraskende, men Comparator-interfacet kræver rent faktisk, at man implementerer en equals-metode, der kan afgøre om en anden Comparator definerer den samme ordning som den selv. Man kan i mangel af bedre, altid implementere denne metode som et check af, at den anden Comparator er en instans af den samme klasse som en selv.