import java.util.Arrays; 
import java.util.List; 
import java.util.LinkedList; 

/** Die Klasse Sort implementiert verschiedene Sortieralgorithmen. 
 * Alle Algorithmen sortieren ein Array ueber dem Typ Comparable
 * bezueglich der durch compareTo definierten Ordnung. 
 */
public class Sort {

  /** Implementiert den Algorithmus SELECTION_SORT. */
  public static void selectionSort( Comparable[] a ) {
    for( int i = 0; i < a.length-1; i++ ) {
      // Erstes minimales Element in (a[i],...,a[n-1]) finden ...
      int min = i; // Position des aktuellen minimalen Elements
      for( int j = i+1; j < a.length; j++ ) 
	if( a[ j ].compareTo( a[ min ] ) < 0 )
	  min = j; 
      // ... und mit a[i] vertauschen:
      swap( a, min, i );
    }
  }

  /** Hilfsmethode zur Vertauschung der Array-Elemente a[i] und a[j]. 
   * Wir setzen 0 <= i, j < a.length voraus. 
   */
  private final static void swap( Comparable[] a, int i, int j ) {
      Comparable tmp = a[ i ];
      a[ i ] = a[ j ];
      a[ j ] = tmp;
  }

  /** Implementiert den Algorithmus INSERTION_SORT. */
  public static void insertionSort( Comparable[] a ) {
    for( int i = 1; i < a.length; i++ ) {
      Comparable tmp = a[ i ];
      int j = i; 
      for( ; j > 0 && tmp.compareTo( a[ j-1 ] ) < 0; j-- )
	a[ j ] = a[ j-1 ];
      a[ j ] = tmp;
    }
  }

  /** Implementiert den Algorithmus INSERTION_SORT als Hilfmethode fuer 
   * QUICK_SORT auf dem Teil-Array a[left] bis a[right]. 
   */
  public static void insertionSort( Comparable[] a, int left, int right ) {
    for( int i = left+1; i <= right; i++ ) {
      Comparable tmp = a[ i ];
      int j = i; 
      for( ; j > left && tmp.compareTo( a[ j-1 ] ) < 0; j-- )
	a[ j ] = a[ j-1 ];
      a[ j ] = tmp;
    }
  }

  /** Implementiert den Algorithmus INSERTION_SORT mit Binaersuche. */
  public static void insertionSortBinarySearch( Comparable[] a ) {
    for( int i = 1; i < a.length; i++ ) {
      Comparable tmp = a[ i ];
      // Position fuer a[i] im Bereich a[0] bis a[i-1] binaer suchen:
      int left = 0; 
      int right = i-1;
      while( left <= right ) {
	int mid = ( left + right ) / 2;
	if( a[ i ].compareTo( a[ mid ] ) < 0 )
	  right = mid - 1;
	else if( a[ i ].compareTo( a[ mid ] ) > 0 )
	  left = mid + 1;
	else {
	  left = mid;
	  break;
	}
      }
      // Dann a[i] an Position left bringen: 
      for( int j = i; j > left; j-- )
	a[ j ] = a[ j-1 ];
      a[ left ] = tmp;
    }
  }

  /** Implementiert den Algorithmus MERGE_SORT. */
  public static void mergeSort( Comparable[] a ) {
    mergeSort( a, new Comparable[ a.length ], 0, a.length-1 );
  }

  /** Eine rekursive Hilfsmethode fuer die Methode mergeSort
   * sortiert den Bereich a[left] bis a[right]. 
   */
  private static void mergeSort( Comparable[] a, Comparable[] b, 
                                 int left, int right ) {
    if( left < right ) {
      int mid = ( left + right ) / 2;
      mergeSort( a, b, left, mid );
      mergeSort( a, b, mid+1, right );
      merge( a, b, left, mid, right );
    }
  }

  /** Implementiert den Algorithmus MERGE_SORT ohne Rekursion. */
  public static void mergeSortBottomUp( Comparable[] a ) {
    Comparable[] b = new Comparable[ a.length ];
    for( int step = 1; step < a.length; step *= 2 ) {
      // Je zwei Bereiche der Groesse step werden zusammengemischt:
      for( int left = 0; left < a.length; left += 2*step ) {
	if( left + step < a.length ) { // sind noch zwei Bereich uebrig?
	  int mid = left + step - 1;
	  // Der letzte Bereich muss an Position a.length-1 enden. 
	  if( mid + step >= a.length )
	    merge( a, b, left, mid, a.length - 1 );
	  else
	    merge( a, b, left, mid, mid + step );
	}
      }
    }
  }

