Elemente in Arrays verschieben

Diskutiere Elemente in Arrays verschieben im Hausaufgaben Bereich.
T

thecain

Java:
public static void main(String[] args) {
    String[] array = { null,  "1", null, "12", "123" };
    int i = 0;
    int j = array.length-1;

    while (i < j) {
        if(array[j] == null) {
            j--;
        }
        else if(array[i] == null && array[j] != null) {
            array[i]= array[j];
            array[j] = null;
            i++;
            j--;
        }
        else {
            i++;
        }

    }
    System.out.println(Arrays.toString(array));
}
Nicht ausgiebig getestet
 
L

LimDul

Java:
public static void main(String[] args) {
    String[] array = { null,  "1", null, "12", "123" };
    int i = 0;
    int j = array.length-1;

    while (i < j) {
        if(array[j] == null) {
            j--;
        }
        else if(array[i] == null && array[j] != null) {
            array[i]= array[j];
            array[j] = null;
            i++;
            j--;
        }
        else {
            i++;
        }

    }
    System.out.println(Arrays.toString(array));
}
Nicht ausgiebig getestet
Zwei Dumme, ein Gedanke :D
 
J

JennyL

Ich denke, das funktioniert. Ist aber nicht mehr stabil, die Reihenfolge nicht null-Elementen könnte verändert werden. Aber weiß nicht, ob das zu den Anforderungen zählt... Vielleicht soll einfach nur ein spezielles BubbleSort geschrieben werden.
 
J

JustNobody

Java:
        if(array[j] == null) {
        } else if(array[i] == null && array[j] != null) {
        } else {
        }
Im stark gekürzten Code sieht man:
Im else if muss man nicht erneut array[j] != null prüfen, denn wäre das Element null, dann wäre ja schon das erste if ausgeführt worden.
 
S

Sabine.Quast

Danke an alle für die Hilfe.
Hab alle getestet und mich am ende für thecain's Lösung mit der Ergänzung von JustNobody entschieden.
Der Code sieht schön aus und ist am leichtesten zu verstehen(Geschmackssache).

Lg, Sabine
 
J

JustNobody

Ich denke, das funktioniert. Ist aber nicht mehr stabil, die Reihenfolge nicht null-Elementen könnte verändert werden. Aber weiß nicht, ob das zu den Anforderungen zählt... Vielleicht soll einfach nur ein spezielles BubbleSort geschrieben werden.
Was mir da gerade auffällt: wenn die Reihenfolge der nicht null Elemente gleich bleiben soll, dann ist die Idee mit dem sortieren natürlich Unsinn.

Aber man kann mit O(n) natürlich auch durchgehen und die Elemente umkopieren.
Man braucht zwei Indices. Ein Lese Index und ein Schreibindex.
Erste Phase: beide Indeces werden hochgehalten, bis man zur ersten null kommt.
Zweite Phase: Der LeseIndex geht dann weiter bis zu einem non null Element um dann das Element zu kopieren und lese Index Inhalt auf null zu setzen (beide Indeces gehen dann eins weiter).

Dann ist man auch mit einmal durchgehen fertig und muss nur eben sehr viel mehr kopieren.
 
J

JustNobody

Im Übrigen ist objektiv gesehen mein Code am "schönsten" und am leichtesten zu verstehen. Ich gebe dir 5 Jahre Zeit, dann siehst du das auch so. ;)
Dazu muss man nicht mehr sagen außer: Du meinst, es dauert 5 Jahre bis man das versteht? Wie lange dauert es noch bei Dir, bis deine 5 Jahre rum sind?

Etwas ist falsch, wenn die Anforderungen nicht erfüllt sind. Die Reihenfolge bei zu behalten war keine Anforderung. Ebenso war das Sortieren keine Anforderung. Also schön und gut ist etwas anderes.
 
J

JennyL

Ich kann gerade in Beitrag #27 und #28 von Nobody nichts sehen, was entweder nicht falsch wäre oder schlicht nicht unsinnig wäre...

