Zufallszahlen & Laufzeitmessung (insertionSort)

Anas

Anas

Mitglied
Liebe Java-Community,

ich habe ein Problem mit einer für mich sehr großen Aufgaben! :D

Ich soll zwei Methoden schreiben, nämlich den Algorithmus insertionSort und einmal
die Boolean isSorted ... das war kein Problem! (haufenweise Pseudo-Codes im Netz)

Bei der Main Methode tauchen die Schwierigkeiten bei mir auf. Folgende Aspekte
müssen vorhanden sein:

1) erstes Argument die Feldgröße übergeben und als zweites (optional) Argument
die Befüllungsart des Feldes (auf, ab, rand = aufsteigend, absteigend, zufällig)

2) danach soll insertionSort das befüllte Array sortieren und dabei soll die Zeit gemessen werden

3) letztendlich soll das Array auf korrekte Sortierheit getestet werden, sprich ausgeben Feld sortiert oder nicht

4) das Feld und die Zeit sollen nur bei höchstens 100 Elementen angegeben werden
___

1) kein Schimmer wie das gehen soll bis auf die zufällige Variante .. Math.random sollte das dort klären oder?

2) auch gar keinen Schimmer wie ich das bewerkstelligen soll! :D

3) reicht es dort, wenn ich einfach mit system.out.printlin arbeite und ein simple if/else?

4) if/else sollte auch hier klären mit einfache system.out.println
___

Die Main Methode sollte mit Integer.parseInt arbeiten! :D

Hier ist noch mein Code, soweit wie ich halt gekommen bin.

Danke im Voraus!

Gruß




Java:
import java.util.Random;

public class InsertionSort
{

    public static void main(String args[])
    {
        Random rd = new Random();
        int arr[] = new int[10000];
       // arr = {1,4,6,78,9,5};
        for(int i = 0; i < arr.length; i++)
        {
            arr[i] = rd.nextInt();
            System.out.println(arr[i]);
        }
    }

    public static void insertionSort(int[] a)
    {
        int key = a.length;
        for (int j = 2; j < a.length; j++)
        {
            key = a[j];
            int i = j - 1;
            while ( i >0 && a[i] > key)
            {
                a[i + 1] = a[i];
                i = i - 1;
            }
            a[i + 1] = key;
        }
    }

/*  public static boolean isSorted(int[] array)
    {
        for (int i = 0; i < array.length; i++)
        {
            for (int j = i; j < array.length; j++)
            {
                if (array[i] > array[j])
                {
                    return false;
                }
            }
        }
        return true;
    }
 */

    public static boolean isSorted(int[] array)
    {
        for (int i = 0; i < array.length; i++)
        {
            for (int j = i; j < array.length; j++)
            {
                assert array[i] > array[j]:"array[i] größer als array[j]";
            }
        }
        return true;
    }

}
 

Anhänge

  • InsertionSort.java
    1,4 KB · Aufrufe: 3
Zuletzt bearbeitet von einem Moderator:
Anas

Anas

Mitglied
Dein InsertionSort war völlig falsch... ich hab's dir mal berichtigt und Aufgabe 1) gemacht:

Java:
import java.util.Arrays;
import java.util.Random;
import java.util.function.BiFunction;

public class InsertionSort {

    public static void insertionSort(int[] a, String... strings) {
        BiFunction<Integer, Integer, Boolean> c = (i, j) -> i > j;
        if (strings != null && strings.length > 0
                && ("ab".equals(strings[0]) || "rand".equals(strings[0]) && Math.random() < 0.5)) {
            c = (i, j) -> i < j;
        }
        int n = a.length;
        for (int j = 1; j < n; j++) {
            int key = a[j];
            int i = j - 1;
            while (i > -1 && c.apply(a[i], key)) {
                a[i + 1] = a[i];
                i--;
            }
            a[i + 1] = key;
        }
    }

//    public static boolean isSorted(int[] array) {
//        for (int i = 0; i < array.length; i++) {
//            for (int j = i; j < array.length; j++) {
//                if (array[i] > array[j]) {
//                    return false;
//                }
//            }
//        }
//        return true;
//    }

