package Sortieralgorithmen;

     


public class InsertionSort {
       
    // Implementierung nach Vorlesung WS 16/17 (mit neuem Array):
    public static int[] sort(int[] a) {
        int n = a.length;   // Anzahl Elemente in a
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            // Füge Element a[i] in das (neue) Array b ein, wobei
            // bislang bereits i Elemente eingefügt wurden:
            
            // 1. Finde die richtige Einfügestelle (Index j) in b
            int j = 0; 
            while (j < i && a[i] > b[j])  // finde Einfuegestelle j fuer x in b
                ++j;
            
            // 2. Schiebe alle Elemente ab j (bis i-1) eins nach rechts (Platz schaffen)
            for (int k = i-1; k >= j; --k)
                b[k+1] = b[k];
            
            // 3. Schreibe a[i] an die richtige Stelle
            b[j] = a[i];
        }
        return b;
    }
    
    // in-place
    public static void insertionSort(int[] a) {
        for(int i = 1; i < a.length; i++) { // sortiere Element am Index i richtig in den bereits sortierten Bereich (bis Index i) ein
            for (int j = i; j > 0 && a[j] < a[j-1]; j--) { // schiebe dazu a[i] durch Vertauschen nach vorne
                int tmp = a[j-1];
                a[j-1] = a[j];
                a[j] = tmp;
            }
        }
    }
    
    public static void main(String[] args) {
        int x = 1, y = 42;
        System.out.println(++y * (1- --x + x++ - (x=y)) + 3 * x++);
        System.out.println(x);
        System.out.println(y);
    }
}