/** InsertionSortRecursive sortiert einen Array 
@ der Grösse n von Integers rekursiv 
*/


public class InsertionSortRecursive{
    
    // Instanzvariablen
    
    private int[] sortierMichBitte;
    private int laenge;
    
    // Konstruktor zum setzen der Instanzvariablen
    
    InsertionSortRecursive(int[] uebergabeArray){
	this.sortierMichBitte = uebergabeArray;
	this.laenge = uebergabeArray.length;
	}
	
    // Hilfsmethode, damit sich der User nicht mit dem zu
    // sotierendem Bereich herumschlagen muss
    
    public int[] sort(){
	recSort(laenge);
	return this.sortierMichBitte;
	}
	
    // die eigentliche Aufgabe:
    // diese Methode ist von aussen nicht zugreifbar
    
    private void recSort(int nochZuSondierenderTeil){
	
	// Rekursionsabbruch
	
	if(nochZuSondierenderTeil == 0)
	    return;
	
	// der Rest
	
	else{
	    int position = this.laenge - nochZuSondierenderTeil;
	    int einzufuegenderSchluessel = this.sortierMichBitte[position];
	    int hilfsInt;
	    int zaehler = this.laenge - nochZuSondierenderTeil;
	    
	    // Suche der Position des einzufügenden Schlüssels
	    
	    while ( position != 0 &&
		    (einzufuegenderSchluessel < this.sortierMichBitte[position - 1])){
		hilfsInt = this.sortierMichBitte[position - 1];
		this.sortierMichBitte[position - 1] = einzufuegenderSchluessel;
		this.sortierMichBitte[position] = hilfsInt;
		position --;
		}
	    
	    recSort(nochZuSondierenderTeil - 1);
	    }
	}
    }


// Testklasse mit main-Methode


class Test{
    public static void main(String[] args){
	double zufall = 50 * java.lang.Math.random();
	int groesse = (int) zufall;
	int[] unsortiert = new int[groesse];
	int[] sortiert;
	
	// f&uuml;llen des Arrays
	
	for(int i = 0; i < groesse; i++){
	    zufall = 1000 * java.lang.Math.random();
	    unsortiert[i] = (int) zufall;
	    System.out.print ((int) zufall + "; ");
	    }
	
	// Sortieren
	
	InsertionSortRecursive ichHoffEsKlappt = new InsertionSortRecursive(unsortiert);
	sortiert = ichHoffEsKlappt.sort();
	
	// Ausgabe des sortierten Arrays
	
	System.out.print("\n\n\n\n");
	
	for(int i = 0; i < groesse; i++){
	    System.out.print(sortiert[i] + "; ");
	    }
	System.out.print("\n\nHatt's geklappt?\n");

	}
    }