/***************************  BucketSort.java  ********************************/

import AlgoTools.IO;

/** Sortieren durch Verteilen auf Buckets (Faecher).
 *  Idee: 1.) Zaehlen der Haeufigkeiten b[i] einzelner Schluessel i;
 *        2.) Buckets durchlaufen und i-ten Schluessel b[i]-mal ausgeben.
 */

public class BucketSort {

  static final int N = 256;                     // Alphabetgroesse N

  public static char[] sort (char[] a) {        // sortiere Character-Array a
                                                // und liefere Ergebnis zurueck
    
    char[] fertig = new char[a.length];         // Ergebniszeichenkette
    int[] b = new int[N];                       // N Buckets
    int i, j, k=0;                              // Laufvariablen

    for (i=0; i < N; i++) b[i] = 0;             // setze alle Buckets auf 0

    for (i=0; i < a.length; i++)                // fuer jedes Eingabezeichen
        b[a[i]]++;                              // zustaendiges Bucket erhoehen
    
    for (i=0; i < N; i++)                       // fuer jedes Bucket
        for (j=0; j < b[i]; j++)                // gemaess Zaehlerstand
            fertig[k++] = (char) i;             // sein Zeichen uebernehmen 

    return fertig;                              // Zeichenkette zurueckgeben
  }

  public static void main (String [] argv) {
 
    char[] zeile, ergebnis;                             // 2 Zeichenfolgen    
 
    zeile = IO.readChars("Bitte Zeichenkette:       "); // Zeichenkette einlesen
    ergebnis = sort(zeile);                             // Bucket-Sort aufrufen
    IO.print("sortiert mit Bucket-Sort: ");             // Ergebnis ausgeben
    IO.println(ergebnis);
  }
}
// Aufwand: O(n) + O(N)   bei n(=a.length) zu sortierenden Zeichen
//                        aus einem N-elementigen Alphabet