// ACHTUNG: das folgende ist kein vollst. JAVA-Code,
// sondern nur eine Sammlung wesentlicher Sortier-Algorithmen


/**
 * Schnittstelle zum Vergleich zweier Objekte aus dem zu sortierenden Feld
 */
public interface SortCondition{

/**
 * liefert true, falls obj2 größer als obj1
 */
   public abstract boolean isGreaterThan(Object obj1, Object obj2);

} // SortCondition

//---------------------------------------------------------------------------

/**
  * der jeweils "pure" Algorithmus, aufgerufen um seine Laufzeit zu messen
  *
  * @param sc - Schnittstelle SortCondition zum Vergleich von Elementen
  * @param a  - zu sortierendes Feld
  * @param n  - Anzahl der Elemente
  */

public void bubbleSort(SortCondition sc, Object a[], int n)   {
    int i,j;
    Object temp;

    for (i = n - 1; i >= 0; i--)		// AND unstable
      for (j = 0; j < i; j++) {			// unstable = false

	if (sc.isGreaterThan(a[j+1],a[j])) {
	  temp = a[j+1];		        // unstable = true
      	  a[j+1] = a[j];
          a[j] = temp;
	} // if

      } // for
    } // for

} // bubbleSort

//----------------------------------------------------------------------------

public void selectionSort(SortCondition sc, Object a[],int n) {
    int i,j,min;
    Object elem;

    for (i=0;i<n-1;i++) {        // search local minimum for a[i]

      min=i;		
      for(j=i+1;j<a.length;j++) {
        if (sc.isGreaterThan(a[j],a[min])) {
          min=j;
	} // if
      } //for

      elem=a[min];		 // switch a[i] with a[min]
      a[min]=a[i];
      a[i]=elem;

    } //for

} // selectionSort

//----------------------------------------------------------------------------

public void insertionSort(SortCondition sc, Object a[], int n) {
    int i,j;
    Object elem;

    for (i=1;i<n;i++) {

      elem=a[i];
      j=i;

      while(sc.isGreaterThan(elem,a[j-1])) {
      	a[j]=a[j-1];
	j=j-1;
        if(j==0) break;
      } // while

      a[j]=elem;

    } // for

} // insertionSort

//----------------------------------------------------------------------------

public void shellSort(SortCondition sc, Object a[],int n) {

    int i,j,delta;
    Object elem;
    delta=1;

    do {
      delta=delta*3+1;
    } while (n >= delta);

    do {

      delta = delta / 3;
      for(i=delta;i<n;i++) {
	    elem=a[i];
        j=i;

        while(sc.isGreaterThan(elem,a[j-delta])) {
          a[j]=a[j-delta];
          j=j-delta;
          if(j<delta) break;
        } // while

        a[j]=elem;
      } // for

    } while (delta > 1);
  
} // shellSort

//----------------------------------------------------------------------------

public void bucketSort(SortCondition sc, Object a[], int n) {

    if( n <= 0 ) return;                                    // Case of empty array
    Integer min = (Integer)a[0];
    Integer max = min;

    for( int i = 1; i < n; i++ )                            // Find the minimum and maximum
      if(sc.isGreaterThan(max,a[i]) )
        max = (Integer)a[i];
      else if(sc.isGreaterThan(a[i],min))
        min = (Integer)a[i];

    int bucket[] = new int[max.intValue()-min.intValue()+1];// Create buckets

    for( int i = 0; i < n; i++ )                            // "Fill" buckets
      bucket[((Integer)a[i]).intValue()-min.intValue()]++;  // by counting each datum

    int i = 0;
    for( int b = 0; b < bucket.length; b++ )                // "Empty" buckets
      for( int j = 0; j < bucket[b]; j++ )                  // back into array
        a[i++] = new Integer(b+min.intValue());             // by creating one per count

} // bucketSort

//----------------------------------------------------------------------------

public void mergeSort(SortCondition sc, Object a[], int lo, int hi) {

      if (lo == hi) return;
      int length = hi-lo+1;
      int pivot = (lo+hi) / 2;

      mergeSort(sc,a, lo, pivot);
      mergeSort(sc,a, pivot+1, hi);

      Object working[] = new Object[length];
      for (int i = 0; i < length; i++) working[i] = a[lo+i];
    
      int m1 = 0;
      int m2 = pivot-lo+1;

      for(int i = 0; i < length; i++) {
        if (m2 <= hi-lo)
          if (m1 <= pivot-lo)
            if (sc.isGreaterThan(working[m2],working[m1]))
              a[i+lo] = working[m2++];
            else a[i+lo] = working[m1++];
          else a[i+lo] = working[m2++];
        else  a[i+lo] = working[m1++];
      } // for
  
} //mergeSort

//----------------------------------------------------------------------------

public void heapSort(SortCondition sc, Object a[],int anz) {
    int k;
    int l;
    Object t;
    int m;
    int n;
    m=anz-1;
    n=m;
   
    //Heap konstruieren
    for (k=m /2;k>=0;k--) {
      DownHeap(sc,k,n,a);
    } // for

    // Heap in der richtigen Reihenfolge abbauen
    do {
      t=a[0];
      a[0]=a[m];
      a[m]=t;
      m=m-1;
      DownHeap(sc,0,m,a);
    } while (m>0);

} // heapSort

//----------------------------------------------------------------------------