/*
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;
  }
}