Elemente in Arrays verschieben

Sabine.Quast

Mitglied
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

Bekanntes Mitglied
Meinste das?
Java:
		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

Mitglied
Meinste das?
Java:
        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));


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

Bekanntes Mitglied
Sortieren ist schneller als jedes Element nach hinten verschieben:
Java:
		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

Mitglied
Sortieren ist schneller als jedes Element nach hinten verschieben:
Java:
        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));

mein Array ist nicht von Typ String
 

LimDul

Top Contributor
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

Mitglied
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

Top Contributor
kann man das auch anfängertauglicher machen, sprich mit Schleifen?
Ich hätte eine rekursive Variante

Java:
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:
Code:
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

Bekanntes Mitglied
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

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

Java:
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));
 

MoxxiManagarm

Top Contributor
@MoxxiManagarm Du erstellst ein zusätzliches Array (Speicherplatzverbrauch 2*n), ich weiß nicht ob das die Aufgabenstellung vorsieht.
Na dann halt so 🤷‍♀️

Java:
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));
 

JennyL

Bekanntes Mitglied
@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));

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

JennyL

Bekanntes Mitglied
Ja aber du weißt ja nicht, wohin.

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

JennyL

Bekanntes Mitglied
Vielleicht noch ein Beispiel:
Java:
	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

Top Contributor
Java:
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

Top Contributor
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
 

LimDul

Top Contributor
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
 

JennyL

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

Sabine.Quast

Mitglied
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
 
K

kneitzel

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

kneitzel

Gast
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

Bekanntes Mitglied
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...
 
K

kneitzel

Gast
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

Bekanntes Mitglied
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?
 
K

kneitzel

Gast
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

Bekanntes Mitglied
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...
 
K

kneitzel

Gast
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));
    }
 
K

kneitzel

Gast
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

Top Contributor
@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.
 

Neue Themen


Oben