Nochmal, sie weiß noch nicht einmal was sie haben will und dann wirfst du mir Unerfahrenheit vor? ... Mir fehlen gerade Worte...

Aber dann mal andersherum, nimm den Code von Cain, er löst all deine Probleme...
 
J

JustNobody

Wenn Du Deine Meinung nur etwas belegen würdest. Aber nein - keine Angst: Das erwarten wir nicht von Dir...

Und so unsinnig ist mein Algorithmus nicht, denn Du hast ihn selbst in #16 ins Forum geklatscht. Nur eben nicht in die zwei Phasen aufgeteilt, weshalb Du da am Anfang Elemente sich selbst zuweist.


Wenn Du nur etwas mehr begründen würdest und nicht nur stumpfsinnig Code ins Forum klatschen würdest ... aber nein: Auch das erwarten wir nicht von Dir. Wir kennen Dich und Du hast noch nie irgendwas begründet.... Aber Du machst einem ja Hoffnungen: Wenn nach 5 Jahren Leute anfangen zu verstehen, dann haben wir ja vielleicht in ein paar Jahren das Glück, das Du auch das eine oder andere verstanden hast.
 
J

JennyL

Beitrag #19 ist eine Begründung, warum ein "einfaches Swappen" nicht funktioniert, wenn es dem Array nicht "Gemüse" werden soll...

Dass das keine mathematische Herleitung ist, ist mir klar, aber danach war hoffentlich nicht gefragt.

@Sabine.Quast Wofür brauchst du das eigentlich? Hausaufgabe, Übungsaufgabe, eigene Anwendung oder professionelle Softwareentwicklung?
 
J

JustNobody

Also wenn du wie in #19 vorgehen wolltest, dann könntest du hinten anfangen nach einem non null Element zu suchen.

Dann würdest du mit zwei Indeces von Vorne (suche nach null) und Hinten (suche nach non null) heran gehen. Aber irgendwann treffen sich die Indeces und du bist fertig - also jedes Element einmal angepackt / geprüft / ggf getauscht.

Aber du hast on #16 ja selbst eine Routine geschrieben, die von Anfang an durch geht und umkopiert. Wobei das null setzen nur erfolgen darf, wenn i und j unterschiedlich waren ... ansonsten ist das Element futsch oder habe ich da jetzt etwas übersehen? Der Algorithmus ist aber problemlos entsprechend möglich.

Und die Anforderung ist übrigens eindeutig: es ist von einem sortieren die Rede, d.h. die Reihenfolge ist danach anders. Und die Anforderung wie sortiert sein soll? Null nach hinten ... Rest ist nicht definiert ...
So wäre meine Interpretation der Aussage in #1.
 
J

JennyL

Es ist, für mich jedenfalls, nicht immer ganz leicht, für ein bestehendes Problem die Optimalität eines Algorithmus zu zeigen/zu beweisen. Oftmals ist das bei mir nur ein Bauchgefühl.

Man kann sich ja mal das ansehen: https://de.wikipedia.org/wiki/Sortierverfahren#Beweis_der_unteren_Schranke_f%C3%BCr_vergleichsbasiertes_Sortieren.

Dann würdest du mit zwei Indeces von Vorne (suche nach null) und Hinten (suche nach non null) heran gehen. Aber irgendwann treffen sich die Indeces und du bist fertig - also jedes Element einmal angepackt / geprüft / ggf getauscht.
Das könnte, in O(n), funktionieren - ich weiß das aber nicht genau. Eine Implementierung würde helfen.

Und die Anforderung ist übrigens eindeutig: es ist von einem sortieren die Rede, d.h. die Reihenfolge ist danach anders. Und die Anforderung wie sortiert sein soll? Null nach hinten ... Rest ist nicht definiert ...
Können uns ewig streiten, was bei "nicht definiert" angenommen werden sollte. Ich weiß es nicht...
 
J

JustNobody