    public static boolean isSorted(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = i; j < array.length; j++) {
                assert array[i] > array[j] : "array[i] größer als array[j]";
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Random rd = new Random(1);
        int arr[] = new int[10];
        // arr = {1,4,6,78,9,5};
        for (int i = 0; i < arr.length; i++) {
            arr[i] = rd.nextInt();
            System.out.println(arr[i]);
        }

        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
        insertionSort(arr, "ab");
        System.out.println(Arrays.toString(arr));
        insertionSort(arr, "auf");
        System.out.println(Arrays.toString(arr));
        insertionSort(arr, "rand");
        System.out.println(Arrays.toString(arr));
    }

}
Die InsertionSort Methode habe ich von der Vorlesungsfolie abgeschrieben. Das war ein Pseudocode.
Deine Lösung ist auch völlig korrekt, Danke dafür.
Mein Problem ist immer noch mit der main-Methode.
Kann ich dir bitte PN schreiben!
 
Zuletzt bearbeitet:
kneitzel

kneitzel

Top Contributor
Also hier möchte ich mich auch noch einmal kurz einmischen wenn ich darf:
und einmal die Boolean isSorted ... das war kein Problem!
Hier möchte ich kurz anmerken, dass < transitiv ist. Aus a < b und b < c folgt automatisch, dass a < c ist.
Daher ist es unnötig, da mit zwei verschachtelten Schleifen zu arbeiten. Eine einfache Schleife, die einmal durch das Array geht und sicherstellt, dass zwei benachbarte Elemente sortiert sind, reicht also!

Und dann ist das eine Methode, die true / false liefern soll. Da hat ein Assert nichts zu suchen! Das ist eine isSorted und kein checkSorted oder validateSort! Also bitte dieses assert gleich streichen und mit dem if ersetzen um ggf. false auszugeben.

Dein InsertionSort war völlig falsch...
Das sehe ich nicht so. Er hat zwar einen kleinen Fehler drin gehabt und eine Sache war unnötig, aber der Algorithmus selbst ist gut zu erkennen:
Unschön: Bei der Deklaration von key muss nichts initialisiert werden. Der Wert, den Du initialisierst, wird nie verwendet.
Falsch: Die Schleife fängt bei 2 an. Du willst beim 2ten Element anfangen, aber da der Index bei 0 startet, muss da ab 1 los gegangen werden.

Bei Lösungen ist die Frage, in wie weit Du schon mit Lambda Ausdrücken und BiFunction und so gearbeitet hast. Vermutlich ist dies nicht das erwartete Niveau. (Und wenn, dann würde ich ein funktionales Interface nutzen das dies auch vom Namen her abdeckt. Hier bietet sich also Comparator an und wenn Lambdas noch unbekannt sind, dann kann man das auch traditionell bauen.
Und die Parameter der Lösungs-Methode sind nicht richtig, denn es soll ja auch kein Array mehr übergeben werden sondern die Größe des Arrays!

Unabhängig davon ist es absolut nicht anzuraten, alles so in eine Methode zu packen! Das ist in keiner Weise mehr leserlich.

@Anas:
Ist die Aufgabe denn so wirklich korrekt wieder gegeben worden? Ich selbst hätte erwartet, dass ihr InsertionSort testen sollt auf Arrays, die entweder zufällig oder schon sortiert sind (absteigend oder aufsteigend).

Generell ist das total einfach mit den Algorithmen die Du schon als Basis hast:
- Initialisieren tust Du du immer mit Zufallszahlen.
- Wenn auf oder ab gefordert ist, dann sortierst Du das Array
- Wenn ab gefordert ist, dann drehst Du noch um.
(Alternativ kannst Du InsertionSort umändern, so dass die Sortierreihenfolge mitgegeben wird. Oder Du arbeitest mit Comparator, der übergeben wird)

Damit ist die Vorbereitung abgeschlossen und Ihr könnt die Laufzeit testen von dem Aufruf auf dem Array. Evtl. habt ihr dazu ja auch schon Code. Generell ist es ein Aufruf, die Zeit in einer Variable zu speichern, dann der Aufruf zum sortieren und im Anschluss dann erneut die Zeit in einer Variable speichern. Im Anschluss kann dann die Differenz berechnet werden.

So hast du relativ einfache Methoden, die übersichtlich sind und korrekte Namen haben.

Ich würde Dir empfehlen, diesen Ansatz zu verfolgen. Und hier kann man dann auch gerne bei Fragen gezielt weiter unterstützen.

Edit: Da ich dann doch nicht mit a) b) c) ... die einzelnen Punkte gelistet habe, habe ich das erste a) auch entfernt.
 
