gistfile1.txt

import java.util.*;
import java.io.*;

class Sorting {
	static int vgl = 0;
	static int inversionen = 0;
	static boolean lt(int x, int y){vgl++; return x <  y;}
	static boolean le(int x, int y){vgl++; return x <= y;}
	static boolean ge(int x, int y){vgl++; return x >= y;}
	static boolean gt(int x, int y){vgl++; return x >  y;}

	static int insertionsort(int[] a) {
		vgl=0;
		int j;
		for (j=1; j < a.length ; j++) {
			int x = a[j];
			int i = j-1;
			//int i_ = i;
			while ( i >= 0 && gt(a[i],x) ) {
				a[i+1] = a[i];
				i--;
			}
			//if(i_<0) // ??
			a[i+1] = x;
		}
		//return a;
		return vgl;
	}


	static int mergesortInitial(int[] a, int l, int r) {
		vgl = 0;
		mergesort(a,l,r);
		return vgl;
	}

	static void mergesort(int[] a, int l, int r) {
		if ( lt(l,r) ) {
			int m = l+(r-l)/2;
			mergesort(a,l,m);
			mergesort(a,m + 1,r);
			merge(a,l,m,r);
		}
	}

	static void merge(int[] a, int l, int m, int r) {
		// Kopiere die beiden sortierten Teilfelder in left und right.
		int[] left = new int[m-l+1];
		int[] right = new int[r-m];
		for (int i = 0; i < m-l+1; i++)
			left[i] = a[l+i];
		for (int i = 0; i < r-m; i++)
			right[i] = a[m+1+i];
		// Solange beide Teilfelder noch Elemente enthalten, füge sie in a ein.
		int iL = 0,
			iR = 0,
			iA = l;
		while ( iL < m-l+1 && iR < r-m) {
			if ( le(left[iL] , right[iR]) )
				{ a[iA] = left[iL]; iA++; iL++; }
			else
				{ inversionen++; // HOCHZÄHLEN
					a[iA] = right[iR]; iA++; iR++; }
		}
		// Füge die übrig gebliebenen Elemente eines Teilfeldes in a ein.
		while ( iL < m-l+1 )
			{ a[iA] = left[iL]; iA++; iL++; }
		while ( iR < r-m )
			{ a[iA] = right[iR]; iA++; iR++; }
	}

	public static int[] randomArray(int n) {
		int[] randomArray = new int[n];
		Random randNumGenerator = new Random();
		for (int i = 0; i < n; i++)
			randomArray[i] = (int) randNumGenerator.nextInt();
		return randomArray;
	}

	public static void main(String... args) throws Exception {
		
		BufferedWriter fileIV = new BufferedWriter(new FileWriter("insertsort-vrgl"));
		BufferedWriter fileIT = new BufferedWriter(new FileWriter("insertsort-time"));
		BufferedWriter fileMV = new BufferedWriter(new FileWriter("mergesort-vrgl"));
		BufferedWriter fileMT = new BufferedWriter(new FileWriter("mergesort-time"));
		for(int len=1; len<=500; len++) {
			int vrglI=0, vrglM=0;
			long timeI=0, timeM=0;
			for (int run=1; run<=len; run++) {
				int[] a = randomArray(len);
				int[] b = new int[len];
				System.arraycopy(a,0,b,0,a.length);

				timeI = System.nanoTime();
				vrglI += insertionsort(a);
				timeI = System.nanoTime() - timeI;

				timeM = System.nanoTime();
				vrglM += mergesortInitial(b,0,len-1);
				timeM = System.nanoTime() - timeM;
			}
			fileIV.write(len+" "+vrglI/len+"\n");
			fileIT.write(len+" "+timeI+"\n");
			fileMV.write(len+" "+vrglM/len+"\n");
			fileMT.write(len+" "+timeM+"\n");
			System.out.print(len+" ");
		}
		System.out.print("\n");
		fileIV.close();
		fileMV.close();
		fileIT.close();
		fileMT.close();
	}
}