bubble-sort-Implementierung, die auf verlinkten Listen

Muss ich implementieren einen BubbleSort-Algorithmus eine verkettete Liste statt einem array. Ich bin neu in java also ich weiß wirklich nicht, wie man es in code. Aber ich habe es ausprobiert, und hier ist was ich habe:

SinglyNode.java

public class SinglyNode
{
public Object names;
public SinglyNode next;

public SinglyNode (Object name1)
{
    names = name1;
}

public SinglyNode (Object name2, SinglyNode next1)
{
    names = name2;
    next = next1;
}

Object getObject()
{
    return names;
}

SinglyNode getNext()
{
    return next;
}

void displayLink()
{
    System.out.print("{" + names + "}");
}
}

LinkList.java ich glaube mein problem wird hier in der Methode. Ich weiß nicht, wie man implementieren Sie den BubbleSort so würde das Sortieren von Objekt-Namen in aufsteigender Reihenfolge.

public class LinkList
{
SinglyNode first;

public boolean isEmpty()
{
    return (first == null);
}

void insertFirst(Object name1)
{
    SinglyNode newNode1 = new SinglyNode(name1);
    newNode1.next = first;
    first = newNode1;
}

SinglyNode delete(Object name2)
{
    SinglyNode temp = first;
    first = first.next;
    return temp;
}

void display()
{
    System.out.print("LIST: \n");
    SinglyNode current = first;
    while(current != null)
    {
        current.displayLink(); //print data
        current = current.next; //move to next link
    }
    System.out.println("\n");
}
//////////////////////////////////////////////////////   
void bubbleSort()
{ 
    Object n = first;
    Object temp = first;

    if (na.compareTo(first) < first.compareTo(na))
    {
        temp = na.compareTo(first);
    } else {
        temp = first.compareTo(na);
    }
    System.out.println(temp);

}

private void swap(Object one, Object two)
{ 
    Object temp = one.names;
    one.names = two.names;
    two.names = temp; 
}
}

SinglyLinkList.java

public class SinglyLinkList
{
public static void main (String args[])
{
    LinkList list = new LinkList();

    list.insertFirst("Squirtle");
    list.insertFirst("Bulbasaur");
    list.insertFirst("Charmander");
    list.insertFirst("Pichu");
    list.insertFirst("Ghastly");
    list.insertFirst("Mewtwo");
    list.insertFirst("Dialga");

    list.display();
    list.bubbleSort();
    list.display();

}
}

InformationsquelleAutor lmpgdn | 2013-04-16

In der Liste wird es helfen haben ein Größe-Feld, um die Nummer zu speichern der Elemente in der Liste. Auch die Klasse SinglyNode implement Comparable so die compareTo Methode verhält, wie Sie wollen. Die in-place-vertauschen von zwei Elementen in Einzel-LinkedList ist tatsächlich ziemlich beteiligt, und die Leistung ist wirklich schlecht!

public void bubbleSort
{
  for (int i = 0; i < size; i++)
  {
    for (int j = i; j < size; j++)
    {
       if (elementAt(j).compareTo(elementAt(j+1)) > 0)
       {
          swap(j, j + 1);
       }
    }
  }
}

public SinglyNode elementAt(int index)
{
   SinglyNode temp = first;

   for (int i = 0, i < index; i++)
   {
      temp = temp.getNext();
   }

   return temp;
}

public void swap(int firstIndex, int secondIndex)
{
   SinglyNode secondNext = elementAt(secondIndex).getNext();       
   SinglyNode second = elementAt(secondIndex);
   SinglyNode first = elementAt(first);
   SinglyNode firstPrevious = elementAt(first - 1);


   firstPrevious.setNext(second);
   first.setNext(secondNext);
   second.setNext(first);
}

Ähm, wird diese noch funktionieren auf einer Schnur? Ich bekomme Fehler. Vielleicht, ich weiß nicht, wie es zu benutzen
Vielleicht SinlgyNode enthalten sollte String nicht Object. Wenn Sie implement Comparable können Sie zurück name.compareTo(other.name) die String Vergleich.

InformationsquelleAutor The Cat

0