Anas

Anas

Mitglied
Danke für Deine Antwort und Deine Korrektur.
Die Aufgabe war komplett wie folgt gegeben:
Diese Aufgabe besteht aus mehreren Teilen. Bitte lesen Sie sich die Aufgabe vorher komplett durch und überprüfen Sie nach der Bearbeitung, ob Sie nichts vergessen haben.
• Legen Sie eine Klasse InsertionSort an.
• Schreiben Sie eine Methode public static void insertionSort(int[] array), die den Algorithmus InsertionSort aus der Vorlesung implementiert, das die Werte in einem Array in aufsteigender Reihenfolge sortiert.
• Schreiben Sie eine Methode public static boolean isSorted(int[] array), welche überprüft, ob das Array array aufsteigend sortiert ist.
• Stellen Sie mittels Assertions die Korrektheit Ihres Programms sicher (siehe Hinweise zu Assertions).
• Schreiben Sie die main-Methode, die den Algorithmus wie folgt testet:

– Das Programm bekommt als erstes Argument die Feldgröße übergeben und als optionales zweites Argument die Befüllungsart dieses Feldes. Als erstes Argument sollen alle natürlichen Zahlen inklusive der 0 akzeptiert werden.
Beispiel: java Sortierung 10000 rand Beachten und behandeln Sie auch Fehleingaben (s.u.) bei den Übergabeparametern!
Der bei Fehleingaben ausgegebene Text soll mit "FEHLER: " beginnen und eine der unten aufgeführten Fehlermeldungen sowie eine Hilfsnachricht zum korrekten Aufruf des Programms ausgeben.

– Das Feld kann auf-, absteigend oder zufällig mit int-Werten gefüllt werden. Entsprechend lauten die Werte für das zweite Argument: auf, ab bzw. rand. Wenn kein zweiter Parameter übergeben wurde, soll das Array mit zufälligen Werten gefüllt werden. Beachten Sie hierzu die Hinweise zu den Zufallszahlen.

– Um die Vergleichbarkeit Ihrer Lösungen zu ermöglichen soll zusätzlich bei der zufälligen Befüllung ein Seed gesetzt werden. Der Seed für die Abgabe lautet: 951 – Ergänzen Sie die main-Methode, so dass die Methode insertionSort das befüllte Array sortiert.

– Zusätzlich soll die Anzahl der Vergleiche zwischen zwei Elementen des Arrays gezählt werden, die notwendig sind um das Array zu sortieren. Legen Sie dazu z.B eine Klassenvariable an, die die Anzahl der benötigten Vergleiche speichert. Für jeden Vergleich von zwei Elementen in dem Array soll die Variable um 1 inkrementiert werden. Beachten Sie, dass auch bei bereits sortierten Arrays möglicherweise Vergleiche zwischen Elementen ausgeführt werden müssen.

– Anschließend soll geprüft werden, ob das Array korrekt sortiert ist, und entsprechend "Feld ist sortiert!" bzw. "FEHLER: Feld ist NICHT sortiert!" ausgegeben werden.