Ist doch einfach umzusetzen. Einfach mal runter geschrieben:
Java:
    public static void moveNullElementsToEnd(Object[] array) {
        int vordererIndex = 0;
        int hintererIndex = array.length - 1;

        while (vordererIndex < hintererIndex) {
            // Get first null element
            while (vordererIndex < hintererIndex && array[vordererIndex] != null)
                vordererIndex++;

            // get last non null element
            while (hintererIndex > vordererIndex && array[hintererIndex] == null)
                hintererIndex--;

            // Switch if required, we know null element so no need to store it!
            if (vordererIndex < hintererIndex) {
                array[vordererIndex] = array[hintererIndex];
                array[hintererIndex] = null;
            }
        }
    }
Die Variante, wie ich sie beschrieben habe in #27 und die in etwa dem entspricht, das Du in #16 geschrieben hast:
Java:
    public static int findFirstNullElement(Object[] array) {
        int result = 0;
        while (result < array.length && array[result] != null)
            result++;

        if (result == array.length) return -1; // No null element found.

        return result;
    }

    public static void compactArray(Object[] array) {
        int vordererIndex = findFirstNullElement(array);

        if (vordererIndex == -1) return; // No null element.

        for (int index = vordererIndex+1; index < array.length; index++) {
            if (array[index] != null) {
                array[vordererIndex] = array[index];
                array[index] = null;
                vordererIndex++;
            }
        }
    }
Oder Deinen Code nur etwas korrigiert (Variablen habe ich mal nicht umbenannt...):
Java:
    public static void main(String[] args) {
        String[] array = { "1", null, null, "2", null };
        System.out.println("In: " + Arrays.toString(array));

        int j = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] != null) {
                if (i != j) {
                    array[j] = array[i];
                    array[i] = null;
                }
                j++;
            }
        }

        System.out.println("Out: " + Arrays.toString(array));
    }
 
T

thecain

Der Code tut etwas was er nicht tun soll ergo ist er "falsch".
inwiefern? null steht hinten. Das die Reihenfolge vom Rest irgendwie relevant ist hast du dazugedichtet.
Aber zuzugeben einmal falsch zu liegen tut gar nicht so weh, Tobias. Ich gebe dir 5 Jahre Zeit, dann siehst du das auch.
 
J

JennyL

Das die Reihenfolge vom Rest irgendwie relevant ist hast du dazugedichtet.
Kannst du auch etwas anderes als billige Unterstellungen von dir geben? Wahrscheinlich nicht...

Edit: Wenn von sortieren die Rede ist, erwarte ich keine gemischte Liste. Punkt.
 
Zuletzt bearbeitet:
J

JustNobody

Edit: Wenn von sortieren die Rede ist, erwarte ich keine gemischte Liste. Punkt.
Sortieren heisst nur, dass eine bestimmte Sortierung gewünscht ist. Hier ist nur nicht null vor null gefordert.

Aber das ist unter dem Strich wie eine Sortierung, bei dem nur ein Merkmal genommen werden soll. Also z.B. sortieren nur nach Nachnamen. Dann ist nicht vorgegeben, in welcher Reihenfolge z.B. 20 Müller sein sollen...

Wenn es da aber keine Vorgabe gibt, dann ist jede Reihenfolge ok.

Also ganz klar die Abnahmekriterien ableiten. Und was nicht angegeben wurde, ist kein Abnahmekriterium. Und jegliche Berücksichtigung von Dingen, die man meint ist eine unnötige Verkomplizierung und damit ein Verstoß gegen KISS.
 
MoxxiManagarm

MoxxiManagarm

@MoxxiManagarm
Java:
String[] array = { "1", null, null, null, null };
System.out.println("In: " + Arrays.toString(array));

int j = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] != null) {
array[j++] = array[i];
array[i] = null;
}
}

System.out.println("Out: " + Arrays.toString(array));
Ey jupp, das habe ich nicht bedacht nachdem ich von in-out (#6) auf array (#14) umgestellt habe. Danke für den Hinweis, gut gesehen. Aber lässt sich doch noch einfach beheben.
 
Thema: 

Elemente in Arrays verschieben

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben