Formatiertes Output bei Insertion Sort

emreiu

Mitglied

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.

Java:
 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();
    }
 
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.
 
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.
Java:
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".
1703939709643.png
Die Ausgabe sollte wie folgt sein:
1703939869860.png
 
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:

Code:
// 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
 
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.
 
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:

Code:
// 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:
Java:
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.
 

Neue Themen


Zurück
Oben