Liste sortieren ohne Array und ohne vorgegebene Sortierung

[Fynn29]

Hallo,

kann mir jemand sagen, wie ich eine Liste (keinen Array) in eine aufsteigende Reihenfolge sortieren kann, ohne den von Java mitgelieferten Sortieralgorithmus zu verwenden?

 

[Jw456]

selber schreiben zb Bubbelsort

Bubblesort: Beispiel, Algorithmus, Laufzeit, Java & C

Einfache Bubblesort Erklärung! Vom Beispiel bis Algorithmus mit zugehörigem Pseudocode & Struktogramm ✅ Java- und C-Implementierung ✅ mit kostenlosem Video

studyflix.de

Sortieralgorithmen mit Arrays und Listen in Java: Insertion Sort, Selection Sort und Bubble Sort - Bloggingwelt

In diesem Beitrag zeige ich dir die wohl drei gängigsten Sortieralgorithmen, erkläre sie kurz und stelle den Quellcode zur Verfügung.

bloggingwelt.de

 

[KonradN]

Wo ist denn das genaue Problem? Woran scheiterst Du?

Die Frage ist erst einmal, was Du für eine Liste hast. Wenn es eine List von Java meint, dann hast Du ähnliche Zugriffsmöglichkeiten wie bei einem Array über die set / get Methoden.

Wenn Du eine eigene Liste sortieren musst, dann wäre die Frage, was Du da an Zugriffsmöglichkeiten hast. Und dann kannst Du die Sortieralgorithmen durchgehen, die Du anwenden kannst. Und bei einer einfach verlinkten Liste ist tatsächlich ein Sortierverfahren wie Bubblesort eine nicht schlechte Idee.

 

[Fynn29]

Wo ist denn das genaue Problem? Woran scheiterst Du?

Die Frage ist erst einmal, was Du für eine Liste hast. Wenn es eine List von Java meint, dann hast Du ähnliche Zugriffsmöglichkeiten wie bei einem Array über die set / get Methoden.

Wenn Du eine eigene Liste sortieren musst, dann wäre die Frage, was Du da an Zugriffsmöglichkeiten hast. Und dann kannst Du die Sortieralgorithmen durchgehen, die Du anwenden kannst. Und bei einer einfach verlinkten Liste ist tatsächlich ein Sortierverfahren wie Bubblesort eine nicht schlechte Idee.

Es ist eine Liste von Java. Das ganze ist nur kompliziert, weil man dort ja nicht einfach an jede beliebige Stelle wie bei einem Array greifen kann, sondern immer nur den Current hat. Die Liste soll dann mit Hilfe von Bubblesort sortiert werden.

 

[Oneixee5]

Man kann selbstverständlich bei einer Klasse die von java.util.List abgeleitet ist auf jedes Element gezielt zugreifen und auch die Position in der Liste verändern.

List (Java Platform SE 8 )

 

[KonradN]

Es ist eine Liste von Java. Das ganze ist nur kompliziert, weil man dort ja nicht einfach an jede beliebige Stelle wie bei einem Array greifen kann, sondern immer nur den Current hat. Die Liste soll dann mit Hilfe von Bubblesort sortiert werden.

Also wenn es eine Liste von Java ist, also java.util.List implementiert wurde, dann hast Du auch den Zugriff über den Index.

Aber wenn Du eine einfach verlinkte Liste hast (Edit: Du also nur meintest "Eine Liste, die von euch in Java implementiert wurde), dann spiel doch einfach einmal durch, was für Zugriffe du brauchst. Dazu kannst Du Dir die Elemente wie kleine Kisten vorstellen. Und Du kannst Dir kleine Marker setzen.

Also Du hast z.B. Streichholzschachteln (das Innenteil) und du hast Wäscheklammern. Zugriffe hast Du nur:

• Auf Streichholzschachteln, die eine Wäscheklammer haben
• Wenn Du auf einem Streichholzschachtelchen bist, dann hast Du Zugriff auf das nächste Streichholzschächtelchen

Ist das etwas, das Du Dir bildlich vorstellen kannst?

Dann ist der Aufbau:

• Du hast Streichholzschächtelchen in einer Reihe liegen und in jeder Schachtel ist ein kleiner Zettel mit einer Zahl.
• An der ersten Streichholzschachtel ist eine Wäscheklammer "Anfang".

Nun kannst Du da durch gehen. Um also alle Zahlen in der Liste auszugeben, wäre dies ein Ablauf wie:
1) Wäscheklammer "current" auf die Schachtel mit Wäscheklammer "Anfang" setzen.
2) So lange Current auf einer Streichholzschachtel ist:
2.1) Lies die Zahl vom Zettel der Streichholzschachtel von "current" vor
2.2) Setze die Wäscheklammer "current" auf die nächste Streichholzschachtel

