bubble sort implementation on linked lists

问题:

I have to implement a BubbleSort algorithm on a Linked List instead of an array. I'm new to java so I don't really know how to put it in code. But I gave it a try and here's what I got:

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 I think my problem is here in the method. I dunno how to implement the BubbleSort so it would sort the Object names in ascending order.

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();

}
}

回答1:

In your list it will help to have a size field, to store the number of elements in the list. Also make the class SinglyNode implement Comparable so the compareTo method behaves as you want. The in-place swapping of two elements in Single LinkedList is actually quite involved, and the performance is really bad!

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

回答2:

You need to implement the Comparable interface in the SinglyNode and use the string compare method inside the implementation. Something like:

public void compareTo(SinglyNode node){
    return this.names.toString.compareTo(node.getNames().toString());
}

Or better just this.names.compareTo(node.getNames());

However instead of just use Object class, I would the use Comparable interface for those wildcard objects.

回答3:

Since it is homework/assignment, I will give a hint instead of direct solution. Bubble sort can be abstracted to this two operations: iteration over collection and swapping elements. Those operations are implemented differently with array or linked list, but the algoritm is the same. You have iteration in display, now you need to implement swapping then do (very abstract pseudocode:

iterate {
 iterate {
  if el.Compare(elNext) > 0 {
    swap(el, el.Next);
  }
 }
}

回答4:

1) You need to implement Comparable

2) You also need to use the swap method in bubblesort. Currently you are not using this and it will only compare the two objects without swapping them in the actual list.

Use the tutorial for the Comparable

回答5:

Example linked list bubble sort that doesn't emulate random access using an elementAt() function, and instead operates via the links between nodes, so time complexity is O(n^2) instead of being much worse. "end" is used to keep track of where the sorted nodes at the end of the list begin. I used the example code from the question and didn't bother changing the class to comparable, using toString() instead for the compare. I used a dummy node to simplify the code.

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
}

回答6:

For bubble sort, both the loops must start from 0. Some versions of that algorithm start the inner loop at where the outer loop is. Doing so will cause issues for some data.

If ... you have an array with the following that you want sorted:

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

the sorted array if both loops start at 0 would be: 1, 2, 3, 3, 4, 5, 23

But if the inner loop starts at j=i, the sorted array would be 23, 1, 2, 3, 3, 4, 5. This is because the inner loop moves on from the first element (which will be 3) after it puts 23 in the correct place and never figures out where to place 3 anymore