/*
Datei............: Aufg1120.java
Projekt..........: Einführung in die Java-Programmierung
Erstellt.........: 21.11.97, Guido Krüger
Geändert.........: --
Aufgabe..........: Musterlösung zu Aufgabe 11.20
Kommentare.......:

Eine lineare Lösung für das Sortierproblem zu finden, bedeutet, 
daß jedes Element des Strings maximal k-mal "angesehen" werden 
darf, wobei k eine kleine ganzzahlige Konstante ist, die nicht
von der Länge des Strings abhängt. Das Laufzeitverhalten der
gebräuchlichen Sortierverfahren ist aber mindestens n log n,
oder sogar noch größer. Nur in Ausnahmefällen, bei denen die 
zu sortierenden Elemente einem endlichen, in der Praxis stark 
beschränkten Wertevorrat entstammen, können - beispielsweise 
mit Hilfe von Abwandlungen des Bucketsort-Verfahrens - lineare
Laufzeiten garantiert werden.

Beim Bucketsort gibt es für jedes Element des Wertevorrats
einen Behälter, typischerweise ein Arrayelement (Bucket = Eimer). 
In unserem Fall handelt es sich um das Array numChars, das
für jeden der Buchstaben von 'A' bis 'Z' ein Element enthält,
in dem die Anzahl des Vorkommens dieses Buchstabens im String
gezählt wird. Eine sortierte Ausgabe erreicht man nun ganz
einfach dadurch, daß nach dem Füllen des Arrays alle Buchstaben
in aufsteigender Reihenfolge jeweils so oft ausgegeben werden,
wie der Inhalt des korrespondierenden Array-Elements ist.

P.S. 

Dem aufmerksamen Leser wird vielleicht aufgefallen sein, daß
das nachfolgende Verfahren nur dann lineare Laufzeit hat, wenn
die Methode String.length() und der Operator += für Strings
konstante Laufzeit haben. Ist ihre Laufzeit selbst linear, 
wäre das komplette Verfahren quadratisch. Beide Routinen 
wurden lediglich aus Gründen der Übersichtlichkeit gewählt
und können leicht gegen solche mit konstanter Laufzeit 
ausgetauscht werden.
*/
import java.util.*;

public class Aufg1120
{
  public static void main(String args[])
  {
	String s[] = {"GURKENSUPPE", "HUEHNERBRUEHE", "NUDELSAUCE"};
	for (int i = 0; i < s.length; ++i) {
	  System.out.println(
        "sort(" + s[i] + ") = " + sort(s[i])
      );
	}
  }

  public static String sort(String s)
  {
	int numChars[]= new int['Z' - 'A' + 1];
	String ret = "";
	//Häufigkeit der Zeichen zählen
	for (int i = 0; i < s.length(); ++i) {
	  char c = s.charAt(i);
	  if (c >= 'A' && c <= 'Z') {
		++numChars[c - 'A'];
	  }
	}
	//Zeichen in alphabetischer Reihenfolge ausgeben
	for (char c = 'A'; c <= 'Z'; ++c) {
	  for (int j = 0; j < numChars[c - 'A']; ++j) {
		ret += c;
	  }
	}
	return ret;
  }
}