Und so kannst Du das auch durchspielen. Du musst nur schauen, was da bei Bubblesort genau gemacht wird. Und dann hast Du z.B. Dinge wie
"Vergleiche den Inhalt der Streichholzschachtel von Wäscheklammer "current" mit der Schachtel dahinter und tausche ggf. den Inhalt."

 

[HerrInfo]

Es ist eine Liste von Java. Das ganze ist nur kompliziert, weil man dort ja nicht einfach an jede beliebige Stelle wie bei einem Array greifen kann, sondern immer nur den Current hat. Die Liste soll dann mit Hilfe von Bubblesort sortiert werden.

Angenommen, du musst die Liste verwenden, die vom Bundesministerium vorgeschrieben ist. In dieser Liste werden hauptsächlich die Methoden

toFirst()

,

hasAccess()

und

getContent()

verwendet. Wenn wir uns nun den Pseudocode für Bubble Sort anschauen:

bubbleSort(Array A)
  for (n = A.size; n > 1; n = n - 1) { // äußere Schleife
    for (i = 0; i < n - 1; i = i + 1) { // innere Schleife
      if (A[i] > A[i + 1]) {
        A.swap(i, i + 1)
      }
    }
  }

(kommt von Wikipedia: https://de.wikipedia.org/wiki/Bubblesort)

kann man ihn mit den genannten Methoden umsetzen. Das sieht dann grob so aus:

List<Integer> sortedList = new List<Integer>();
int pointer;

listToSort.toFirst();
while (listToSort.hasAccess()) {
    pointer = listToSort.getContent();
    sortedList.toFirst();
    while (sortedList.hasAccess()) {
        if (pointer < sortedList.getContent()) {
            sortedList.insert(pointer);
            break;
        }
        sortedList.next();
    }
    if (!sortedList.hasAccess()) {
        sortedList.append(pointer);
    }
    listToSort.next();
}

Nun ist die Liste sortiert und in der neuen Liste gespeichert.

 

[Fynn29]

Angenommen, du musst die Liste verwenden, die vom Bundesministerium vorgeschrieben ist. In dieser Liste werden hauptsächlich die Methoden

toFirst()

,

hasAccess()

und

getContent()

verwendet. Wenn wir uns nun den Pseudocode für Bubble Sort anschauen:

bubbleSort(Array A)
  for (n = A.size; n > 1; n = n - 1) { // äußere Schleife
    for (i = 0; i < n - 1; i = i + 1) { // innere Schleife
      if (A[i] > A[i + 1]) {
        A.swap(i, i + 1)
      }
    }
  }

(kommt von Wikipedia: https://de.wikipedia.org/wiki/Bubblesort)

kann man ihn mit den genannten Methoden umsetzen. Das sieht dann grob so aus:

List<Integer> sortedList = new List<Integer>();
int pointer;

listToSort.toFirst();
while (listToSort.hasAccess()) {
    pointer = listToSort.getContent();
    sortedList.toFirst();
    while (sortedList.hasAccess()) {
        if (pointer < sortedList.getContent()) {
            sortedList.insert(pointer);
            break;
        }
        sortedList.next();
    }
    if (!sortedList.hasAccess()) {
        sortedList.append(pointer);
    }
    listToSort.next();
}

Nun ist die Liste sortiert und in der neuen Liste gespeichert.

Das ganze müsste in der unsortierten Liste ohne eine neue Liste funktionieren.

 

[KonradN]

Sorry, aber was hast Du Dir denn bisher an weiteren Gedanken gemacht? Du hast einige Antworten bekommen, die Dir weiter helfen sollten. Wenn nicht wäre wichtig, dass Du schreibst, wo es hakt.

Ziel sollte sein, dass Du lernst, so Aufgaben selbst zu lösen…

 

[Fynn29]

Sorry, aber was hast Du Dir denn bisher an weiteren Gedanken gemacht? Du hast einige Antworten bekommen, die Dir weiter helfen sollten. Wenn nicht wäre wichtig, dass Du schreibst, wo es hakt.

Ziel sollte sein, dass Du lernst, so Aufgaben selbst zu lösen…

Ich probiere die ganze Zeit verschiedene Möglichkeiten an Code, komme aber gar nicht weiter.

 

[KonradN]

Wenn Du uns Details nennst, dann hast Du eine Chance, dass wir Dir weiter helfen. Ohne diese wird es aber sehr schwer.

Und hast Du Dir denn schon ein generelles Vorgehen überlegt? Das ist IMMER der erste Schritt. Ohne ein Verständnis des Problems und der Lösung wäre es ein absoluter Zufall, einen funktionierenden Code zu erstellen.

 

[Fynn29]

Wenn Du uns Details nennst, dann hast Du eine Chance, dass wir Dir weiter helfen. Ohne diese wird es aber sehr schwer.

Und hast Du Dir denn schon ein generelles Vorgehen überlegt? Das ist IMMER der erste Schritt. Ohne ein Verständnis des Problems und der Lösung wäre es ein absoluter Zufall, einen funktionierenden Code zu erstellen.

Ich habe schon einen Code, der einen Array sortiert. Das war auch nicht so schwer. Ich tue mich jedoch schwer dabei, mit Currents in Listen zu arbeiten, weil ich dort ja nicht wie bei einem Array einfach in einer For-Schleife mit der aktuellen Zahl aus der For-Schleife auf eine beliebige Stelle im Array zugreifen kann. Den Current kann ich ja immer nur um eins nach hinten schieben.

 

[KonradN]

Also kommen wir erst einmal zu einer früheren Frage zurück: Was genau für eine Liste hast Du? Es ist nach Deinen aktuellen Aussagen nicht die java.util.List von Java sondern ganz offensichtlich eine einfache linked list.

Da wäre dann die Frage: Was für Zugriffe hast Du auf die Liste? Oder hast Du alle Zugriffe und kannst komplett auf alles zugreifen weil die Methode Bestandteil der List wird?

Aber fangen wir einfach an und überlegen diverse Szenarien:

• Leere Liste -> Kannst Du den Fall abhandeln?
• Liste mit einem Element -> Kannst Du den Fall abhandeln?
• Liste mit 2 Elementen -> Kannst Du den Fall abhandeln?
• Liste mit 3 Elementen -> Wie sieht es da jetzt aus? Kannst Du evtl. das, was Du mit 2 Elementen gemacht hast, hier anwenden?

Das wäre eine Schritt für Schritt Herangehensweise. Und stell es Dir bildlich vor! Ich habe versucht, Dir da ein Szenario aufzumalen mit Streichholzschachteln und Wäscheklammern.

Aber Du kannst es Dir auch wie ein Zug vorstellen. Du hast eine Lok mit Anhängern. Lok und Anhänger sind alle Verbunden, aber die Tür zwischen Lok und Anhänger oder zwischen zwei Anhängern lässt sich nur von der Lok Seite aus öffnen.
Du stehst am Bahnsteig und kannst Leute in den Zug schicken. Du hast aber nur eine begrenzte Anzahl an Leuten und Du musst halt sagen, wie viele Du brauchst. Eine Person gibt es und das ist der Lokführer.
Vom Bahnsteig aus kannst Du in den Zug, aber die Tür muss von außen geöffnet werden.
Damit Du etwas mit dem Inhalt des Anhängers machen kannst, muss eine Person in dem Anhänger sein.

Nun kannst Du damit Dinge machen. Du willst also z.B. die Anzahl der Anhänger zählen. Dazu schickst Du eine Person in den Zug. Und die Person geht dann von der Lok (dem Kopf der Liste) von Anhänger zu Anhänger und immer wenn er in einen Anhänger geht, zählt er einen Zähler hoch.
==> Das ist dann vermutlich ein Ablauf, den Du kennst um die Anzahl der Elemente zu zählen.


Und nun kannst Du schauen, ob Du mit so einem Szenario etwas machen kannst, um dann einen Lösungsweg zu finden. Den Lösungsweg kann man dann einfach in Code umsetzen. Personen sind dann Variablen, die Lok ist der Kopf der Liste (So es den gibt, ggf. ist da auch einfach ein erster Anhänger) und die Anhänger sind die Knoten der Liste.

 

[Fynn29]

Also kommen wir erst einmal zu einer früheren Frage zurück: Was genau für eine Liste hast Du? Es ist nach Deinen aktuellen Aussagen nicht die java.util.List von Java sondern ganz offensichtlich eine einfache linked list.

Da wäre dann die Frage: Was für Zugriffe hast Du auf die Liste? Oder hast Du alle Zugriffe und kannst komplett auf alles zugreifen weil die Methode Bestandteil der List wird?

Aber fangen wir einfach an und überlegen diverse Szenarien:

• Leere Liste -> Kannst Du den Fall abhandeln?
• Liste mit einem Element -> Kannst Du den Fall abhandeln?
• Liste mit 2 Elementen -> Kannst Du den Fall abhandeln?
• Liste mit 3 Elementen -> Wie sieht es da jetzt aus? Kannst Du evtl. das, was Du mit 2 Elementen gemacht hast, hier anwenden?

Das wäre eine Schritt für Schritt Herangehensweise. Und stell es Dir bildlich vor! Ich habe versucht, Dir da ein Szenario aufzumalen mit Streichholzschachteln und Wäscheklammern.

Aber Du kannst es Dir auch wie ein Zug vorstellen. Du hast eine Lok mit Anhängern. Lok und Anhänger sind alle Verbunden, aber die Tür zwischen Lok und Anhänger oder zwischen zwei Anhängern lässt sich nur von der Lok Seite aus öffnen.
Du stehst am Bahnsteig und kannst Leute in den Zug schicken. Du hast aber nur eine begrenzte Anzahl an Leuten und Du musst halt sagen, wie viele Du brauchst. Eine Person gibt es und das ist der Lokführer.
Vom Bahnsteig aus kannst Du in den Zug, aber die Tür muss von außen geöffnet werden.
Damit Du etwas mit dem Inhalt des Anhängers machen kannst, muss eine Person in dem Anhänger sein.

Nun kannst Du damit Dinge machen. Du willst also z.B. die Anzahl der Anhänger zählen. Dazu schickst Du eine Person in den Zug. Und die Person geht dann von der Lok (dem Kopf der Liste) von Anhänger zu Anhänger und immer wenn er in einen Anhänger geht, zählt er einen Zähler hoch.
==> Das ist dann vermutlich ein Ablauf, den Du kennst um die Anzahl der Elemente zu zählen.


Und nun kannst Du schauen, ob Du mit so einem Szenario etwas machen kannst, um dann einen Lösungsweg zu finden. Den Lösungsweg kann man dann einfach in Code umsetzen. Personen sind dann Variablen, die Lok ist der Kopf der Liste (So es den gibt, ggf. ist da auch einfach ein erster Anhänger) und die Anhänger sind die Knoten der Liste.

Ist die Liste, die "HerrInfo" oben angemerkt hat. Danke erstmal. Ich schaue, ob ich damit etwas anfangen kann.

 

[KonradN]

Ist die Liste, die "HerrInfo" oben angemerkt hat. Danke erstmal. Ich schaue, ob ich damit etwas anfangen kann.

Die kenne ich nicht. Kannst Du bitte die genauen Details teilen?

 

[Jw456]

Zeige doch mal was von den Code was du bis jetzt hast.
Da können wir sicherlich sehen was das für eine Liste ist.

 

[Jw456]

ist es etwas diese art von Liste

https://cpothmann.de/wp-content/uploads/2021/07/AB-Liste-Methoden.pdf

 

[KonradN]

@Jw456 Danke für den Link / die Beschreibung.

Die Liste bietet natürlich sehr wenig Zugriffsmöglichkeiten, aber mir fällt da direkt ein anderes Szenario ein, das Bildlich sehr gut ist:

Du hast ein Kartenspiel. Du hast also eine ganze Menge an Karten auf einem Stapel. Und Du kannst den Kartenstapel immer nur von Anfang an durchgehen. Also Du hast einen Stapel Karten und Du siehst nur die oberste Karte. Und du kannst zur nächsten Karte kommen, in dem Du sozusagen die oberste Karte umdrehst und auf einen anderen Stapel legst.

Was Du machen kannst sind daher die Operationen:
a) hasAccess -> Ist noch eine Karte sichtbar?
b) toFirst -> Alle Karten, die umgedreht wurden, werden wieder auf den Stapel gelegt und du siehst die erste Karte.
c) insert -> Es wird eine Karte oben auf die sichtbare Karte gelegt.
d) remove -> Die sichtbare Karte wird weggenommen.

