CSI2110 Sorting

gistfile1.java

public class Sort {

        private final static boolean D = true;

	public static void main(String[] args) {


		int[] array = {5,2,1,9,12,32,8,6};

		SortAlgo[] algos = {
				new Insertion(),
				new Selection(),
				new Bubble()
		};
                for(SortAlgo anAlgo : algos){ 
                    anAlgo.sort(); 
                    // Do stuff with the anAlgo object (read its statistics)
                }

	}

	static class Insertion extends SortAlgo{

		protected void sort() {
			for(int i = 0; i < n; i++){
				int pivot = get(i);
				int index = i;
				while( index > 0 ){
					steps++;
					if(D) System.out.println(printOriginalArray());
					int moving = get(index - 1);
					int compare = compare(pivot, moving);
					if( compare > 0 ){
						break;
					}

					swap(index,index-1);
					index--;
				}
			}
		}

		protected String name() {
			return "Insertion Sort";
		}

	}

	static class Selection extends SortAlgo{

		protected void sort() {
			int valueSmall;
			int indexSmall;
			int valueMoving;
			int indexMoving;
			for(int indexSorted = 0; indexSorted < n; indexSorted++){
				indexSmall = indexSorted;
				valueSmall = get(indexSmall);
				for(indexMoving = indexSmall + 1; indexMoving < n; indexMoving++){
					steps++;
					valueMoving = get(indexMoving);
					if( compare(valueSmall, valueMoving) > 0 ){
						indexSmall = indexMoving;
						valueSmall = get(indexSmall);
					}
				}
				swap(indexSorted, indexSmall);
				if(D) System.out.println(printOriginalArray());
			}
		}

		protected String name() {
			return "Selection Sort";
		}

	}

	static class Bubble extends SortAlgo{

		protected void sort() {
			boolean swapped;

			int sortedTop = n;
			if(D) System.out.println(printOriginalArray());
			do{
				int pairLow = 0;
				int pairHigh = 1;
				swapped = false;
				for(int i = 1; i < sortedTop; i++){

					steps++;
					if(compare(get(pairLow), get(pairHigh)) > 0){
						swap(pairLow, pairHigh);
						if(D) System.out.println(printOriginalArray());
						swapped = true;
					}

					pairLow++;
					pairHigh++;
				}
				sortedTop--;
			} while( swapped );
			if(D) System.out.println(printOriginalArray());
		}

		protected String name() {
			return "Bubble Sort";
		}
	}

	static abstract class SortAlgo {
		protected int steps = 0;
		private int comparisons = 0;
		private int swaps = 0;
		private int reads = 0;
		private int writes = 0;
		private long time = 0;

		private int[] original;
		private int[] array;
		protected int n;

		protected abstract void sort();
		protected abstract String name();

		String getHeader(){
			return "algo\ttime(median ns)\tsteps\tcomparisons\tswaps\treads\twrites\tarray";
		}

		private void reset(){
			steps = 0;
			comparisons = 0;
			swaps = 0;
			reads = 0;
			writes = 0;
			time = 0;
		}

		String getSortResult(int[] array) {
			reset();

			n = array.length;
			this.original = new int[n];
			System.arraycopy(array, 0, this.original, 0, n);
			this.array = new int[n];
			System.arraycopy(array, 0, this.array, 0, n);

			long[] measurements = new long[TIME_AVERAGING_COUNT];
			for(int i = 0; i < TIME_AVERAGING_COUNT; i++){
				time = System.nanoTime();
				sort();
				measurements[i] = System.nanoTime() - time;
			}
			Arrays.sort(measurements);
			long median = measurements[measurements.length/2];

			n = array.length;
			this.original = new int[n];
			System.arraycopy(array, 0, this.original, 0, n);
			this.array = new int[n];
			System.arraycopy(array, 0, this.array, 0, n);

			reset();
			sort();

			return String.format("%s\t%d\t%d\t%d\t%d\t%d\t%d\t%s",
					name(), median, steps, comparisons, swaps, reads, writes, printOriginalArray());
		}

		/**
		 * Compare the two integers
		 * @param a
		 * @param b
		 * @return >0 if a>b, 0 if a == b, <0 if a < b
		 */
		protected int compare(int a, int b){
			comparisons++;
			if(D)System.out.printf("compare %d < %d\n", a,b);
			return a - b;
		}

		protected int get(int i){
			reads++;
			return array[i];
		}

		protected void set(int i, int val){
			writes++;
			array[i] = val;
		}

		protected void swap(int a, int b){
			swaps++;
			if(D) System.out.printf("swap array[%d] := %d; array[%d] := %d\n", a, array[b], b, array[a]);
			int t;
			t = array[a];
			set(a,array[b]);
			set(b, t);
		}

		public String printOriginalArray(){
			ArrayList<Integer> a = new ArrayList<Integer>();
			for(int i : original)
				a.add(i);
			return a.toString();
		}

		public int getComparisons(){
			return comparisons;
		}

		public int getReads() {
			return reads;
		}

		public int getSteps() {
			return steps;
		}

		public int getSwaps() {
			return swaps;
		}

		public long getTime() {
			return time;
		}

		public int getWrites() {
			return writes;
		}
	}

}