– Bei höchstens (inklusive) 100 Elementen soll in einer neuen Zeile das erzeugte unsortierte Feld und in einer weiteren Zeile das sortierte Feld ausgegeben werden. Die Elemente der Liste sollen durch Leerzeichen getrennt werden. Dabei muss die vorgegebene Reihenfolge eingehalten werden. Bsp. eines korrekten Aufrufes:Input: java InsertionSort 10 ab Output: 10 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10 Feld ist sortiert! Das Sortieren des Arrays hat 45 Vergleiche benötigt. • Die Fehlerbehandlung soll dabei wie folgt aussehen:

– Es soll als erstes geprüft werden ob die richtige Anzahl der Parameter mitgegeben wurde. Falls nicht soll diese Fehlermeldung ausgegeben werden: FEHLER: Es müssen zwischen 1 und 2 Parameter angegeben werden. – Danach soll geprüft werden ob die mitgegebenen Parameter korrekte Eingaben sind.
∗ Falls der erste Parameter keine natürliche Zahl ist soll folgende Fehlermeldung ausgegeben werden: FEHLER: Der erste Parameter muss eine natürliche Zahl sein.
∗ Falls der zweite Parameter keine bekannte Füllmethode ist soll folgende Fehlermeldung ausgegeben werden:
FEHLER: Unbekanntes Vorsortierverfahren: wobei mit dem übergebenen Parameter ersetzt werden soll.

– Zusätzlich soll im Fehlerfall, wie auf dem ersten Übungsblatt, eine Hilfsnachricht ausgegeben werden: Aufruf mit: java InsertionSort n [auf|ab|rand] Beispiel: java InsertionSort 10000 rand – Die Ausgaben zu fehlerhaften Eingaben sollen dann z.B. wie folgt aussehen: Input: java InsertionSort Output: FEHLER: Es müssen zwischen 1 und 2 Parameter angegeben werden. Aufruf mit: java InsertionSort n [auf|ab|rand] Beispiel: java InsertionSort 10000 rand Input: java InsertionSort 100 meineVorsortierung Output: FEHLER: Unbekanntes Vorsortierverfahren: meineVorsortierung Aufruf mit: java InsertionSort n [auf|ab|rand] Beispiel: java InsertionSort 10000 rand
....................................................................................
Unschön: Bei der Deklaration von key muss nichts initialisiert werden. Der Wert, den Du initialisierst, wird nie verwendet.
Falsch: Die Schleife fängt bei 2 an. Du willst beim 2ten Element anfangen, aber da der Index bei 0 startet, muss da ab 1 los gegangen werden.
Das stand aber in der Vorlesung als Pseudocode.
 
kneitzel

kneitzel

Top Contributor
Man kann da unterschiedlicher Meinung sein.
Ja, aber gewisse Meinungen sind einfach falsch. Auch wenn gewisse Dinge in der Aufgabenstellung nicht komplett gegeben waren, war da durchaus was gegeben, das Du schlicht nicht beachtet hast:
erstes Argument die Feldgröße übergeben und als zweites (optional) Argument
die Befüllungsart des Feldes (auf, ab, rand = aufsteigend, absteigend, zufällig)
Und das erfüllt Deine Lösung schlicht nicht!

Und der Insertion Sort vom TE ist im übrigen nur eine Umsetzung wie z.B. auf https://de.wikipedia.org/wiki/Insertionsort gebracht. Den Fehler in der Umsetzung habe ich aufgezeigt (Das erste Element wurde nicht in der Sortierung berücksichtigt - das ist alles)!
Und wenn in 5 Zeilen Pseudo-Code 3 Fehler enthalten sind
Und da es nur um einen Fehler ging, ist das eine Aussage, die einfach falsch ist. Du magst Probleme haben, so Dinge nachzuvollziehen, aber das ist schlicht Dein Problem.

Falsche Aussagen werden als solche bezeichnet und wenn (extrem) schlechter Code gepostet wird, dann werde ich das auch durchaus so bemerken (mit Begründungen! Lies diese vielleicht einfach mal. Vielleicht lernst Du dann auch noch etwas!)

Ich hoffe, das Thema ist damit erledigt und man kann jetzt auf die Themen des TE zurück kommen. Danke!
 
kneitzel

kneitzel

Top Contributor
@Anas Danke für die ausführliche Aufgabe. Diese kannst Du so fast 1:1 implementieren.

Also die Klasse InsertionSort hast Du ja schon fast komplett fertig.

Wichtig ist vielleicht noch eine Anmerkung zu
Stellen Sie mittels Assertions die Korrektheit Ihres Programms sicher (siehe Hinweise zu Assertions).
Dies bedeutet nicht, dass Du in isSorted dann so ein Assert einbaust. Denn die Korrektheit einer Methode isSorted(Array) besagt ja nicht, dass das Array sortiert sein muss. Wenn man sich das also überlegt, dann bedeutet dies: Du machst etwas und prüfst dann am Ende, ob etwas korrekt ist.
Prinzipiell könntest Du somit im Code gewisse Prüfungen machen. Also am Ende vom Sortieren hast Du dann ein Assert, dass isSorted(array) true ist.
Aber das macht keinen Sinn. Denn du gehst davon aus, dass Dein Code korrekt ist. Das prüfst Du nicht wirklich immer. Eine Validierung macht da nicht wirklich Sinn. Statt dessen ist es üblich, dass man Tests hat, die die Funktionalität testen. Also sowas wie Unit Tests (==> ggf. mal in Google nach suchen!).
Da ich aber nicht eure Vorlesung und damit die Erwartung des Professors kenne, kann ich hier nicht sagen, was genau gefordert wird. Aber wenn Du nach der Erstellung eines zufälligen Arrays noch ausgeben willst, ob es sortiert ist, dann wird deutlich: Da hat eine Assertion, wie sie dir als "Verbesserung" angeboten wurde, schlicht nichts verloren.

Das Programm bekommt als erstes Argument
Das verstehe ich so, dass hier die Argumente der main Methode verwendet werden sollen. main hat ja ein String Array als Parameter. Das wird dann auch bestätigt im Bespiel Aufruf:
java Sortierung 10000 rand

Somit sollte dann in der Klasse Sortierung (Somit hast Du (mindestens) zwei Klassen! Die erste Klasse hast du ja mit den beiden Methoden bereits fertig denke ich mal ...) in main die Parameter ausgewertet werden: Sind zwei Parameter gegeben? Ist der erste ein int? Ist der zweite gültig?
Beachten und behandeln Sie auch Fehleingaben (s.u.) bei den Übergabeparametern!

Das Feld kann auf-, absteigend oder zufällig mit int-Werten gefüllt werden.
Hier ist die Frage, wie man das interpretieren kann. Das Feld füllen kann durchaus bedeuten: Erst Zufallszahlen und dann schnell sortieren.
Wenn das aus Deiner Sicht nicht als "aufsteigend" füllen zählt (So ist das vermutlich gemeint), dann kann man natürlich hin gehen und die Zufallszahlen einschränken:
Von dem bisher größten Element bis Max wäre da eine Idee. Dann hat man aber keine gute Verteilung mehr. Wenn die erste Zahl durch Zufall die maximale Zahl ist, dann sind alle weiteren Zahlen diese maximale Zahl. So einen Algorithmus kann man sich aber auch durchaus überlegen.
In einer Methode kannst Du das ja einfach abbilden: Du hast min und max als Werte in der Methode. Dann kommt die Schleife, die Zufallszahlen erzeugt und einträgt. Wenn absteigend, dann wird das max immer auf das minimum von max und neuer Zufallszahl gesetzt. Bei aufsteigend wird das min immer auf das Maximum von min und der neuen Zufallszahl gesetzt.
Das wäre dann eine direkte Lösung, die Du implementieren könntest ...

Und so in der Art dann einfach mal schauen, ob Du da weiter kommen kannst. Den Anfang habe ich jetzt hoffentlich etwas verständlicher erläutern können.
 

Ähnliche Java Themen


Oben