Sortieren mit Iterator

[Bobi]

Guten Abend,
Ich habe folgendes Problem ich muss arrayListe mit ListIterator sortieren und es muss funktionieren wie Bubblesort.
Ich versuche die Aufgabe schon seit 8 Stunde zu lösen aber es funktioniert nicht.
Kann mir bitte jemand helfen?

 public static <T extends Comparable<T> > void bubblesort(List<T> a) {
           
        if (a == null) {
            throw new IllegalArgumentException("Null-Referenz uebergeben.");
        }
       
        boolean swapped = false;
       
        ListIterator<T> it = a.listIterator(); 
       
        do {
            swapped = false;

           while(it.hasNext()) {
                T first= it.next();
                T second = it.next();
                   
                     
                if(first.compareTo(second) > 0) {
                     
                    it.previous();
                       it.previous();
                       it.next();
                       it.set(second);
                       it.next();
                       it.set(first);
                     
                     
                       swapped = true;
                    }
                }
          }while(swapped);
       
        }

 

[mihe7]

Im Wesentlichen sehe ich zwei Fehler:

1. Die Zeile ListIterator<T> it = a.listIterator(); muss in die do-while-Schleife gesetzt werden (wenn der Iterator einmal durch ist, fängt er nicht wieder von vorne an, d. h. Du brauchst in jedem Durchgang einen frischen)
2. Du rufst innerhalb der while-Schleife zweimal it.next() auf, um first und second abzurufen. Damit überspringst Du jeweils ein Element.

Beispiel:
DCBA
1. Durchgang: first = D, second = C
2. Durchgang: first = B, second = A
Es fehlt: first = C, second = B

 

[Bobi]

Beispiel:
DCBA
1. Durchgang: first = D, second = C
2. Durchgang: first = B, second = A
Es fehlt: first = C, second = B

Wie du sagst, dann muss ich ein Schritt zurück gehen um C noch einzubeziehen. aber irgendwie es funktioniert trotzdem nicht. Ich verstehe irgendwas wesentliches nicht.

Hat jemand noch Ideen ?

if(first.compareTo(second) > 0) {
                     
                        it.previous();
                        it.set(first);
                        it.previous();
                        it.set(second);
                       
                        it.previous(); // ein Schritt zurück gehen. 
                       
                       swapped = true;
                       
                    }

 

[mihe7]

Was Du jetzt machst: zurück auf second, zurück auf first, zurück auf first-1, das nächste next() liefert dir dann erst einmal first-1. Du willst aber, dass das nächste next() (am Anfang der Schleife) Dein second liefert.
Sollte also in etwa so funktionieren:

T first = it.next(); // first
T second = it.next(); // second
if (vertauschen) {
    it.previous(); // liefert second
    it.set(first);
    it.previous(); // liefert first
    it.set(second);
    it.next(); // liefert first, nächstes next() liefert second
    swapped = true;
} else {
    it.previous(); // liefert second, nächstes next() liefert second
}

UPDATE: Man muss die Invariante des Iterators verstehen. Der "Zeiger" des Iterators steht immer so, dass next() das nächste Element, previous() das vorhergehende Element liefert.
Gibt ein Aufruf von next() also das Element e zurück, muss ein unmittelbar folgender Aufruf von previous() folglich ebenfalls e liefern.

 

[Bobi]

mihe7 Viele danke zuerst.
Ich hatte noch eine Kleine Fehler in meinem Code, habe ich korrigiert und es hat Funktioniert.

UPDATE: Man muss die Invariante des Iterators verstehen. Der "Zeiger" des Iterators steht immer so, dass next() das nächste Element, previous() das vorhergehende Element liefert.
Gibt ein Aufruf von next() also das Element e zurück, muss ein unmittelbar folgender Aufruf von previous() folglich ebenfalls e liefern.

Ich habe so viel rumexperimentiert next() und previous() Methoden habe ich verstanden.