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?
精彩评论