# Elemente in Arrays verschieben



## Sabine.Quast (23. Jun 2020)

Hallo,

ich habe ein Array Typ Klasse.

Klasse [] Array = new Klasse_;

Die Elemente des Arrays sind Attribute einer anderen Klasse.
durch gezieltes löschen wurden manche Elemente dieses Arrays zu Nullstellen.
Jetzt will ich eine Methode Schreiben die das Array so sortiert das alle Nullstellen ganz hinten stehen sollen.
Im Internet finde ich nichts vergleichbares.

Ich bedanke mich im voraus für jeden Hinweis.


Lg, Sabine_


----------



## JennyL (23. Jun 2020)

Meinste das?

```
String[] a = {
				"a",
				null,
				"b",
				null,
				null,
				"c"
			};
		Arrays.sort(a, new Comparator<String>() {
			@Override
			public int compare(String o1, String o2) {
				int i = o1 == null ? 1 : 0 - (o2 == null ? 1 : 0);
				return i;
			}
		});
		System.out.println(Arrays.toString(a));
```


----------



## Sabine.Quast (23. Jun 2020)

JennyL hat gesagt.:


> Meinste das?
> 
> ```
> String[] a = {
> ...




Der Array muss schon typ Klasse sein.
Person[] Mensch = new Person[5].
mit for schleife menschen bilden....
Menschen wurde der Wert Null gegeben.
z.b

Mensch[0] = irgentwas;
Mensch[1] = Null;
Mensch[2] = irgentwas;
Mensch[3] = Null;
Mensch[4] = irgentwas;

daraufhin soll der Array mit einer Methode  sortiert werden das er das wiedergibt:
                                                                                                     Mensch[0] = irgentwas;                                                                                              
                                                                                                     Mensch[2] = irgentwas;                                                     
                                                                                                     Mensch[4] = irgentwas;
                                                                                                     Mensch[1] = Null;
                                                                                                      Mensch[3] = Null;

am besten mit einer for-Schleife wenn möglich.


----------



## JennyL (23. Jun 2020)

Sortieren ist schneller als jedes Element nach hinten verschieben:

```
String[] a = {
				"a",
				null,
				"b",
				null,
				null,
				"c"
			};
		Arrays.sort(a, new Comparator() {
			@Override
			public int compare(Object o1, Object o2) {
				int i = o1 == null ? 1 : 0 - (o2 == null ? 1 : 0);
				return i;
			}
		});
		System.out.println(Arrays.toString(a));
```


----------



## Sabine.Quast (23. Jun 2020)

JennyL hat gesagt.:


> Sortieren ist schneller als jedes Element nach hinten verschieben:
> 
> ```
> String[] a = {
> ...



mein Array ist nicht von Typ String


----------



## LimDul (23. Jun 2020)

Sabine.Quast hat gesagt.:


> mein Array ist nicht von Typ String


Dann transferie die Lösung auf dein Problem und nimm deinen Datentyp.



> Sortieren ist schneller als jedes Element nach hinten verschieben:


Unfug. Sortieren hat eine Laufzeit von O(n log n), die Aufgabenstellung bekommt man auch in O(n) hin, wenn ich jedes Element nur nach hinten schiebe. Laufzeitechnisch ist nach hinten verschieben schneller als sortieren.


----------



## Sabine.Quast (23. Jun 2020)

LimDul hat gesagt.:


> Dann transferie die Lösung auf dein Problem und nimm deinen Datentyp.
> 
> 
> Unfug. Sortieren hat eine Laufzeit von O(n log n), die Aufgabenstellung bekommt man auch in O(n) hin, wenn ich jedes Element nur nach hinten schiebe. Laufzeitechnisch ist nach hinten verschieben schneller als sortieren.




hat erst jetzt geklappt. 
kann man das auch anfängertauglicher machen, sprich mit Schleifen?


----------



## MoxxiManagarm (23. Jun 2020)

Sabine.Quast hat gesagt.:


> kann man das auch anfängertauglicher machen, sprich mit Schleifen?


Ich hätte eine rekursive Variante


```
public static String[] move(String[] array, int x) {
    if (x == array.length) return new String[0];

    String[] result = new String[array.length - x];
    String[] rekursiv = move(array, x + 1);

    int offset = array[x] == null ? 0 : 1;
    result[0] = array[x];

    for (int i = 0; i < rekursiv.length; i++) {
        result[i + offset] = rekursiv[i];
    }

    return result;
}

public static void main(String[] args) {
    String[] array = {null, "1", null, null, "2", "3", "4", "5", null, "6", "7", "8", "9", null, null, "10", null, "11", "12", "13"};

    System.out.println("In: " + Arrays.toString(array));
    array = move(array, 0);
    System.out.println("Out: " + Arrays.toString(array));
}
```

Ausgabe:

```
In: [null, 1, null, null, 2, 3, 4, 5, null, 6, 7, 8, 9, null, null, 10, null, 11, 12, 13]
Out: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, null, null, null, null, null, null, null]
```


----------



## JennyL (23. Jun 2020)

LimDul hat gesagt.:


> Unfug. Sortieren hat eine Laufzeit von O(n log n), die Aufgabenstellung bekommt man auch in O(n) hin, wenn ich jedes Element nur nach hinten schiebe. Laufzeitechnisch ist nach hinten verschieben schneller als sortieren.


Du solltest etwas auf deinen Umgangston achten, ansonsten könnte das für dich schnell unangenehm werden. Jedes Element aufzuschieben hat eine Laufzeit von O(n²). Es gilt weiterhin O(n²)>O(n log(n)).


----------



## MoxxiManagarm (23. Jun 2020)

Und hier noch die einfache iterative Variante, die natürlich am sinnvollsten ist ;-)


