ソート、集計ソートの挿入


package org.sz.sort;

import java.util.Arrays;
/**
 *  
 */
public class SortUtil {
    /**
     *  
     * compareTo T <? super T>
     *  
     */
	public static <T extends Comparable<? super T>> 
        void insertionSort(T[] a) {
		int j;
		for (int i = 1; i < a.length; i++) {
			T tmp = a[i];
			for (j = i; j > 0; j--) {
				if (tmp.compareTo(a[j -1]) < 0) {
					a[j] = a[j -1];
					a[j -1] = tmp;
				}
			}
		}
    }
    /**
     *  
     */
	private static <T extends Comparable<? super T>> 
	    void mergeSort(T[] a, T[] tmp, int left, int right) {
		if (left < right) {
			int center = (left + right) / 2;
			mergeSort(a, tmp, left , center);
			mergeSort(a, tmp, center + 1, right);
			merge(a, tmp, left, center + 1, right);
		}
	}
	private static <T extends Comparable<? super T>>
	    void merge(T[] a, T[] tmp, int leftPos, int rightPos, int rightEnd) {
		int leftEnd = rightPos - 1;
		int tmpPos = leftPos;
		int numElements = rightPos - leftPos + 1;
		
		while(leftPos <= leftEnd && rightPos <= rightEnd) {
			if(a[leftPos].compareTo(a[rightPos]) < 0)
				tmp[tmpPos++] = a[leftPos++]; 
			else 
				tmp[tmpPos++] = a[rightPos++]; 
		}
		while(leftPos <= leftEnd) {
			tmp[tmpPos++] = a[leftPos++];
		}
		while(rightPos <= rightEnd) {
			tmp[tmpPos++] = a[rightPos++];
		}
		for(int i = 0; i < numElements; i++, rightEnd--) {
			a[rightEnd] = tmp[rightEnd];
		}
	}
	public static void main(String[] args) {
		Subject[] a = {new Subject(20), new Subject(54), new Subject(50)};
		insertionSort(a);
		System.out.println(Arrays.deepToString(a));
	}
	
	static class Subject implements Comparable<Subject> {
        private int score;
        public Subject(int score) {
        	this.score = score;
        }
		@Override
		public int compareTo(Subject o) {
			if (this.score > o.score) {
				return 1;
			} else if (this.score < o.score) {
				return -1;
			} else {
				return 0;
			}
		}
		@Override
		public String toString() {
			return " " + this.score;
		}
	}
}