import java.lang.String;
/**
  *
  * Es geht hier um die experimentelle Bestimmung der Zeitkomplexität
  * dazu wird das Programm so bearbeitet,
  *   dass die Anzahl der Elemente über eine Variable n festgelegt werden kann
  *   um die Zeit mit der Uhr messen zu können, wird wiederholt
  *   Ausgabe des gewürfelten Feldes entfällt, um die Zeit nicht zu verfälschen
  *   das Auswürfeln des Feldes ist so schnell, dass Fehler in Kauf genommen wird
  *   (bei n = 500 und diesen 100000 Wiederholungen keine 2 Sekunden)
  *
  * @version 1.0 vom 04.05.2013
  * @author {$USERNAME$}
  */

public class bubble {

  public static void main(String[] args) {
    int i, j;                   // Zaehlvariablen deklarieren
    int hilf;                   // Hilfsvariable fuers Tauschen

    int n = 100;                // Anzahl der Elemente im Feld

    // Feld deklarieren
    int[] feld = new int[n];

    System.out.println("Start!");

    // 100000x wiederholen, um messbare Zeiten zu bekommen
    for (int anz = 0; anz < 100000; anz++) {

      // Feld initialisieren
      for (i = 0; i < n; i++) {
        feld[i] = (int) (500 * Math.random()  + 1);
      }

      // wir sortieren
      for (j = 0; j < n - 1; j++) {
        for (i = 0; i < n - 1 - j; i++) {
          if (feld[i] > feld[i+1]) {
            hilf      = feld[i];
            feld[i]   = feld[i+1];
            feld[i+1] = hilf;
          }
        }
      }
    }

    // sortierte Feld ausgeben
    for (i = 0; i < n; i++) {
      System.out.print(feld[i] + " ");
    }
    System.out.println();

  }
}

/* Messwerte:

   n           100    200    300    400    500
   t            4s    12s    28s    48s    73s

   n^2/t      2500   3333   3214   3333   3424  =>  t ~ n^2

*/