Implementering av Insertion Sort

[martingee]

Hei!

Det er forøvrig JAVA det dreier seg om ^^

 

Jeg prøver å implementere en Insertion Sort metode i en eksisterende klasse.

Får ikke sorteringen til å fungere som den skal.

Kan noen hjelpe?

 

Under er den eksisterende koden.

 

/**
* This class is the same as ListStack, except that it keeps
* a pointer to the last element. This makes it suitable for
* implementation of a queue.
* 
* @author 
* @version 1.0
*/
public class ListQueue
{
   /** The list node class. Declared as a private inner
    * class because it is an implementation detail.
    * Nobody else needs to know about it. */
   private class Node {
       int data;
       Node next;

       public Node(int data, Node next) {
           this.data = data;
           this.next = next;
       }


       public void display() {
           System.out.print(" "+data);
       }
   }


   /** The start of the list */
   private Node first;
   private Node last;


   public ListQueue() {
       first = null;
       last = null;
   }


   public void insertFirst(int data) {
       // if empty, we don't want to mess with the last pointer here
       if (first == null) insertLast(data);
       else first = new Node(data, first);
   }


   public void insertLast(int data) {
       if (first == null) {
           // insert in empty queue - new node is both first and last 
           first = new Node(data, null);
           last = first;
       }
       else {
           last.next = new Node(data, null);
           last = last.next;
       }
   }



   public int removeFirst() throws Exception {
       if (first != null) {
           int data = first.data;
           // if we removed last, both first and last must be null
           if (first == last) {
               last = null;
               first = null;
           }
           else first = first.next;
           return data;
       }
       else throw new Exception("Can't remove from empty list!");
   }


   /** print queue contents */
   public void display() {
       System.out.print("Queue contents: {");
       Node current = first;
       while (current != null) {
           current.display();
           current = current.next;
       }
       System.out.println(" }");
   }


   /** enqueue() is an alias for insertLast() */
   public void enqueue(int data) {
       insertLast(data);
   }


   /** dequeue() is an alias for removeFirst() */
   public int dequeue() throws Exception {
       return removeFirst();
   }


   /** Demo */
   public static void main(String[] args) throws Exception {
       ListQueue q = new ListQueue();
       q.enqueue(1);
       q.enqueue(2);
       q.display();
       System.out.println(q.dequeue());
       System.out.println(q.dequeue());
       q.display();
       q.enqueue(3);
       q.enqueue(4);
       q.insertFirst(5);
       q.display();
   }
}

 

Og her er sorteringsmetoden vi ønsker å ha inn.

Den fungerer som sagt ikke som den skal.

Hvordan kan løse dette?

 

    
       public void sort() {

       Node old = first.next;
       Node current = first;

       first.next = null;

       while (old != null) {
           Node temp = old;
           old = old.next;

           while (current.next != null && current.data >= temp.data) {
               current.next.data = current.data;
               first.data = temp.data;
               current = current.next;
           }
           current.data = temp.data;
       }
   }

Endret 12. februar 2010 av martingee

[pgdx]

Jeg prøver å implementere en Insertion Sort metode i en eksisterende klasse.

Får ikke sorteringen til å fungere som den skal.

Kan noen hjelpe?

 

Og her er sorteringsmetoden vi ønsker å ha inn.

Den fungerer som sagt ikke som den skal.

Hvordan kan løse dette?

Hva er problemet, igjen? Ikke bare gi masse kode som ikke fungerer, si nøyaktig hva som ikke fungerer, hva er symptomene? Blir output omvendt av hva du forventer? Er det noen elementer som ikke blir sortert? Går den i en uendelig løkke?