  /** Eine Hilfsmethode fuer die Methode mergeSort. 
   * Die sortierten Bereiche a[left] bis a[mid] und a[mid+1] bis a[right] 
   * werden zu einem sortierten Bereich a[left] bis a[right] gemischt.
   * Im Array b wird das Ergebnis zwischengespeichert. 
   */
  private static void merge( Comparable[] a, Comparable[] b,
			     int left, int mid, int right ) {
    int i1 = left; // laeuft hoch bis mid
    int i2 = mid + 1; // laeuft hoch bis right
    int bPos = left; // kopiere nach b ab bPos
    while( i1 <= mid && i2 <= right ) {
      if( a[ i1 ].compareTo( a[ i2 ] ) <= 0 ) 
	b[ bPos++ ] = a[ i1++ ];
      else
	b[ bPos++ ] = a[ i2++ ];
    }
    while( i1 <= mid ) // ersten Bereich vollends kopieren
      b[ bPos++ ] = a[ i1++ ];
    while( i2 <= right ) // zweiten Bereich vollends kopieren
      b[ bPos++ ] = a[ i2++ ];
    // Zuletzt von b nach a zurueckkopieren:
    for( bPos = left; bPos <= right; bPos++ )
      a[ bPos ] = b[ bPos ]; 
  }

  /** Implementiert den Algorithmus QUICK_SORT. */
  public static void quickSort( Comparable[] a ) {
    quickSort( a, 0, a.length-1 );
  }

  /** Arrays der Groesse CUTOFF oder kleiner werden bei QUICK_SORT
   * mit INSERTION_SORT sortiert. CUTOFF muss > 1 sein. 
   */
  private final static int CUTOFF = 8; 

  /** Eine rekursive Hilfsmethode fuer die Methode quickSort. */
  private static void quickSort( Comparable[] a, int left, int right ) {
    if( left + CUTOFF > right ) // fuer kleine Bereiche
      insertionSort( a, left, right );
    else { // fuer grosse Bereiche
      int m = partition( a, left, right );
      quickSort( a, left, m - 1 );  // kleine Elemente sortieren
      quickSort( a, m + 1, right ); // grosse Elemente sortieren
    }
  }

  /** Implementiert den Algorithmus QUICK_SORT mit kleiner Verfeinerung. */
  public static void quickSortTuned( Comparable[] a ) {
    quickSortTuned( a, 0, a.length-1 );
  }

  /** Eine rekursive Hilfsmethode fuer die Methode quickSortTuned. */
  private static void quickSortTuned( Comparable[] a, int left, int right ) {
    if( left + CUTOFF > right ) // fuer kleine Bereiche
      insertionSort( a, left, right );
    else { // fuer grosse Bereiche
      int m = partition( a, left, right );
      // Rekursiven Aufruf zuerst fuer den kleineren Bereich:
      if( m - left < right - m ) {
	quickSortTuned( a, left, m - 1 );  // die kleinen Elemente sortieren
	quickSortTuned( a, m + 1, right ); // die grossen Elemente sortieren
      }
      else {
	quickSortTuned( a, m + 1, right ); // die grossen Elemente sortieren
	quickSortTuned( a, left, m - 1 );  // die kleinen Elemente sortieren
      }      
    }
  }

