开发者

Quick Sort using recursion on a linked list

I have to do a quick sort with recursion on a linked list.... So far I've been ok, however I ran into a little problem that I can't see to figure out why it is not working correctly.

Here is the object Node:

    public class Node
    {
      String name;
      Node next;
    }

Here is the program's code:

    public class QuickSortRecusionLinkedList
    {
      public static void quickS(int start, int finish, Node head, Node tail)
      {
        int left = start;
        int right = finish;
        Node pivot = head;
        for(int i = 0; i < ((left+right)/2); i++)
        {
          pivot = pivot.next;
        }
        Node temp = new Node();
        Node leftN = head;
        Node rightN = head;

        while(right > left)
        {
          leftN = hea开发者_如何学运维d;
          for(int i = 0; i < left; i++)
          {
            leftN = leftN.next;
          }
          while ((leftN.name).compareToIgnoreCase((pivot.name))<0)
          {
            left = left + 1; 
            leftN = leftN.next;
          }
          rightN = head;
          for(int i = 0; i < right; i++)
          {
            rightN = rightN.next;
          }
          while ((pivot.name).compareToIgnoreCase((rightN.name))<0)
          {
            right = right - 1;
            rightN = head;
            for(int i = 0; i < right; i++)
            {
              rightN = rightN.next;
            }
          }

          if ( left <= right
             )
          {
            temp.name = leftN.name;
            leftN.name = rightN.name;
            rightN.name = temp.name;

            left = left +1;
            leftN = leftN.next;

            right = right -1;
            rightN = head;
            for(int i = 0; i < right; i++)
            {
              rightN = rightN.next;
            }

            int size = 1;
            temp = head;
            while (temp!=tail)
            {
              temp = temp.next;
              size++;
            }
            temp = head;
            while(temp != tail)
            {
              System.out.print(temp.name + ", ");
              temp = temp.next;
            }
            System.out.println(tail.name + ".");
          }
        }

        if(start < right) 
          quickS(start, right, head, tail);
        if(left < finish) 
          quickS(left, finish, head, tail);
      }

      public static void main(String[] args)
      {
        Node head = new Node();
        Node tail = new Node();
        Node a = new Node();
        Node b = new Node();
        Node c = new Node();

        head.name = "R";
        tail.name = "D";
        a.name = "Z";
        b.name = "C";
        c.name = "P";

        head.next = a;
        a.next = b;
        b.next = c;
        c.next = tail;

        int size = 0;
        Node temp = head;
        while (temp!= tail)
        {
          temp = temp.next;
          size++;
        }

        quickS(0,size,head,tail);
      }

    }

Here is the printout:

C, Z, R, P, D.
C, Z, R, P, D.
C, D, R, P, Z.
C, D, P, R, R.
C, D, P, R, R.
C, D, P, R, R.

The end result should be C, D, P, R, Z. but for some reason the program is substituting Z for another R. What is wrong with the code?


Possible hint: be careful what that temp variable is pointing to when you use it for swapping the name.


With respect this seems like a fool's errand. Quiksort on a linked list will be anything but quick. The whole idea of it is to use arrays. What's the objective here?

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