Gegebenes Array sortieren, indem zufällige Zahlenpaare aus Array ausgewählt werden

[lynnmiliwin]

Hallo

In meiner Aufgabe muss ich ein Array sortieren, indem es zufällige Zahlenpaare aus dem Array auswählt und in die richtige Reihenfolge setzt. Zudem muss es zählen, wie oft es zu einem Tausch gekommen ist. Wenn ich die Methode geschrieben habe, muss ich ein Test durchlaufen lassen, welches dieses Array sortieret: {1, 3, 2, 6, 5, 4}. Wenn ich den Test richtig interpretiert habe, kann in diesem Beispiel mind. 1 Tausch oder max. 3 tausche erfolgen.

Untenstehend mein Code. Leider würde es nur tauschen wenn ich die Zahlenpaare nicht zufällig bilden müsste. Ich habe es auch mit random versucht aber ich komme wirklich nicht weiter.

Hat jemand vielleicht eine Idee?

Danke für euche Unterstützung! (

int count = 0;

        int length = array.length;
        for (int i = 0; i < length - 1; i++) {
            //search smallest Element
            int minPos = i;
            int min = array[minPos];
            for (int j = i + 1; j < length; j++) {
                if (array[j] < min) {
                    minPos = j;
                    min = array[minPos];

                }
            }
            if (minPos != i) {
                array[minPos] = array[i];
                array[i] = min;
                count++;
            }
        }
        return count;
    }
}

 

[berndoa]

Irgendwie vermute ich dass da noch was an Angaben fehlt...

Ich meine, rein logisch betrachtet:
Wenn ich ein unsortiertes Array habe und "rein zufällig" immer nur das Paar an den indizes (22,4) immer wieder miteinander vergleiche, wird das Programm ja nie fertig.
Gut, man könnte annehmen dass jedes zufällig gewählte Paar nur einmal betrachtet wird.
Ist dann nach letztlich Durchgehen aller Paare Alles sortiert?
Keien Ahnung. So oder so ein sehr umständliches Vorgehen.

Hast du die Originalaufgabe zu dem Ganzen?

"Wenn ich den Test richtig interpretiert habe, kann in diesem Beispiel mind. 1 Tausch oder max. 3 tausche erfolgen."
Keine Ahnung was du da meinst oder wie du drauf kommst.

Es fehlen Erklärungen zu diesem "zufällig Paare raussuchen und sortieren" Part.
Poste mal die Originalaufgabe.

Ich habe jetzt deinen Code nicht im Detail betrachtet aber vermutlich gehst du da die elemente vorne nach hinten durch und guckst alle Paarungen mit Elementen rechts vom aktuellen Element an und vertauschst.

Links bildet sich also ein sortiertes Array während rechts das unsortierte Array schrumpft. Oder so.

Was aber so oder so nichts mit diesem zufälligen Paarauswählen zu tun hat und keine Ahnung ob der Algorithmus so überhaupt gemeint war.
Schließlich ist ja kein Algorithmus gegeben bisher...


Ansosnten, gut kann man halt einen Algorithmus bauen, der dem Muster folgt:
1. wähle 2 random Zahlen aus dem Array und vertausche sie wenn nötig dmait links die kleienre steht.
2. Gucke ob Array sortiert ist. Falls nein, gehe zu 1.
Falls ja, Programm fertig und gib sortiertes Array aus.

Und kannst halt mitzählen wie oft der Schritt 1 umgesetzt wurde.
Aber höchst ineffizient und höchstens gut um zu zeigen wie wichtig es ist, beim Erfinden eines Sortieralgorithmus den kopf zu benutzen und systematishc (und eben nicht random) vorzugehen.

Ansosnten musst du dir natürlich grundsätzlich überlegen, wenn du eine Zufallszahl Math.random() aus dem Intervall [0,1) hast, wie du das skalierst, dmai es eine Zufallszahl aus [0, Arraylänge] wird.

 

[thecain]

Das Verfahren gibts schon und wird z.B. Bogosort genannt: https://de.m.wikipedia.org/wiki/Bogosort
Auf der Wiki seite sind bei genauem Hinschauen auch Code Beispiele zu finden

 

[berndoa]

Kommt der Ausdruck von lateinisch "Bogus" also Unsinn?


Edit: Gerade die Seite angeguckt:
Er sucht wirklich random zufällig Paare die er vertauscht bis er irgendwie irgendwo irgendwann mal zufällig eine sortierte Lsite hat.
Da hatte ich mit meinem sehr idiotischen Algorithmus ja shcon den Nagel auf den Kopf getroffen 🙃

Dämlicher Algorithmus aber dann ist das Vorgehen ja klar.

Wäre nur noch interessant zu wissen wie wahrscheinlich es ist dass er nie zum Ende kommt weil er bspw. immer wieder Dasselbe Paar untersucht.
Ist ja stochastik gesehen durchaus im bereich des Möglichen, nur verschwindend unwahrscheinlich

 

[thecain]

Bei unendlich Zeit und einem korrekten Random würde ich sagen es ist Unmöglich.

Und ja, der Algorithmus ist zu Lehrzwecken und keinstenfalls Performant

 

[berndoa]

Ja, das ist so eine Sache wo ich den Kopf nicht drum kriege.
Einerseits gibt es stochastisch ja ein (unendlich langes) Baumdiagramm, wo jede Verzweigung eine einfache Wahrscheinlichkeit hat.
Die Wahrscheinlichkeit für bspw das Paar (1,5) lässt sich (bei kenntnis der Arraylänge) berechnen und ist definitiv eine fest Zahl P mit 0<P<1.

Für eine Runde (1,5) ziehen käme man dann auch Wahrshceinlichkeit P, für 2 Runden mit je (1,5) auf P^2, usw.
n Runden wäre die Wahrshceinlichkeit P^n.

Offensichtlich sit dass für unendlich viele Runden der Grenzwert 0 ist da 0<P<1.

Aber das gilt ja im Prinzip für wirklich jeden (unendlich langen) Pfad im Baumdiagramm.
Und doch ist die Summe aller Pfade doch 1.

Liegt aber vermutlich daran dass bei gleichverteilung es an jedem knoten k pfade gibt und jeder davon Wahrshceinlichkeit 1/k hat, also in summe wieder
k*1/k=1.

Komme trotzdem nicht klar damit dass man rein logishc immer dasselbe paar wählen kann und die wahrshceinlichkeit im grenzwert Null sien soll.
Schließlich ist es ja möglich, genauso wie ich endlos immer wieder einen Würfel werfen und jedes mal ne 6 haben kann.

Es wird zwar mit jedem Wurf unwarhsceinlicher, den Streak aufrechtzuerhalten aber unmöglich wird es nie.
Ausser iM Grenzwert.

Aber gut, da shat nun wirklich nichts mehr mit dem programmieren der Aufgabe zu tun.
Alogirthmus habe ich ja shcon in peudocode vorgesagt, muss er ihn nur noch schreiben

Und halt nopch de zählervariable an sinnvoller stelle definieren und inkrementieren

 

[KonradN]

Wenn ich die Methode geschrieben habe, muss ich ein Test durchlaufen lassen, welches dieses Array sortieret: {1, 3, 2, 6, 5, 4}. Wenn ich den Test richtig interpretiert habe, kann in diesem Beispiel mind. 1 Tausch oder max. 3 tausche erfolgen.

Der Test ist falsch. Es gibt den Fall mit 4 Zahlenpaare tauschen:
1. Tausch: 3 und 2
2. Tausch: 5 und 4
3. Tausch: 6 und 4
4. Tausch: 6 und 5
==> erst nach 4 mal tauschen sind wir bei der Reihenfolge durch.

Und als Minimum gibt es zwei: 3 mit 2 und 6 mit 4 müssen getauscht werden.

Das was du suchtest ist kein reines Bogosort...

Das ist richtig, da nicht zufällig getauscht wird sondern zwei zufällige Elemente werden in die richtige Reihenfolge gebracht.
Bei Deinem Code wird aber kein zufälliges Zahlenpaar genommen und es wird auch deutlich mehr als ein Zahlenpaar getauscht in Deiner Iteration. Damit erfüllt Dein Code aus meiner Sicht nicht die Vorgabe:

In meiner Aufgabe muss ich ein Array sortieren, indem es zufällige Zahlenpaare aus dem Array auswählt und in die richtige Reihenfolge setzt.

 

[lynnmiliwin]

Irgendwie vermute ich dass da noch was an Angaben fehlt...

Ich meine, rein logisch betrachtet:
Wenn ich ein unsortiertes Array habe und "rein zufällig" immer nur das Paar an den indizes (22,4) immer wieder miteinander vergleiche, wird das Programm ja nie fertig.
Gut, man könnte annehmen dass jedes zufällig gewählte Paar nur einmal betrachtet wird.
Ist dann nach letztlich Durchgehen aller Paare Alles sortiert?
Keien Ahnung. So oder so ein sehr umständliches Vorgehen.

Hast du die Originalaufgabe zu dem Ganzen?

"Wenn ich den Test richtig interpretiert habe, kann in diesem Beispiel mind. 1 Tausch oder max. 3 tausche erfolgen."
Keine Ahnung was du da meinst oder wie du drauf kommst.

Es fehlen Erklärungen zu diesem "zufällig Paare raussuchen und sortieren" Part.
Poste mal die Originalaufgabe.

Ich habe jetzt deinen Code nicht im Detail betrachtet aber vermutlich gehst du da die elemente vorne nach hinten durch und guckst alle Paarungen mit Elementen rechts vom aktuellen Element an und vertauschst.

Links bildet sich also ein sortiertes Array während rechts das unsortierte Array schrumpft. Oder so.

Was aber so oder so nichts mit diesem zufälligen Paarauswählen zu tun hat und keine Ahnung ob der Algorithmus so überhaupt gemeint war.
Schließlich ist ja kein Algorithmus gegeben bisher...


Ansosnten, gut kann man halt einen Algorithmus bauen, der dem Muster folgt:
1. wähle 2 random Zahlen aus dem Array und vertausche sie wenn nötig dmait links die kleienre steht.
2. Gucke ob Array sortiert ist. Falls nein, gehe zu 1.
Falls ja, Programm fertig und gib sortiertes Array aus.

Und kannst halt mitzählen wie oft der Schritt 1 umgesetzt wurde.
Aber höchst ineffizient und höchstens gut um zu zeigen wie wichtig es ist, beim Erfinden eines Sortieralgorithmus den kopf zu benutzen und systematishc (und eben nicht random) vorzugehen.

Ansosnten musst du dir natürlich grundsätzlich überlegen, wenn du eine Zufallszahl Math.random() aus dem Intervall [0,1) hast, wie du das skalierst, dmai es eine Zufallszahl aus [0, Arraylänge] wird.

Also die Aufgabe sieht folgendermasen aus:

import java.util.Arrays;

public class RandomSort {

    public static void main(String[] args) {
        int[] array = {1, 2, 6, 5, 3, 4, 7, 9, 8, 0};
        System.out.println(Arrays.toString(array));

        int swaps = randomSort(array);
        System.out.println("Sortiert: " + Arrays.toString(array));
        System.out.println(swaps + " mal getauscht");
    }


    /**
     * Sortiert das gegebene Array, indem wiederholt zufällig
     * Zahlenpaare im Array ausgewählt und in die richtige
     * Reihenfolge gebracht werden. Nach jedem Tausch wird
     * mittels isSorted geprüft, ob das Array bereits sortiert
     * ist. Gibt die Anzahl erfolgter Tauschoperationen zurück.
     */
    public static int randomSort(int[] array) {
        int count = 0;

        int length = array.length; // {1,2,3,6,5,4}
        for (int i = 0; i < length - 1; i++) {
            //search smallest Element
            int minPos = i;
            int min = array[minPos];
            for (int j = i + 1; j < length; j++) {
                if (array[j] < min) {
                    minPos = j;
                    min = array[minPos];

                }
            }
            if (minPos != i) {
                array[minPos] = array[i];
                array[i] = min;
                count++;
            }
        }
        return count;
    }
}

Und einer der Tests die bei mir immer fehlschlagen ist folgender:

 @Test
    public void testRandomSortOneOrThreeSwaps() {
        // teste mehrmals, da zufällig
        int oneSwap = 0;
        int threeSwaps = 0;
        for (int i = 0; i < 100; i++) {
            // 1 oder 3 swaps möglich:
            int[] array = {1, 2, 3, 6, 5, 4};
            int[] copy = Arrays.copyOf(array, array.length);
            int swaps = RandomSort.randomSort(array);
            Arrays.sort(copy);
            assertArrayEquals(copy, array);
            if (swaps == 1) {
                oneSwap++;
            } else if (swaps == 3) {
                threeSwaps++;
            } else {
                fail("1 oder 3 Swaps erwartet, waren " + swaps);
            }
        }
        if (oneSwap == 0) {
            fail("Nie in 1 Swap erfolgt. Sehr wahrscheinlich verbuggt...");
        }
        if (threeSwaps == 0) {
            fail("Nie in 3 Swaps erfolgt. Sehr wahrscheinlich verbuggt...");
        }
    }

Wenn ich nun den unteren Teil ansehe, erwartet der Test, dass es in 1 oder 3 Swaps erfolgt. Ich hoffe das klärt etwas auf was ich eigentlich tun sollte

Danke bereits an alle, die mir Vorschläge gegeben haben.

 

[KonradN]

Du hast da kein RandomSort implementiert - oder wo siehst Du:

• Das ermitteln von zufälligen Zahlenpaaren?
• Die Prüfung on das Array sortiert ist?

Also ich sehe hier als erstes, dass Du den gesuchten Algorithmus nicht umgesetzt hast!

 

[lynnmiliwin]

Du hast da kein RandomSort implementiert - oder wo siehst Du:

• Das ermitteln von zufälligen Zahlenpaaren?
• Die Prüfung on das Array sortiert ist?

Also ich sehe hier als erstes, dass Du den gesuchten Algorithmus nicht umgesetzt hast!

Ja ich weiss, ich wusste nicht wie. Wenn ich nun die anderen Beiträge durchlese, lese ich von dem Bogosort-Algorithmus? Wäre dieser hier angebracht? Dann kann ich das mal genauer anschauen und versuchen zu implementieren.

Arrays sind Neuland für mich, deshalb die Frage.

 

[KonradN]

Woran scheitert es denn genau? Der Bogosort Algorithmus ist noch etwas anders - Da bin ich mir nicht sicher, ob und wie Dir das wirklich weiter hilft.

Die Aufgabe ist ja im Kommentar beschrieben:

Sortiert das gegebene Array, indem wiederholt zufällig
Zahlenpaare im Array ausgewählt und in die richtige
Reihenfolge gebracht werden. Nach jedem Tausch wird
mittels isSorted geprüft, ob das Array bereits sortiert
ist. Gibt die Anzahl erfolgter Tauschoperationen zurück.

Was also gebraucht wird, sind zufällige Zahlenpaare. Kannst Du zufällige Zahlen bekommen?
Wenn du damit auf Zahlen im Array zugreifen willst: In welchem Bereich müssten die Zahlen dann sein?

Um die Elemente in die richtige Reihenfolge zu bekommen: Was wäre da die Bedingung? Wie bekommst Du die Zahlen in die richtige Reihenfolge?

Und zu guter Letzt: Es soll eine Methode isSorted geben - kannst Du so eine Methode schreiben? Was musst Du prüfen, um das sicher zu stellen?

 

[KonradN]

und in den bereits sortierten Teil einsortiert.

Und genau das ist eben nicht die Anforderung. Es sollen lediglich die zwei zufällig gewählten Elemente in die richtige Reihenfolge gebracht werden.

Ansonsten könnte das bei längeren Listen Stunden dauern und die maximale Anzahl der Vertauschungen wäre auch nicht beschränkt.

Wenn ich Dich richtig verstehe, dann sagst Du damit doch selbst, dass Du den Algorithmus angepasst hast um diesen zu optimieren. Damit sollte auch Dir klar sein, dass dies eben nicht mehr der Anforderung entspricht.

Merke: Erst lesen, dann denken, dann warten, dann antworten. Unsinn kannst du dir doch sparen.

Ok, Du bist unser allseits bekannter Tobias. Spare Dir doch einfach solche dummen Anmachen und befolge diese selbst. Wenn Du die Anforderungen gelesen und dann darüber nachgedacht hättest, dann hättest Du Dir diesen Unsinn sparen können. Vor allem würdest Du Dir, so Du dieses schlechte Benehmen ablegen würdest, die ständige Erstellung von neuen Accounts sparen.

 

[berndoa]

Laut dem Kommentar müsste ja eigentlich mein 2 Schritt Algorithmus dann genau der Richtige sein, Effizienz ist hier scheinbar nicht wichtig.

 

[KonradN]

Laut dem Kommentar müsste ja eigentlich mein 2 Schritt Algorithmus dann genau der Richtige sein, Effizienz ist hier scheinbar nicht wichtig.

Ja genau, so Du Dich auf Deine Aussage:

1. wähle 2 random Zahlen aus dem Array und vertausche sie wenn nötig dmait links die kleienre steht.
2. Gucke ob Array sortiert ist. Falls nein, gehe zu 1.

beziehst, dann ist das so genau richtig.

 

[Jw456]

Bei dem Code aus dem link von Thecain findet zb kein prüfen statt ob die beiden Paare in der richten Reihenfolge sind . Sie werde da ja immer getauscht. Was nicht der Aufgabe entspricht.

Tipp du musst auch Prüfen welcher index ( a ,b ) den du bekommst der Größere … ist

​