  /** Eine Hilfsmethode fuer die Methode quickSort. 
   * Gibt die Position des Schnittpunkts zurueck. 
   */
  private static int partition( Comparable[] a, int left, int right ) {
    // "Median von drei":
    int mid = ( left + right) / 2; 
    if( a[ mid ].compareTo( a[ left ] ) < 0 )
      swap( a, mid, left );
    if( a[ right ].compareTo( a[ left ] ) < 0 )
      swap( a, right, left );
    if( a[ right ].compareTo( a[ mid ] ) < 0 )
      swap( a, right, mid );
    Comparable cut = a[ mid ]; // der Schnittpunkt der Partitionierung
    swap( a, mid, right-1 ); // der Schnittpunkt kommt an Position right-1

    // Das eigentliche Partitionieren: 
    int i1 = left;    // laeuft hinauf
    int i2 = right-1; // laeuft hinunter
    while( i1 < i2 ) {
      do i1++;
      while( a[ i1 ].compareTo( cut ) < 0 ); // nun ist a[i1] groesser gleich cut
      do i2--;
      while( a[ i2 ].compareTo( cut ) > 0 ); // nun ist a[i2] kleiner gleich cut
      if( i1 < i2 )
	swap( a, i1, i2 );
    }
    swap( a, i1, right - 1 ); // den Schnittpunkt wieder an seinen Platz bringen
    return i1;
  }

  /** Implementiert den Algorithmus RADIX_SORT. 
   * Jede Zahl im Array a muss < 10^k sein. 
   */
  public static void radixSort( Integer[] a, int k ) {
    LinkedList[] list = new LinkedList[ 10 ]; // die Listen list[0] bis list[9]
    for( int i = 0; i < 10; i++ )
      list[ i ] = new LinkedList( );
    LinkedList tmpList = new LinkedList( ); // die Hilfsliste
    for( int i = 0; i < a.length; i++ )
      tmpList.addLast( a[ i ] );

    for( int i = 0, mult = 1; i < k; i++ ) {
      while( !tmpList.isEmpty( ) ) {
	Integer p = (Integer)tmpList.removeFirst( ); 
	list[ ( p.intValue( ) / mult ) % 10 ].addLast( p );	
      }
      for( int j = 0; j < 10; j++ ) {
	tmpList.addAll( list[ j ] ); // list[j] an tmpList anhaengen
	list[ j ].clear( ); // list[j] leer machen
      }
      mult *= 10;
    }
    // tmpList enthaelt jetzt alle Elemente von a in sortierter Folge
    tmpList.toArray( a );
  }

  /** Testet, ob zwei Arrays identisch sind, d.h. gleich lang sind und an 
   * gleichen Positionen Elemente enthalten, die true beim Vergleich mit == liefern. 
   */
  public static boolean identical( Object[] a, Object[] b ) {
    if( a.length != b.length )
      return false; 
    for( int i = 0; i < a.length; i++ )
      if( a[ i ] != b[ i ] )
	return false;
    return true;
  }
    
