Insertionsort von Permutationen

[xheinz]

Guten Tag,
ich hab eine Frage zu meinem Code. Es geht darum, dass ich Permutationen dieser Art:

[ 4 1 2 3 ] feld[0]
[ 1 2 3 4 ] feld[1]
[ 4 3 2 1 ] feld[2]
[ 3 1 2 4 ] feld[3]
[ 4 3 1 2 ] feld[4]
[ 2 1 3 4 ] feld[5]
[ 4 1 3 2 ] feld[6]
[ 1 4 2 3 ] feld[7]

sortieren muss. Dabei gibt es diese Kriterien: Falls die Differenz vom Feld 0 Wert 1 - Wert 4 > als die Different Wert 1 - Wert4 vom darauffolgenden Feld. Bsp.: feld[0] < feld[1], da 1(4-3) < 3(4-1). Dabei wird der Betrag beachtet. Falls diese Differenz kleiner ist, werden die einzelnen Feldindexe vergleiche, sprich feld[1].wert (1) < feld[2].wert (1).

sortiert würde es dann so aussehen:
[ 3 1 2 4 ] feld[0]
[ 4 1 2 3 ] feld[1]
[ 1 4 2 3 ] feld[2]
[ 2 1 3 4 ] feld[3]
[ 4 1 3 2 ] feld[4]
[ 4 3 1 2 ] feld[5]
[ 1 2 3 4 ] feld[6]
[ 4 3 2 1 ] feld[7]


Dieses Feld soll nun mithilfe von Insertionsort mit der Schrittweite 3 sortiert werde. Meine Methode für den Insertionsort sieht bislang so aus :

public int insertionsort(permutation[] feld, int schrittweite) {
        int count = 0;
            for (int i = schrittweite; i<feld.length-1; i++) {
                count++;
                permutation neu = feld[i];
                System.out.println(i);
                int k = i;
                System.out.println("K: " + k);
                System.out.println("schrittweite: "+ schrittweite);
                while(Math.abs(feld[i].wert(1)-feld[i].wert(4)) < Math.abs(feld[i-schrittweite].wert(1) -feld[i-schrittweite].wert(4))) {
                    feld[k] = feld[k-schrittweite];
                    k = k-schrittweite;
                    System.out.println("k-schrittweite: " + (k-schrittweite));
                }
                feld[k] = neu;
            }
       
    return count;
    }

Ich bin jetzt davon ausgegangen, dass es mir das Feld bereits nach Differenzen sortiert zurückgibt, was jedoch nicht der Fall ist. Ich hoffe Ihr könnt mir weiterhelfen.MfG

 

[MoxxiManagarm]

Ich sehe keinen Zusammenhang von InsertionSort und Schrittweite. Welche Bedeutung soll die Schrittweite haben? Bist du dir sicher, dass du das nicht mit ShellSort verwechselst?

 

[MoxxiManagarm]

Wenn ich InsertionSort höre würde ich eher an sowas denken:

public class PermutationSort {
    private static boolean isOrdered(int[] left, int[] right) {
        int leftDiff = Math.abs(left[0] - left[left.length-1]);
        int rightDiff = Math.abs(right[0] - right[right.length-1]);

        if (leftDiff < rightDiff) {
            return true;
        } else if (leftDiff > rightDiff) {
            return false;
        }

        for (int i = 0; i < left.length; i++) {
            if (left[i] < right[i]) {
                return true;
            } else if (left[i] > right[i]) {
                return false;
            }
        }

        return true;
    }

    public static int[][] sortPermutationsByInsertion(int[][] permutations) {
        int[][] sorted = new int[permutations.length][];
        for (int i = 0; i < permutations.length; i++) {
            sorted[i] = permutations[i];

            for (int j = i; j > 0 && !isOrdered(sorted[j-1], sorted[j]); j--) {
                int[] temp = sorted[j];
                sorted[j] = sorted[j-1];
                sorted[j-1] = temp;
            }
        }
        return sorted;
    }

    public static void main(String... args) {
        int[][] permutations = {
                { 4, 1, 2, 3 },
                { 1, 2, 3, 4 },
                { 4, 3, 2, 1 },
                { 3, 1, 2, 4 },
                { 4, 3, 1, 2 },
                { 2, 1, 3, 4 },
                { 4, 1, 3, 2 },
                { 1, 4, 2, 3 }
        };

        System.out.println(Arrays.deepToString(sortPermutationsByInsertion(permutations)));
    }
}

 

[LMessi]

Hallo,
du suchst wahrscheinlich den Johnson and Trotter algorithm, um alle Permutationen zu bestimmen, jedenfalls würde das zur erwarteten Ausgabe passen.

 

[xheinz]

Ich sehe keinen Zusammenhang von InsertionSort und Schrittweite. Welche Bedeutung soll die Schrittweite haben? Bist du dir sicher, dass du das nicht mit ShellSort verwechselst?

ja mein Fehler. meinte natürlich den Shellshort!

 

[MoxxiManagarm]

ja mein Fehler. meinte natürlich den Shellshort!

Ok, abgeändert:

public static void shellSort(int[][] permutations, int gap) {
    for (int k = gap; k > 0; k /= 2) {
        for (int i = k; i < permutations.length; i++) {
            int[] key = permutations[i];

            int j;
            for (j = i; j >= k && isOrdered(key, permutations[j - k]); j -= k) { // isOrdered unverändert zu meinem vorherigen Beispiel
                permutations[j] = permutations[j - k];
            }
            permutations[j] = key;
        }
    }
}

public static void main(String... args) {
    int[][] permutations = {
            { 4, 1, 2, 3 },
            { 1, 2, 3, 4 },
            { 4, 3, 2, 1 },
            { 3, 1, 2, 4 },
            { 4, 3, 1, 2 },
            { 2, 1, 3, 4 },
            { 4, 1, 3, 2 },
            { 1, 4, 2, 3 }
    };

    shellSort(permutations, 3);

    System.out.println(Arrays.deepToString(permutations));
}