
import static org.junit.Assert.*;
import java.util.*;
 
 
public class Insertionsort> extends SortAlgos {
 
 
	public static > void sort(E[] a) {
		E temp;
 
		for (int n = 1; n < a.length; n++) {
 
			temp = a[n]; // entnommenes Element merken
			int i = n - 1;
 
			while (i >= 0 && temp.compareTo(a[i]) < 0) {
				a[i + 1] = a[i];
				i--;
			}
			a[i + 1] = temp; // entnommenes Element
			// einsetzen
		}
	}
 
	private static String toString(Element[] x){
		String res="";
		for(Element e:x){
			res=res+e.toString();
		}
		return res;
	}
 
	public static void main(String[] args) {
		Element[] nonuniqueElements2 = { 
				new Element(1, "Ich") , 
				new Element(2, "wissen"), 
				new Element(4, "ist"),
				new Element(2, "ob"),
				new Element(1, "wuerde"),
				new Element(2, "der"),
				new Element(1, "gerne"),
				new Element(2, "Algorithmus"),
				new Element(3, "stabil"),
				new Element(2, "auch"),
				new Element(2, "wirklich"),
				};
 
		String nonunique2_ElementsExpect="IchwuerdegernewissenobderAlgorithmusauchwirklichstabilist";
 
		Element[] test=nonuniqueElements2.clone();
		System.out.println("Unsortiert: " +Arrays.toString(test));
		Insertionsort.sort(test);
		String x=toString(test);
 
		System.out.println("Sortiert: " +Arrays.toString(test));
		assertEquals(nonunique2_ElementsExpect,x);
	}
}
 
 
class Element implements Comparable {
	int key;
	String value;
 
	Element(int key, String value) {
		this.key = key;
		this.value = value;
	}
 
	@Override
	public int compareTo(Element o) {
		if (key < o.key) {
			return -1;
		} else if (key > o.key) {
			return 1;
		}
		return 0;
	}
 
	@Override
	public String toString() {
		if(value instanceof String){
			return (String) value;
		}
 
		return value.toString();
	}
}