  public static void main( String[] args ) {

    final int n = 20;
    final int max = 100; 
    // Erzeuge ein Array der Laenge n, das zufaellige ganzzahlige Werte
    // gleichverteilt aus dem Bereich [0, max) enthaelt: 
    Integer[] a = new Integer[ n ];
    for( int i = 0; i < n; i++ )
      a[ i ] = new Integer( (int)( Math.random( ) * max ) ); 
    System.out.println( "Das unsortierte Array:\n" + Arrays.asList( a ) );
    System.out.println( );

    // Teste die verschiedenen Sortieralgorithmen: 
    Integer[] a1 = (Integer[])a.clone( ); 
    Integer[] a2 = (Integer[])a.clone( ); 
    Integer[] a3 = (Integer[])a.clone( ); 
    Integer[] a4 = (Integer[])a.clone( ); 
    Integer[] a5 = (Integer[])a.clone( ); 
    Integer[] a6 = (Integer[])a.clone( ); 
    Integer[] a7 = (Integer[])a.clone( ); 
    Integer[] a8 = (Integer[])a.clone( ); 
    Integer[] a9 = (Integer[])a.clone( ); 

    long time0 = System.currentTimeMillis( );
    selectionSort( a1 );
    long time1 = System.currentTimeMillis( );
    insertionSort( a2 );
    long time2 = System.currentTimeMillis( );
    insertionSortBinarySearch( a3 );
    long time3 = System.currentTimeMillis( );
    mergeSort( a4 );
    long time4 = System.currentTimeMillis( );
    mergeSortBottomUp( a5 );
    long time5 = System.currentTimeMillis( );
    a6 = (Integer[]) new VollstaendigerBinaererBaum( a ).heapSort( );
    long time6 = System.currentTimeMillis( );
    quickSort( a7 );
    long time7 = System.currentTimeMillis( );
    quickSortTuned( a8 );
    long time8 = System.currentTimeMillis( );
    radixSort( a9, Integer.toString( max - 1 ).length( ) );
    long time9 = System.currentTimeMillis( );

    System.out.println( "Das mit selectionSort sortierte Array:\n" + 
    			Arrays.asList( a1 ) );
    System.out.println( "Das mit insertionSort sortierte Array:\n" + 
			Arrays.asList( a2 ) );
    System.out.println( "Das mit insertionSortBinarySearch sortierte Array:\n" + 
			Arrays.asList( a3 ) );
    System.out.println( "Das mit mergeSort sortierte Array:\n" + 
			Arrays.asList( a4 ) );
    System.out.println( "Das mit mergeSortBottomUp sortierte Array:\n" + 
    			Arrays.asList( a5 ) );
    System.out.println( "Das mit heapSort sortierte Array:\n" + 
    			Arrays.asList( a6 ) );
    System.out.println( "Das mit quickSort sortierte Array:\n" + 
    			Arrays.asList( a7 ) );
    System.out.println( "Das mit quickSortTuned sortierte Array:\n" + 
    			Arrays.asList( a8 ) );
    System.out.println( "Das mit radixSort sortierte Array:\n" + 
			Arrays.asList( a9 ) );
    System.out.println( );

    // Laufzeiten: 

    System.out.println( "Laufzeiten in Millisekunden:" );
    System.out.println( "selectionSort:\t\t\t" + 
			(time1 - time0) + " ms" );
    System.out.println( "insertionSort:\t\t\t" +
			(time2 - time1) + " ms" );
    System.out.println( "insertionSortBinarySearch:\t" +
			(time3 - time2) + " ms" );
    System.out.println( "mergeSort:\t\t\t" + 
			(time4 - time3) + " ms" );
    System.out.println( "mergeSortBottomUp:\t\t" + 
			(time5 - time4) + " ms" );
    System.out.println( "heapSort:\t\t\t" +
			(time6 - time5) + " ms" );
    System.out.println( "quickSort:\t\t\t" +
			(time7 - time6) + " ms" );
    System.out.println( "quickSortTuned:\t\t\t" +
			(time8 - time7) + " ms" );
    System.out.println( "radixSort:\t\t\t" +
			(time9 - time8) + " ms" );
    System.out.println( );

    // Test, ob alle Sortierverfahren identische Resultate geliefert haben:
    System.out.println( "Alle Algorithmen liefern sortierte Folgen: " +
			( Arrays.equals( a1, a2 ) && Arrays.equals( a1, a3 ) && 
			  Arrays.equals( a1, a4 ) && Arrays.equals( a1, a5 ) && 
			  Arrays.equals( a1, a6 ) && Arrays.equals( a1, a7 ) && 
			  Arrays.equals( a1, a8 ) && Arrays.equals( a1, a9 ) ) );
    System.out.println( );

    // Test, ob Stabilitaet verletzt ist: 
    System.out.println( "Test auf Stabilitaet am Beispiel:" );
    // Wir wissen, dass insertionSort stabil ist, also dient a2 als Referenzarray: 
    System.out.println( "selectionSort:\t\t\t" + 
			( identical( a2, a1 ) ? "+" : "-" ) );
    System.out.println( "insertionSort:\t\t\t" + "+ (immer +)" );
    System.out.println( "insertionSortBinarySearch:\t" +
			( identical( a2, a3 ) ? "+" : "-" ) );
    System.out.println( "mergeSort:\t\t\t" +
			( identical( a2, a4 ) ? "+" : "-" ) + " (immer +)" );
    System.out.println( "mergeSortBottomUp:\t\t" +
			( identical( a2, a5 ) ? "+" : "-" )  + " (immer +)" );
    System.out.println( "heapSort:\t\t\t" +
			( identical( a2, a6 ) ? "+" : "-" ) );
    System.out.println( "quickSort:\t\t\t" +
			( identical( a2, a7 ) ? "+" : "-" ) );
    System.out.println( "quickSortTuned:\t\t\t" +
			( identical( a2, a8 ) ? "+" : "-" ) );
    System.out.println( "radixSort:\t\t\t" +
			( identical( a2, a9 ) ? "+" : "-" ) + " (immer +)" );
  }

} // class Sort