```
String[] in = {null, "1", null, null, "2", "3", "4", "5", null, "6", "7", "8", "9", null, null, "10", null, "11", "12", "13"};
String[] out = new String[in.length];

System.out.println("In: " + Arrays.toString(in));

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

System.out.println("Out: " + Arrays.toString(out));
```


----------



## JennyL (23. Jun 2020)

Sabine.Quast hat gesagt.:


> mein Array ist nicht von Typ String


Na und? Ich habe dir bereits eine generalisierte Lösung geschrieben.


----------



## MoxxiManagarm (23. Jun 2020)

JennyL hat gesagt.:


> Du solltest etwas auf deinen Umgangston achten


Ich finde jetzt nicht, dass der sich im Ton vergriffen hat.  🤔


----------



## JennyL (23. Jun 2020)

@MoxxiManagarm Du erstellst ein zusätzliches Array (Speicherplatzverbrauch 2*n), ich weiß nicht ob das die Aufgabenstellung vorsieht.


----------



## MoxxiManagarm (23. Jun 2020)

JennyL hat gesagt.:


> @MoxxiManagarm Du erstellst ein zusätzliches Array (Speicherplatzverbrauch 2*n), ich weiß nicht ob das die Aufgabenstellung vorsieht.


Na dann halt so 🤷‍♀️


```
String[] array = {null, "1", null, null, "2", "3", "4", "5", null, "6", "7", "8", "9", null, null, "10", null, "11", "12", "13"};
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));
```


----------



## LimDul (23. Jun 2020)

JennyL hat gesagt.:


> Du solltest etwas auf deinen Umgangston achten, ansonsten könnte das für dich schnell unangenehm werden. Jedes Element aufzuschieben hat eine Laufzeit von O(n²). Es gilt weiterhin O(n²)>O(n log(n)).


Nö. ich muss nur tauschen, ich muss jedes Element 1x anfassen.


----------



## JennyL (23. Jun 2020)

@MoxxiManagarm 

```
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));
```

@LimDul Die Operation "ein Element nach hinten zu verschieben" erfordert alle Elemente aufzuschieben. Aber ich lasse mich natürlich gerne vom Gegenteil überraschen.


----------



## LimDul (23. Jun 2020)

Verschieben nicht von "ich lasse es wie in einem bubblesort aufsteigen" sondern ich tausche es direkt nach hinten.


----------



## JennyL (23. Jun 2020)

Ja aber du weißt ja nicht, wohin.

Edit: Bzw, du weißt schon wohin, aber du kannst nicht einfach vertauschen, du musst "aufschieben".


----------



## JennyL (23. Jun 2020)

Vielleicht noch ein Beispiel:

```
public static void moveNullToBack(Object[] a) {
		int x = a.length - 1;
		for (int i = 0; i < x; i++) {
			if (a[i] == null) {
				Object o = a[x];
				a[x] = a[i];
				a[i] = o;
			}
		}
	}
```

Das würde funktionieren, wenn wir ausschließen könnten, dass hinten nicht bereits null-Elemente stehen. Da wir das aber nicht ausschließen können, "müssen" wir nach hinten verschieben. Das Verschieben kostet eine weitere innere Schleife, dadurch erhöht sich dann die Komplexität auf n².


----------



## LimDul (23. Jun 2020)

```
public class ArrayTest {

    private static String[] strings = { "a", "b", null, "c", null, null, "d" };

    public static void main(String[] args) {

        int i = 0;
        int j = strings.length - 1;

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

        System.out.println(Arrays.toString(strings));
    }

}
```
Laufzeit O(n).


----------



## thecain (23. Jun 2020)

```
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


----------



## LimDul (23. Jun 2020)

thecain hat gesagt.:


> ```
> public static void main(String[] args) {
> String[] array = { null,  "1", null, "12", "123" };
> int i = 0;
> ...


Zwei Dumme, ein Gedanke


----------



## JennyL (23. Jun 2020)

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.


----------



## kneitzel (23. Jun 2020)

thecain hat gesagt.:


> ```
> 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.


----------



## Sabine.Quast (23. Jun 2020)

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


----------



## JennyL (23. Jun 2020)

Sabine.Quast hat gesagt.:


> Geschmackssache


Nein, mit Geschmack hat das nichts zu tun. Der Code tut etwas was er nicht tun soll ergo ist er "falsch".

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.


----------



## kneitzel (23. Jun 2020)

JennyL hat gesagt.:


> 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.


----------



## kneitzel (23. Jun 2020)

JennyL hat gesagt.:


> 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.


----------



## JennyL (23. Jun 2020)

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...


----------



## kneitzel (23. Jun 2020)

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.


----------



## JennyL (23. Jun 2020)

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?


----------



## kneitzel (23. Jun 2020)

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.


----------



## JennyL (23. Jun 2020)

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`.



JustNobody hat gesagt.:


> 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.



JustNobody hat gesagt.:


> 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...


----------



## kneitzel (23. Jun 2020)

Ist doch einfach umzusetzen. Einfach mal runter geschrieben:

```
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:

```
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...):

```
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));
    }
```


----------



## thecain (23. Jun 2020)

JennyL hat gesagt.:


> 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.


----------



## JennyL (23. Jun 2020)

thecain hat gesagt.:


> 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.


----------



## kneitzel (23. Jun 2020)

JennyL hat gesagt.:


> 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 (24. Jun 2020)

JennyL hat gesagt.:


> @MoxxiManagarm
> 
> ```
> String[] array = { "1", null, null, null, null };
> ...



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.


----------

