/* From ulliull@uni-paderborn.de Mon Oct 19 16:38:34 1998 Path: news.uni-jena.de!news-lei1.dfn.de!news-ber1.dfn.de!news-ham1.dfn.de!news-han1.dfn.de!news.uni-paderborn.de!not-for-mail From: "Ulli" <ulliull@uni-paderborn.de> Newsgroups: de.comp.lang.java Subject: Re: Integer-Array sortieren Date: Sun, 18 Oct 1998 15:06:51 +0200 Organization: uni-paderborn.de Lines: 107 Message-ID: <70ehd8$4n9$3@news.uni-paderborn.de> References: <6vjlgu$l5j$1@news02.btx.dtag.de> NNTP-Posting-Host: ascend1-29.uni-paderborn.de X-Newsreader: Microsoft Outlook Express 4.72.3110.1 X-MimeOLE: Produced By Microsoft MimeOLE V4.72.3110.3 Xref: news.uni-jena.de de.comp.lang.java:22807 Mario Telzer schrieb in Nachricht <6vjlgu$l5j$1@news02.btx.dtag.de>... >Hallo, > >hat jemand von Euch eine funktion, mit der man ein int[] sortieren kann. Der >Algorythmus muß nicht besonders schnell sein, da es sich nur um sehr kleine >Datenmengen handelt. >Danke! > >Mario > > Quellcode folgt. Ulli */ Compare.java import java.lang.Math; /** * Ein Interface für alle Vergleiche */ public interface Compare { public int compare( Object a, Object b ); /** * Das Spezielle Compare nur für Zeichenketten */ public class StringCompare implements Compare { public final int compare ( Object a, Object b ) { return ( (String) a ).compareTo( (String) b ); } } /** * Das Spezielle Compare nur für Ganzzahlen */ public class IntegerCompare implements Compare { public final int compare ( Object a, Object b ) { return ((Integer) a).intValue() - ((Integer) b).intValue(); } } } QuickSort.java public class QuickSort { private Compare delegate; private Object [] userArray; public static void sort( Object [] userArray, Compare delegate ) { QuickSort h = new QuickSort(); h.delegate = delegate; h.userArray = userArray; if( h.isAlreadySorted() ) return; h.quicksort( 0, userArray.length-1 ); return; } private void quicksort( int p, int r ) { if ( p < r ) { int q = partition( p, r ); if ( q == r ) q--; quicksort( p, q ); quicksort( q+1, r ); } } private int partition( int lo, int hi ) { Object pivot = userArray[lo]; while ( true ) { while ( delegate.compare( userArray[hi],pivot) >= 0 && lo < hi ) hi--; while ( delegate.compare( userArray[lo],pivot) < 0 && lo < hi ) lo++; if (lo < hi) { Object T = userArray[lo]; userArray[lo] = userArray[hi]; userArray[hi] = T; } else return hi; } } private boolean isAlreadySorted() { for ( int i=1; i<userArray.length; i++ ) if ( delegate.compare( userArray[i], userArray[i-1]) < 0 ) return false; return true; } }