0

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 = head;
          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?

9
  • 1
    either reformat the code or pastebin it. Commented Feb 23, 2011 at 12:56
  • What do you see when you use the debugger? Commented Feb 23, 2011 at 13:01
  • First off, I have no clue how to edit the code so that it is normal, and not all wierd as i have it right now... this was the best i could manage sorry. Commented Feb 23, 2011 at 13:07
  • 3
    Is this homework? If not, why not just use Collections.sort? Commented Feb 23, 2011 at 13:08
  • 1
    A good opportunity to get to know your debugger. Commented Feb 23, 2011 at 13:12

2 Answers 2

2

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

Sign up to request clarification or add additional context in comments.

3 Comments

Thanks johusman! It worked perfectly after i put temp = new Node(); before the swap... thanks
Still feel a bit dirty for helping people with homework, but it wasn't really related to the quicksort algorithm per se, just a silly oversight :)
you hardly did his homework for him! You just pointed out a [small] logical error
1

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?

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.