Insertionsort von Permutationen

Diskutiere Insertionsort von Permutationen im Allgemeine Java-Themen Bereich.
X

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 :

Code:
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
 
Zuletzt bearbeitet:
MoxxiManagarm

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

MoxxiManagarm

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

Java:
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)));
    }
}
 
L

LMessi

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

MoxxiManagarm

ja mein Fehler. meinte natürlich den Shellshort! :)
Ok, abgeändert:

Java:
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));
}
 
Zuletzt bearbeitet:
Thema: 

Insertionsort von Permutationen

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben