3 Komponenten in einem Array mit unbekannter Länge vertauschen und nach Größe sortieren

[Astrova]

Hallo, 

ich bin ein bisschen am verzweifeln und hoffe, dass mir hier jemand helfen kann.

Mein Aufgabe lautet, dass ich die Werte der Komponenten eines Arrays an drei vorher zufällig gewählten Indizes so vertauschen soll, dass array[i1] ≤ array[i2] und array[i2] ≤ array[i3] gilt.

Ich stehe noch am Anfang meines Studiums und weiß nicht genau, wie ich das Lösen kann. 

Vielen Dank für jede Hilfe!

[0x00]

Da wir hier den Grundsatz Hilfe zur Selbsthilfe wertschätzen: Woran scheiterts denn? Hast du schon irgendwelche Lösungsansätze? Irgendwelche Ideen?

[Whiz-zarD]

Es gibt keine Arrays mit unbekannter Länge.

Die Länge eines Arrays ist immer bekannt, sie als ein ganzer Block im Speicher liegen. Die Größe muss also schon beim erstellen  bekannt sein und die Größe lässt sich auch nicht verändern.

Wie sehen denn ansonsten deine Versuche aus und was verstehst du nicht?

 

Bearbeitet 11. November 2021 von Whiz-zarD

[Astrova]

[ public static int[] arrayNext(int[] array, int i1, int i2, int i3) {

           if(array[i1] > array[i2]){

               int temp = array[i1];

                array[i1] = array[i2];

                array[i2] = temp;

            }

         if(array[i2] > array[i3]){

              int temp2 = i2;

              array[i2] = array[i3];

              array[i3] = temp2;

        }

       if(array[i1] > array[i2]){

            int temp3 = array[i1];

            array[i1] = array[i2];

            array[i2] = temp3;

       }

return array;

}]

[Astrova]

Gerade eben schrieb Astrova:

[ public static int[] arrayNext(int[] array, int i1, int i2, int i3) {

           if(array[i1] > array[i2]){

               int temp = array[i1];

                array[i1] = array[i2];

                array[i2] = temp;

            }

         if(array[i2] > array[i3]){

              int temp2 = i2;

              array[i2] = array[i3];

              array[i3] = temp2;

        }

       if(array[i1] > array[i2]){

            int temp3 = array[i1];

            array[i1] = array[i2];

            array[i2] = temp3;

       }

return array;

}]

ich weiß leider nicht genau, wie ich hier meinen code angemessen anzeigen lassen kann, aber das hier ist mein ansatz bis jetzt

 

[Astrova]

vor 14 Minuten schrieb Whiz-zarD:

Es gibt keine Arrays mit unbekannter Länge.

Die Länge eines Arrays ist immer bekannt, sie als ein ganzer Block im Speicher liegen. Die Größe muss also schon beim erstellen  bekannt sein und die Größe lässt sich auch nicht verändern.

Wie sehen denn ansonsten deine Versuche aus und was verstehst du nicht?

 

genau, die größe wird jedoch zufällig gesetzt in dieser aufgabe, 

meinen Ansatz habe ich unten gepostet

 

[Astrova]

vor 18 Minuten schrieb 0x00:

Da wir hier den Grundsatz Hilfe zur Selbsthilfe wertschätzen: Woran scheiterts denn? Hast du schon irgendwelche Lösungsansätze? Irgendwelche Ideen?

unten habe ich meinen ansatz gepostet

[Whiz-zarD]

vor 19 Minuten schrieb Astrova:

ich weiß leider nicht genau, wie ich hier meinen code angemessen anzeigen lassen kann, aber das hier ist mein ansatz bis jetzt

Im Texteditor gibt es ein Button, mit dem du Code einfügen kannst.

Im Grunde hast du ja schon richtig erkannt, dass du die Zahlen sortieren musst und dass du das Sortieren mit den Tauschen der Position realisieren kannst. Diesbezüglich schaue dir dazu mal den Bubblesort-Algorithmus an.

[Astrova]

vor 18 Minuten schrieb Whiz-zarD:

Im Texteditor gibt es ein Button, mit dem du Code einfügen kannst.