Sie implementieren müssen, um die Vergleichbar-Schnittstelle in der SinglyNode und Verwendung der string-compare-Methode innerhalb der Umsetzung. So etwas wie:
```
public void compareTo(SinglyNode node){
    return this.names.toString.compareTo(node.getNames().toString());
}
```
Oder besser, nur this.names.compareTo(node.getNames());

Jedoch statt nur mit dem Objekt-Klasse, ich würde die Nutzung Vergleichbarer Schnittstelle für diejenigen, die Platzhalter-Objekte.

InformationsquelleAutor Khanser
0

Da es Hausaufgaben/Zuordnung, gebe ich einen Tipp anstatt der direkten Lösung. Bubble-sort abstrahiert werden kann, um diese beiden Operationen: iteration über Sammlung und Austausch von Elementen. Diese Vorgänge werden unterschiedlich implementiert mit array oder einer verknüpften Liste, aber der algoritm ist die gleiche. Sie haben iteration in display, jetzt müssen Sie implementieren, austauschen dann tun (sehr abstrakte pseudocode:
```
iterate {
 iterate {
  if el.Compare(elNext) > 0 {
    swap(el, el.Next);
  }
 }
}
```
InformationsquelleAutor Andrey
0

1) Sie implementieren müssen, um Vergleichbare

2), müssen Sie auch verwenden die swap-Methode bubblesort. Derzeit sind Sie nicht verwenden, und es wird nur der Vergleich der beiden Objekte ohne Tausch im eigentlichen Liste.

Verwenden Sie die tutorial für die Vergleichbaren
- Könnte ich noch verwenden Vergleichbar, ohne dass ein array?
- Das Objekt, das Sie vergleichen möchten, sollten zu implementieren, Vergleichbar! Nichts zu tun mit dem array!
InformationsquelleAutor Nidis

Beispiel verknüpfte Liste, bubble-sort, der nicht emulieren random access mit einer elementAt () - Funktion, und stattdessen betreibt über die verbindungen zwischen den Knoten, so dass die Zeit-Komplexität ist O(n^2) statt viel schlimmer. "end" wird verwendet, um zu verfolgen, wo die sortierten Knoten am Ende der Liste beginnen. Verwendet habe ich das Beispiel-code aus der Frage, und nicht die Mühe das ändern der Klasse vergleichbar, mit toString() stattdessen für die vergleichen. Ich verwendet eine dummy-Knoten, um den code vereinfachen.

void bubbleSort()
{ 
    if(first == null)
        return;
    SinglyNode dmy = new SinglyNode("dummy");  //dummy node
    dmy.next = first;
    //end == null or first sorted node at end of list
    SinglyNode end = null;
    int swap;
    do{
        swap = 0;
        SinglyNode prv = dmy;           //previous node
        while(true){
            SinglyNode cur = prv.next;  //current node
            SinglyNode nxt = cur.next;  //next node
            if(nxt == end){             //if at end node
                end = cur;              // update end = cur
                break;                  // and break
            }
            //if out of order, swap nodes
            if(cur.names.toString().compareTo(nxt.names.toString()) > 0){
                cur.next = nxt.next;
                nxt.next = cur;
                prv.next = nxt;
                swap = 1;
            }
            prv = prv.next;             //advance to next node
        }
    }while(swap != 0);                  //repeat untl no swaps
    first = dmy.next;                   //update first
}

InformationsquelleAutor rcgldr

-1

Für bubble-sort, die beide die Rundwege starten von 0. Einige Versionen dieses Algorithmus beginnen, die innere Schleife auf, wo die äußere Schleife ist. So tun, verursacht Probleme für einige Daten.

... Wenn Sie ein array mit den folgenden, die Sie wollen sortiert:

23,3,1,2,3,4,5

sortierten array, wenn beide Schleifen bei 0 beginnen würde: 1, 2, 3, 3, 4, 5, 23

Aber wenn die innere Schleife beginnt bei j=i, sortierten array wäre 23, 1, 2, 3, 3, 4, 5. Dies ist, weil die innere Schleife beginnt ab dem ersten element (die 3) nach bringt es 23 an der richtigen Stelle und nie herausfindet, wo die 3 mehr

InformationsquelleAutor Sesh

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.