/*
Kurzbeschreibung von Bubble Sort (Sortieren durch Austauschen) 

Die zu sortierende Folge von N Elementen wird vom ersten Element an 
durchlaufen, wobei immer zwei nebeneinander liegende Elemente 
verglichen werden. Sind zwei Elemente falsch sortiert, so vertauscht 
man die beiden. Nach dem ersten Durchlaufen der Folge ist das groesste
Element an seinem richtigen Platz angelangt. Dann geht man die Folge
erneut durch und vertauscht, falls noetig, wiederum je zwei 
benachbarte Elemente. Dieses Durchlaufen wiederholt man solange, bis 
keine Vertauschungen mehr auftreten.

Bubble Sort benoetigt im Durchschnitt und im unguenstigsten Fall ungefaehr 1/2 N^2 Vergleiche und 1/2 N^2 Austauschoperationen.
*/

class BubbleSort
{
   public static void bubble(int[] a)
   {
      for(int i = a.length-1; i > 0; i--)
         for(int j = 0; j < i; j++)
            if(a[j] > a[j+1])
            {
               int tmp = a[j];
               a[j] = a[j+1];
               a[j+1] = tmp;
            }
   }

   public static void main(String[] args)
   {
      int[] intFeld = new int[10];
   
      // intFeld mit Pseudo-Zufallszahlen
      // im Bereich 0 .. 100 initialisieren
      for(int i=0; i<intFeld.length; i++)
         intFeld[i] = (int)(100*Math.random()); 

      System.out.print("vor dem Sortieren:  ");
      for(int i=0; i<intFeld.length; i++)
         System.out.print(intFeld[i] + " ");
      System.out.println();

      bubble(intFeld);

      System.out.print("nach dem Sortieren: ");
      for(int i=0; i<intFeld.length; i++)
         System.out.print(intFeld[i] + " ");
      System.out.println();
   }
}


/* 
Beispiel fuer die Ausgabe des Programms:

vor dem Sortieren:  8 64 13 9 2 27 3 123 17 1 
nach dem Sortieren: 1 2 3 8 9 13 17 27 64 123 

*/