public class NeuBubble {
	private final static void swap(int[] a, int i, int k){
		int h = a[i];
		a[i] = a[k];
		a[k] = h;
	}

	static void bubbleSort1(int[] a){
		int hi = a.length-1;
		for (int k=hi;k>0;k--)
			for (int i=0;i<k;i++)
				if ( a[i] > a[i+1]) swap (a, i, i+1);
	}

	static void bubbleSort2(int[] a){
		int hi = a.length-1;
		boolean test;
		for (int k=hi;k>0;k--) {
			test=true;
			for (int i=0;i<k;i++)
				if (a[i]>a[i+1]) {
					swap(a,i,i+1);
					test=false;
				}
			if (test) break;
		}
	}

	static void dualBubbleSort(int[] a) {
		int hi = a.length-1;
		int lo=0;
		boolean test;
		while (hi>lo) {
			test=true;
			for (int i=lo;i<hi;i++)
				if (a[i]>a[i+1]) {
					swap(a,i,i+1);
					test=false;
				}
			hi--;
			for (int j=hi;j>lo;j--)
				if (a[j-1]>a[j]) {
					swap(a,j,j-1);
					test=false;
				}
			lo++;
			if (test) break;
		}
	}

	public static void main(String args[]) {

		int len=10000;		//Arraygröße (Anzahl der Daten) einstellen

		int[] src = new int[len];
		for (int i=0;i<len;i++) src[i]=-1;
		int t,i=0;
		//Zufällig belegtes Array erzeugen...
		while (i<len) {
			t=(int)(Math.random()*len);
			if (src[t]<0) src[t]=i++;
			//System.out.println(t+"\t"+i);
		}

		int[] feld = new int[len];
		long t0,t1;

		System.arraycopy(src,0,feld,0,len);
		System.out.print("Bubble Sort1:      ");
		t0=System.currentTimeMillis();
		bubbleSort1(feld);
		t1=System.currentTimeMillis();
		System.out.println("Laufzeit bei "+len+" Zahlen: "+(t1-t0));

		System.arraycopy(src,0,feld,0,len);
		System.out.print("Bubble Sort2:      ");
		t0=System.currentTimeMillis();
		bubbleSort2(feld);
		t1=System.currentTimeMillis();
		System.out.println("Laufzeit bei "+len+" Zahlen: "+(t1-t0));

		System.arraycopy(src,0,feld,0,len);
		System.out.print("DualBubble Sort:   ");
		t0=System.currentTimeMillis();
		dualBubbleSort(feld);
		t1=System.currentTimeMillis();
		System.out.println("Laufzeit bei "+len+" Zahlen: "+(t1-t0));
		// for (int j=0;j<len;j++) System.out.println(feld[j]);



		System.out.println("Bei sortierten Daten:");



		System.out.print("Bubble Sort1:      ");
		t0=System.currentTimeMillis();
		bubbleSort1(feld);
		t1=System.currentTimeMillis();
		System.out.println("Laufzeit bei "+len+" Zahlen: "+(t1-t0));

		System.out.print("Bubble Sort2:      ");
		t0=System.currentTimeMillis();
		bubbleSort2(feld);
		t1=System.currentTimeMillis();
		System.out.println("Laufzeit bei "+len+" Zahlen: "+(t1-t0));

		System.out.print("DualBubble Sort:   ");
		t0=System.currentTimeMillis();
		dualBubbleSort(feld);
		t1=System.currentTimeMillis();
		System.out.println("Laufzeit bei "+len+" Zahlen: "+(t1-t0));

	}
}