Kannst Du prüfen, ob die Karten sortiert sind? Das sollte ja möglich sein, oder? Du merkst Dir halt, was auf der sichtbaren Karte ist und drehst diese dann um auf den anderen Stapel. Und damit siehst Du ja die nächste Karte oder siehst, dass Du am Ende bist.

Wenn Du das geschafft hast:
Wenn Du ein sortiertes Kartenspiel hast: Kannst Du da eine Karte einfügen (so dass danach das Kartenspiel auch noch sortiert ist?

Dann wäre der letzte Schritt, beides aneinander hängen ... Du prüfst das Kartenspiel bis Du zu einer Karte kommst, die nicht richtig einsortiert ist. Dann machst Du etwas um dann das zu machen, was Du als zweite Teilaufgabe gemacht hast.
Damit bist Du aber noch nicht fertig, denn nach dem Einfügen musst Du wieder mit was anderem weiter machen ...
Kannst Du Dir das evtl. jetzt überlegen?

 

[Jw456]

Und dass würde dann meinen ersten Post Link 2 entsprechen.

 

[Fynn29]

Zeige doch mal was von den Code was du bis jetzt hast.
Da können wir sicherlich sehen was das für eine Liste ist.

Das ist mein aktueller Code. Ich bekomme jedoch eine NullPointerException in der Zeile bei der If-Abfrage. Ich weiß jedoch nicht, wie ich das beheben kann. Ist ja die einzige Möglichkeit, die ich überhaupt habe.

 

[Fynn29]

public void sort() {
        myList.toFirst();
        
        while(myList.hasAccess()) {
            x = myList.getContent();
            myList.next();
            if(x > myList.getContent()) {
                y = myList.getContent();
                myList.insert(y);
                myList.insert(x);
                myList.remove();
            }
        }
    }

Hier das ganze auch noch als Java Code.

 

[Jw456]

Schaue dir mal den Code von meinen ersten Post link 2 an.

Da wird eine Liste übergeben und eine sortierte Liste in der Methode zurückgegeben.
Die sortiertere ist dann nicht direkt die gleiche wie die übergebene Liste .
Es wird in der Methode eine Neue Liste erstellt und in ihr werden die Elemente in sortierter Reihenfolge eingefügt. Und die wird zurückgegeben.

Das macht auch HerrInfo

code aus dem link https://bloggingwelt.de/sortieralgo...nsertion-sort-selection-sort-und-bubble-sort/

public List<Integer> bubbleSort(List<Integer> l) {
    int temp1, temp2;
    boolean changed = false;
    do {
        l.toFirst();
        temp1 = l.getContent();
        l.next();
        while(temp1 > l.getContent() && l.hasAccess()) {
            temp2 = l.getContent();
            l.remove();
            l.insert(temp2);
            l.insert(temp1);
            changed = true;
        }
    } while(l.hasAccess() && changed == true)
    return l;
}

 

[Fynn29]

Schaue dir mal den Code von meinen ersten Post link 2 an.

Da wird eine Liste übergeben und eine sortierte Liste in der Methode zurückgegeben.
Die sortiertere ist dann nicht direkt die gleiche wie die übergebene Liste .
Es wird in der Methode eine Neue Liste erstellt und in ihr werden die Elemente in sortierter Reihenfolge eingefügt. Und die wird zurückgegeben.

Das macht auch HerrInfo

code aus dem link https://bloggingwelt.de/sortieralgo...nsertion-sort-selection-sort-und-bubble-sort/

public List<Integer> bubbleSort(List<Integer> l) {
    int temp1, temp2;
    boolean changed = false;
    do {
        l.toFirst();
        temp1 = l.getContent();
        l.next();
        while(temp1 > l.getContent() && l.hasAccess()) {
            temp2 = l.getContent();
            l.remove();
            l.insert(temp2);
            l.insert(temp1);
            changed = true;
        }
    } while(l.hasAccess() && changed == true)
    return l;
}

Der Code aus dem Link hier wird mir aber leider nicht wirklich helfen, weil hier das Tauschen ja nur einmal durchgeführt werden kann, weil danach nicht mehr auf die nächste Zahl in der Liste gewechselt wird.

 

[Jw456]

Ja das prüfen auf changed == True ist von dem Autor nicht so sinnvoll.
Kannst du ja ändern
Habe den Code nicht überprüft.

Ging hier mehr darum das du zwei Listen hast.
Das kleinste suchst und das dann erstens in die neue Liste speicherst und aus der alten liste entfernst.

 

[KonradN]

Also ich stehe gerade auf dem Schlauch: Es ist offensichtlich nicht erwünscht, sich einen Algorithmus selbst zu erarbeiten. Dabei hatte ich ein etwas schlechtes Gewissen, weil ich in #18 den Algorithmus aus meiner Sicht schon zu genau beschrieben hatte ...

@Fynn29: Darf ich fragen, wieso Du dies ablehnst und Du auch auf keinen Versuch eingehst, Dir das visuell vorzustellen? Nicht falsch verstehen: Es ist super, wenn Du Algorithmen auch ohne so eine visuelle Vorstellung schreiben kannst.... Aber mich irritiert das gerade einfach etwas ...

Aber der Algorithmus kann relativ einfach aufgebaut werden - wie schon beschrieben in paar einfachen Schritten:

• Man geht an den Anfang (Wer weiss, wo current gerade steht ...)
• Das Sortieren geht die Liste durch und sucht nach einem Wert, der an falscher Stelle ist
• Wird kein solcher Wert gefunden, dann ist man fertig (hasAccess ist falsch).
• Dann wird der entfernte Werte eingefügt in den sortierten Bereich.
• Dann kann man wieder von Anfang an loslegen. (Dabei kann man einfach bei dem zuletzt eingefügten Element weiter suchen)

Suchen nach einem falschen Wert ist einfach:

• Du merkst Dir den aktuellen Wert.
• So lange es einen Wert gibt und der gemerkte Wert <= dem Content ist, merkst Du Dir den Inhalt und gehst weiter.

Insert wrong Value ist einfach:

• Man geht an de Anfang.
• So lange es einen aktuellen Wert gibt und dieser kleiner ist, als der einzufügende Wert ist: Gehe weiter
• Füge den Wert ein.

Somit haben wir den Ablauf beschrieben und können diesen in Code schreiben:

void sortList(List toSort) {
    toSort.toFirst();
    while (true) {
        findWrongValue(toSort);
        if (!toSort.hasAccess) {
            // No more wrong values: List is sorted
            return;
        }
        int nextWrongValue = toSort.getContent();
        toSort.remove();
        insertWrongValue(toSort, nextWrongValue);
    }
}

void findWrongValue(List toSort) {
    int currentValue = toSort.getContent();
    toSort.next();
    while (toSort.hasAccess() && currentValue <= toSort.getContent()) {
        currentValue = toSort.getContent();
        toSort.next();
    }
}

void insertWrongValue(List toSort, int insertValue) {
    toSort.toFirst();
    while (toSort.hasAccess && insertValue > toSort.getContent()) {
        toSort.next();
    }
    toSort.insert(insertValue);
}

Evtl. hat sich ein Fehler eingeschlichen. Aber so sollte man vorgehen. Durch das Aufteilen in Teilprobleme ist jedes kleinere Problem für sich lösbar und einfach umzusetzen.