Formatiertes Output bei Insertion Sort

[emreiu]

Aufgabe​

Modifizieren Sie unten stehende Implementierung derart, dass nach jedem Durchlauf

• das Ende des sortierten Bereich mit einem senkrechten Strich markiert wird
• das neu eingefügte Element von runden Klammern umgeben dargestellt wird
• das nächste einzufügende Element als Zahl und
• alle weiteren Elemente des unsortierten Bereichs als Punkte dargestellt werden

Zu Beginn soll das unsortierte und am Ende das sortierte Array ausgegben werden. Alle Zahlenwerte werden mit zwei Stellen und anführender Null dargestellt.

Der Output sollte für die Eingabe 8, 99, 9 wie folgt aussehen:
33 61 85 38 17 02 35 39
33| 61 . . . . . .
33 61| 85 . . . . .
33 61 85| 38 . . . .
33 (38) 61 85| 17 . . .
(17) 33 38 61 85| 02 . .
(02) 17 33 38 61 85| 35 .
02 17 33 (35) 38 61 85| 39
02 17 33 35 38 (39) 61 85|
02 17 33 35 38 39 61 85

jedoch wird bei meiner implementierung die Klammer () immer in einer Zeile davor eingefügt.

 public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] a = testData(sc.nextInt(), sc.nextInt(), sc.nextInt());
        printArray(a);
        insertion(a);
        printArray(a);
        sc.close();
    }

    public static int[] testData(int size, int max, int seed) {
        int[] a = new int[size];
        Random r = new Random(seed);
        for (int i = 0; i < a.length; i++)
            a[i] = r.nextInt(max);
        return a;
    }

    public static void insertion(int[] numbers) {

        for (int i = 1; i < numbers.length; i++) {
            int j = i;
            int tmp = numbers[i];
            boolean sort = numbers[j] < numbers[j - 1];
            printArrayWithMarkers(numbers, i, j, sort);
            while (j > 0 && tmp < numbers[j - 1]) {
                numbers[j] = numbers[j - 1];
                j--;
            }
            numbers[j] = tmp;
        }
    }

    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.printf(" %02d  ", i);
        }
        System.out.println();
    }

    private static void printArrayWithMarkers(int[] arr, int i, int j, boolean sort) {
        for (int k = 0; k < arr.length; k++) {
            if (sort && k == j) {
                System.out.printf("(%02d) ", arr[k]);
            } else if (k == i - 1) {
                System.out.printf(" %02d| ", arr[k]);
            } else if (k == i || k < i) {
                System.out.printf(" %02d  ", arr[k]);
            } else {
                System.out.printf("%3c  ", '.');
            }
        }
        System.out.println();
    }

 

[mihe7]

Die Invariante der Schleife lautet, dass die ersten i Elemente im Array sortiert sind. Der sortierte Bereich umfasst also die Indizes von 0 bis einschließlich i-1 vor und nach jeder Iteration. Während der Iteration den Bereich von 0 bis i-1 vor dem Einfügen bzw. 0 bis i nach dem Einfügen. Nach dem Einfügen ist auch klar, an welcher Stelle das neue Element eingefügt wurde (s. Zeile 29).

Naja, und damit ist die Sache doch recht einfach: unmittelbar nach Zeile 29 lässt man sich das Ergebnis ausgeben. Die Variable sort ist unnötig, da angefügt wird, wenn j == i gilt, d. h. es wird eingefügt, falls j < i.

 

[emreiu]

Die Invariante der Schleife lautet, dass die ersten i Elemente im Array sortiert sind. Der sortierte Bereich umfasst also die Indizes von 0 bis einschließlich i-1 vor und nach jeder Iteration. Während der Iteration den Bereich von 0 bis i-1 vor dem Einfügen bzw. 0 bis i nach dem Einfügen. Nach dem Einfügen ist auch klar, an welcher Stelle das neue Element eingefügt wurde (s. Zeile 29).

Naja, und damit ist die Sache doch recht einfach: unmittelbar nach Zeile 29 lässt man sich das Ergebnis ausgeben. Die Variable sort ist unnötig, da angefügt wird, wenn j == i gilt, d. h. es wird eingefügt, falls j < i.

Ich werde leider aus der Erklärung nicht viel schlauer.
Die Ausgabe soll so sein, dass in jeder Zeile zunächst mal die sortierten Werte ausgegeben werden im Format %02d und anschließend der als nächstes zu beobachtende Wert im Format %02d|. Alle darauf folgenden Werte durch einen '.' ersetzt.
Falls in der aktuellen Zeile, der zu beobachtende Wert von letzter Zeile, an eine anderen Stelle eingefügt wird, soll der im Format (%02d) ausgegeben werden.

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] a = testData(sc.nextInt(), sc.nextInt(), sc.nextInt());
        printArray(a);
        insertion(a);
        printArray(a);
        sc.close();
    }

    public static int[] testData(int size, int max, int seed) {
        int[] a = new int[size];
        Random r = new Random(seed);
        for (int i = 0; i < a.length; i++)
            a[i] = r.nextInt(max);
        return a;
    }

    public static void insertion(int[] numbers) {

        for (int i = 1; i < numbers.length; i++) {
            int j = i;
            int tmp = numbers[i];

            while (j > 0 && tmp < numbers[j - 1]) {
                numbers[j] = numbers[j - 1];
                j--;
            }
            numbers[j] = tmp;
            printArrayWithMarkers(numbers, i, j);
        }
    }

    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.printf(" %02d  ", i);
        }
        System.out.println();
    }

    private static void printArrayWithMarkers(int[] arr, int i, int j) {
        for (int k = 0; k < arr.length; k++) {
            if (k == j) {
                System.out.printf("(%02d) ", arr[k]);
            } else if (k == i - 1) {
                System.out.printf(" %02d| ", arr[k]);
            } else if (k == i || k < i) {
                System.out.printf(" %02d  ", arr[k]);
            } else {
                System.out.printf("%3c  ", '.');
            }
        }
        System.out.println();
    }

Wenn ich nun die Ausgabe nach Zeile 29 einfüge ist der Output nicht "richtiger".

Die Ausgabe sollte wie folgt sein:

 

[mihe7]

Ich werde leider aus der Erklärung nicht viel schlauer.

Du hast ein Array mit n Elementen. Du hast eine Schleife mit einem Schleifenzähler i. Die Elemente zwischen 0 und i (excl.) sind in jedem Fall sortiert. In der Schleife fügst Du ein Element ein. Danach weißt Du, an welcher Stelle das Element eingefügt wurde (Index j). Außerdem ist klar, dass das nächste noch nicht sortierte Element an Index i+1 steht.

Die Ausgabe erfolgt nach dem Einfügen, damit hast Du alles beisammen, was Du brauchst:

// sortierter Bereich
für alle k = 0 bis i
    falls k == j und j < i, gib arr[k] in Klammern aus, sonst ohne Klammerm
gib einen senkrechten Strich aus

// unsortierter Bereich
für alle k = i+1 bis arr.length - 1
    falls k == i+1, gib arr[k] aus, sonst gib einen "." aus
gib einen Zeilenumbruch aus

 

[KonradN]

Nur so als kleiner Tipp: Wenn man Dinge ordentlich benennt, dann versteht man so Dinge deutlich einfacher und der Code wird aus lesbarer. Das hantieren mit i, j, k, ... ist doch alles andere optimal.

 

[emreiu]

Du hast ein Array mit n Elementen. Du hast eine Schleife mit einem Schleifenzähler i. Die Elemente zwischen 0 und i (excl.) sind in jedem Fall sortiert. In der Schleife fügst Du ein Element ein. Danach weißt Du, an welcher Stelle das Element eingefügt wurde (Index j). Außerdem ist klar, dass das nächste noch nicht sortierte Element an Index i+1 steht.

Die Ausgabe erfolgt nach dem Einfügen, damit hast Du alles beisammen, was Du brauchst:

// sortierter Bereich
für alle k = 0 bis i
    falls k == j und j < i, gib arr[k] in Klammern aus, sonst ohne Klammerm
gib einen senkrechten Strich aus

// unsortierter Bereich
für alle k = i+1 bis arr.length - 1
    falls k == i+1, gib arr[k] aus, sonst gib einen "." aus
gib einen Zeilenumbruch aus

Danke für den Tipp. Er hat leider nicht ganz zum gewünschten Output geführt, aber dafür mich auf den richtigen Pfad.
Ich habe es nun endlich auf die folgende Weise gelöst und bekomme die gewünschte Ausgabe exakt:

package SelfstudyJ_SortAndSearch;

import java.util.Random;
import java.util.Scanner;

public class A01_insertionSort {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] a = testData(sc.nextInt(), sc.nextInt(), sc.nextInt());
        printArray(a);
        insertion(a);
        printArray(a);
        sc.close();
    }

    public static int[] testData(int size, int max, int seed) {
        int[] a = new int[size];
        Random r = new Random(seed);
        for (int i = 0; i < a.length; i++)
            a[i] = r.nextInt(max);
        return a;
    }

    public static void insertion(int[] numbers) {
        int i;
        int insert = -1;
        for (i = 1; i < numbers.length; i++) {
            printArray(numbers, i, insert);
            insert = -1;
            int j = i;
            int tmp = numbers[i];

            while (j > 0 && tmp < numbers[j - 1]) {
                numbers[j] = numbers[j - 1];
                j--;
            }
            numbers[j] = tmp;
            if (j != i) {
                insert = j;
            }
        }
        printArray(numbers, i, insert);
    }

    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.printf(" %02d  ", i);
        }
        System.out.println();
    }

    public static void printArray(int[] arr, int i, int insert) {
        for (int k = 0; k < arr.length; k++) {
            if (k == insert && insert != i) {
                System.out.printf("(%02d) ", arr[k]);
            } else if (k < (i - 1) || k == i) {
                System.out.printf(" %02d  ", arr[k]);
            } else if (k < i) {
                System.out.printf(" %02d| ", arr[k]);
            } else {
                System.out.printf("%3c  ", '.');
            }
        }
        System.out.println();
    }
}

Möglicherweise könnte man den Code noch hier und da vereinfachen bzw. kürzen, aber fürs erste reicht er mir.

 

[mihe7]

Danke für den Tipp. Er hat leider nicht ganz zum gewünschten Output geführt

Ja, das kann schon sein. Der Pseudocode ist nur eine grobe Skizze 😀