Im Grunde hast du ja schon richtig erkannt, dass du die Zahlen sortieren musst und dass du das Sortieren mit den Tauschen der Position realisieren kannst. Diesbezüglich schaue dir dazu mal den Bubblesort-Algorithmus an.

vielen dank! ok super, das schaue ich mir einmal an

 

 

[Alaric]

Sofern ich deine Aufgabe richtig verstanden habe:

Es gibt ein Array, dass eine beliebige Länge haben kann.

Nun sollen 3 Zufällige Indexe gewählt werden.

Das Array wird aufsteigend sortiert, aber nur die gewählten Indexe sollen berücksichtigt werden.

Dann könnte die Lösung so aussehen:

public class App {
    public static void main(String[] args) throws Exception {
        //Array Egal welcher Länge instanziieren und mit irgendwelchen Werten füllen
        int[] array = new int[6];
        array[0] = 4;
        array[1] = 1;
        array[2] = 3;
        array[3] = 7;
        array[4] = 9;
        array[5] = 1;

        //Ausgabe des Arrays vor dem Sortieren
        for(int i = 0; i < array.length; i++){
            System.out.println("Index "+i+": "+array[i]);
        }

        //Das Array soll sortiert werden, dabei nur die Indexe 3,5,2 berücksichtigen
        array = sortArray(array,3,5,2);

        //Ausgabe des Arrays nach dem Sortieren
        for(int i = 0; i < array.length; i++){
            System.out.println("Index "+i+": "+array[i]);
        }
    }

    public static int[] sortArray(int[] array, int i1, int i2, int i3) throws Exception{
        //Die Länge des Arrays erfragen
        int maxIndex = array.length;

        //Ist ein Index außerhalb des Arrays. Wenn ja: Abbruch
        if(i1 > maxIndex || i2 > maxIndex || i3 > maxIndex){
            throw new Exception("Array out of bounce");
        }


        System.out.println("Sort indexes "+i1+" "+i2+" "+i3);

        //Iteriere das Array durch
        for(int i = 0; i < array.length; i++){
            for(int ii = 0; ii < array.length; ii++){
                //Wird der selbe Index verglichen, Weiter
                if(i == ii){
                    continue;
                }
                //Ist das zu vergleichende Element in der Berücksichtigung
                if((i == i1 || i == i2 || i == i3) && (ii == i1 || ii == i2 || ii == i3)){
                    //Ermittel ob getauscht werden soll
                    if(array[i] < array[ii]){
                        //Tausch des Arrays
                        array = swapArray(array, i, ii);
                    }
                }
            }
        }

        return array;
    }

    //Kleine Hilfsfunktion um ein Array zu tauschen
    public static int[] swapArray(int[] array, int i1, int i2){
        int tmp;
        tmp = array[i1];
        array[i1] = array[i2];
        array[i2] = tmp;
        return array;
    }
}

 

Das Erzeugt die Ausgabe:

Index 0: 4
Index 1: 1
Index 2: 3
Index 3: 7
Index 4: 9
Index 5: 1
Sort indexes 3 5 2
Index 0: 4
Index 1: 1
Index 2: 1
Index 3: 3
Index 4: 9
Index 5: 7

Vielleicht ist das ja ein Ansatz für dich

 

Noch ein paar Anmerkungen zu deinem Ansatz:

1. Nachdem du das erste mal Sortiert hast, kann es sein, dass du nochmal von vorne schauen musst

Wenn

x[1] = 3
x[2] = 9
x[3] = 1

Erster Vergleich:

x[1] > x[2] => Stimmt nicht also kein Tausch

x[1] = 3
x[2] = 9
x[3] = 1

Nächster Vergleich:
x[2] > x[3]  => Stimmt also Tausch

x[1] = 3
x[2] = 1
x[3] = 9

Nächster Vergleich:
x[1] > [x3]  => Stimmt nicht also kein Tausch

x[1] = 3
x[2] = 1
x[3] = 9

 

Du bist hier bereits am ende der Prüfung.
Durch das tauschen ist jetzt aber
x[1] > x[2] => Wahr

 

Diese Problematik umgehe ich im gezeigtem Ansatz. (Such mal nach Selection Sort)

 

