Liste und Bubble Sort

[Siegrein]

Hallo Leute,
bin neu hier und habe gerade das Modul Info I an der Uni, bin Java-Anfänger.

In einer Altklausur war folgende Aufgabe gestellt:

public class Liste{
  public int val;
  public Liste next;
}

public class SortList{
 public Liste sort(Liste a){

Ich soll nun die Methode sort schreiben, und zwar soll die übergebene Liste a mit dem Bubblesort-Verfahren sortiert werden.

Mein Versuch

public Liste sort(Liste a){
   boolean swapped;
   do{
       swapped=false;
      
       //Nun geh ich bis zum Ende der Liste
       
       while(a.next!=null){
           if(a.val>a.next.val){
          
           //Ich vertausche zwei Listenelemente

              b=a.next.next;
              a.next.next=a;
              a.next=b;
              swapped=true;
           }
           else a=a.next;
       }
  while(swapped);
}

Ist das soweit akzeptabel?
Jetzt habe ich aber das Problem, das beim Start der äußeren Schleife immer wieder beim ersten Listen-Element begonnen werden muss. Wenn man Bubble-Sort auf ein Array anwendet, ist ja klar, wie das geht (Einfach die Zählvariable auf den 0-ten Index zurücksetzen). Aber wie macht man es hier?

Beste Grüße

 

[JavaMeister]

Dein "a" ist sozusagen der Start.

Den solltest du nicht verändern. Bzw. Musst du dir eine andere Laufvariable ausdenken.

Momentan testest du ob a und der nachfolger vertauscht werden müssen, und tauscht dann den nachfolger mit dessen nachfolger.

Also zu weit nach forne.

 

[njans]

Liste als Namen für einen Container zu nehmen klingt eher unüblich.

public class Liste
{
  private ListenBehaelter erster;
}

public class ListenBehaelter
{
  private ListenBehaelter naechster;
  private int wert;

  public ListenBehaelter gibNaechsten()
  {
    return naechster;
  }

  public int gibWert()
  {
    return wert;
  }
}

Das wäre so grob meine Vorstellung.

 

[JavaMeister]

Ist aber nicht das Problem hier.

 

[Siegrein]

Dein "a" ist sozusagen der Start.

Den solltest du nicht verändern. Bzw. Musst du dir eine andere Laufvariable ausdenken.

Momentan testest du ob a und der nachfolger vertauscht werden müssen, und tauscht dann den nachfolger mit dessen nachfolger.

Also zu weit nach forne.

Hey, danke für deine Antwort!

Vertausche ich in meiner If-Abfrage nicht a mit dem Nachfolger?
a.next.next ist doch praktisch die next-variable im Nachfolger von a.
Also die Referenz des Nachfolgers von a auf dessen Nachfolger.
In b speichere ich diese Referenz ein.
Dann lasse ich den Nachfolger von a auf a zeigen, und a selbst soll auf das Element zeigen, auf das vorher der Nachfolger von a gezeigt hat, also a.next=b.

Leider versteh ich das mit der anderen Zählvariable nicht ganz.
a ist doch gerade der erste Knoten. Wenn der erste Knoten aber mit dem zweiten getauscht wird, ist a doch der zweite Knoten, nicht mehr der erste...

Gruß