2. die Temp variable brauchst du nur einmal, Temp1 ,Temp2, Temp3 brauchst du nicht

 

Bearbeitet 11. November 2021 von Alaric
Typo

[_n4p_]

vor 1 Stunde schrieb Alaric:

//Ist ein Index außerhalb des Arrays. Wenn ja: Abbruch
        if(i1 > maxIndex || i2 > maxIndex || i3 > maxIndex){
            throw new Exception("Array out of bounce");
        }

java wirft schon von sich aus ArrayIndexOutOfBoundsException, warum macht man das selbst?

 

vor 1 Stunde schrieb Alaric:

//Iteriere das Array durch
        for(int i = 0; i < array.length; i++){
            for(int ii = 0; ii < array.length; ii++){

oder man kürzt das ab und sortiert nur die elemente die benötigt werden?

[Alaric]

Stimmt beides!

vor 6 Stunden schrieb _n4p_:

java wirft schon von sich aus ArrayIndexOutOfBoundsException, warum macht man das selbst?

Weil ich darauf hinweisen wollte, dass solche Probleme bei einem Array "unbekannter Länge" entstehen können

 

vor 6 Stunden schrieb _n4p_:

oder man kürzt das ab und sortiert nur die elemente die benötigt werden?

Klar aber da kann der Threadersteller auch selbst optimieren. Er hatte ja Grundsatzprobleme mit dem Ansatz. Auf das Problem wollte ich hier eingehen.

 

[Whiz-zarD]

vor 7 Stunden schrieb _n4p_:

oder man kürzt das ab und sortiert nur die elemente die benötigt werden?

Joa, so hätte ich es auch einfach gemacht. Einfach ein neues Array mit den drei Elementen erzeugen. Dieses Array sortieren und die Elemente wieder entsprechend an ihre Positionen zurückgeschrieben. Einfach das Problem in Teilprobleme zerlegen und sie nach und nach abarbeiten.

vor 15 Minuten schrieb Alaric:

Weil ich darauf hinweisen wollte, dass solche Probleme bei einem Array "unbekannter Länge" entstehen können

Und zudem auch noch falsch, da da der größte Index nicht die Länge vom array ist, sondern Länge - 1. Der Index fängt nämlich bei 0 an...

vor 15 Minuten schrieb Alaric:

Klar aber da kann der Threadersteller auch selbst optimieren. Er hatte ja Grundsatzprobleme mit dem Ansatz. Auf das Problem wollte ich hier eingehen.

Weil wir nun mal kein Forum sind, das die Hausaufgaben macht. Natürlich könnte ich schnell eine Lösung hinrotzen aber davon hat der TE nichts. Ich hab ihn ja ein Hinweis zum Bubblesort-Algorithmus gegeben, den er sich mal anschauen sollte, da ich denke, dass die Aufgabe genau darauf hinaus wollte. Allerdings mit dem Kniff, dass nicht das gesamte Array sortiert werden sollte, sondern nur einzelne Elemente.

Bearbeitet 12. November 2021 von Whiz-zarD

[Alaric]

Öhm, es tut mir wirklich leid wenn ich hier irgendjemanden auf die Füße getreten bin, wollte damit nur helfen. Ich denke da ist alles drin was man für die letztendliche Umsetzung benötigt.

Aber gut, Nachricht angekommen

[Gast r00t]

Ich glaube man sollte keine Lösung mit quadratischer Laufzeit (O(n²)) nutzen für sowas simples was in konstanter Laufzeit gelöst werden kann (O(1)). Gerade wenn es beliebig lang sein kann, dann erwartet man eine Lösung die das berücksichtigt.

 

So kannst du den Kern der Aufgabe in drei Zeilen lösen mit konstanter Laufzeit:

arr[firstIndex] = Math.Min(val1, Math.Min(val2, val3));
arr[secondIndex] = Math.Max(Math.Min(val1, val2), Math.Min(Math.Max(val1, val2), val3));
arr[thridIndex] = Math.Max(val1, Math.Max(val2, val3));

 

Bearbeitet 12. November 2021 von r00t

[Whiz-zarD]

vor einer Stunde schrieb r00t:

Ich glaube man sollte keine Lösung mit quadratischer Laufzeit (O(n²)) nutzen für sowas simples was in konstanter Laufzeit gelöst werden kann (O(1)). Gerade wenn es beliebig lang sein kann, dann erwartet man eine Lösung die das berücksichtigt.

Es sind erstmal nur drei Zahlen. Also nichts, was wirklich lange dauert. Auch bei einer Laufzeit von O(n²). Außerdem berücksichtigt deine Lösung nicht, dass es beliebig viele Zahlen geben kann, die du sortieren musst. Und klar, es gibt weitaus bessere Sortieralgorithmen aber der TE steht am Anfang seines Studiums und da ist oft Bubblesort und andere Sortieralgorithmen ein Thema.

[Gast r00t]

vor 1 Minute schrieb Whiz-zarD:

Es sind erstmal nur drei Zahlen. Also nichts, was wirklich lange dauert. Auch bei einer Laufzeit von O(n²). Außerdem berücksichtigt deine Lösung nicht, dass es beliebig viele Zahlen geben kann, die du sortieren musst. Und klar, es gibt weitaus bessere Sortieralgorithmen aber der TE steht am Anfang seines Studiums und da ist oft Bubblesort und andere Sortieralgorithmen ein Thema.

Lies nochmal die Aufgabe 😉 

Zitat

Mein Aufgabe lautet, dass ich die Werte der Komponenten eines Arrays an drei vorher zufällig gewählten Indizes so vertauschen soll, dass array[i1] ≤ array[i2] und array[i2] ≤ array[i3] gilt.

Du sollst die drei Stellen in dem Array von klein nach groß sortieren, mehr nicht.

[Whiz-zarD]

vor 11 Minuten schrieb r00t:

Du sollst die drei Stellen in dem Array von klein nach groß sortieren, mehr nicht.

Ja und? Weil es nur drei Zahlen sind, soll man sich nicht mit Sortieralgorithmen beschäftigen?

[Gast r00t]

Sorry, ich glaube wir haben aneinander vorbeigeredet – natürlich sollte er sich damit beschäftigen 👍

[Gast r00t]

Kontext: Mein Kommentar war auf den Java? Code bezogen der als Lösung vorgeschlagen wurde und nicht den Vorschlag die Elemente die man braucht auszulesen, mit bubblesort zu sortieren und dann wieder einzufügen. Daher die Verwirrung 

Bearbeitet 12. November 2021 von r00t

[Whiz-zarD]

vor 2 Minuten schrieb r00t:

Mein Kommentar war auf den Java? Code bezogen der als Lösung vorgeschlagen wurde und nicht den Vorschlag die Elemente die man braucht auszulesen, mit bubblesort zu sortieren und dann wieder einzufügen. Daher die Verwirrung 

Ah, okay. Dann hab ich dich missverstanden.

[_n4p_]

vor 18 Stunden schrieb Alaric:

Weil ich darauf hinweisen wollte, dass solche Probleme bei einem Array "unbekannter Länge" entstehen können

auch dann ist es besser die "Standard" Exception korrekt zu behandeln anstatt eine neue unbekannte Exception einzuführen, die
a) einen Schreibfehler (mir sind zumindest keine hüpfenden Arrays bekannt) enthält
b) vom Rest des Codes trotzdem ignoriert wird

Was dabei das Problem ist, wird spätestens klar wenn man sich vorstellt das jemand anderes diese Funktion nutzen möchte und weil es ja um Arrays geht will er die "ArrayIndexOutOfBoundsException" behandeln. Die kommt aber nie. Klar das wird in dem Fall nicht passieren, aber auch schlechter Stil schleift sich ein. Oder wird mitkopiert und "gelernt".

vor 17 Stunden schrieb Alaric:

irgendjemanden auf die Füße getreten bin

darum ging es nicht. Wir geben hier Hilfe zur Selbsthilfe. Selbst erarbeitetes wird besser verinnerlicht und oft reicht ein kleiner Schubs in die richtige Richtung. Durch eine fertige Lösung lernt man in der Regel nicht viel mehr als "Kopieren und Einfügen", da helfen auch keine Kommentare im Code. Kommentare die Code wiederholen statt zu erklären halte ich persönlich auch für suboptimal.