I'm writing an inplace quicksort for linked lists, but I seem to have a bug. I don't know if it's because I changed the structure of my list, but it shouldn't be? I'm infinite looping.
here is my quicksort function
Code:
struct label * quicksort(struct table *p, int list_start, int list_end, FILE *o)
{
printTable(p, o);
printf("quicksort starting\n");
fflush(stdout);
struct label *list = p->first;
struct label *pivot = malloc(sizeof(struct label));
struct label *left=list;
struct label *right=list;
struct label *tmp;
int i = list_start;
int j= list_end-1;
if (list_start >= list_end) {
return list;
}
//printf("right is %s\n", right->labelsymbol);
right = getNth(list, list_end);
//printf("right is %s\n", right->labelsymbol);
left = getNth(list, list_start);
pivot = right;
right = findBefore(left, pivot);
//printf("right is %s\n", right->labelsymbol);
//printf("went here\n");
//printf("left %s\n", left->labelsymbol);
//printf("pivot %s\n", pivot->labelsymbol);
//printf("%d\n", strcmp(left->labelsymbol, pivot->labelsymbol));
//printf("%d\n", strcmp(right->labelsymbol, pivot->labelsymbol));
fflush(stdout);
printf("right is %s\n", right->labelsymbol);
printf("left %s\n", left->labelsymbol);
printf("pivot %s\n", pivot->labelsymbol);
while (1) {
for(; strcmp(left->labelsymbol, pivot->labelsymbol) < 0; left=left->next,i++);
for(; strcmp(right->labelsymbol, pivot->labelsymbol) > 0; right = findBefore(list,right),j--); //seems to be looping around here, when right is "main" for some reason?
printf("!!!came here\n");
fflush(stdout);
printf("2left %s\n", left->labelsymbol);
printf("2right %s\n", right->labelsymbol);
printf("i %d j %d\n", i, j);
if (i < j) {
list = swapEntries(list, left, right);
tmp = left;
left = right;
right = tmp;
printf("swapped\n");
fflush(stdout);
}
else
break;
}
list = swapEntries(list, left, pivot);
printf("came here\n");
printTable(p, o);
fflush(stdout);
printf("next %d %d\n", list_start, i-1);
list = quicksort(p, list_start, i-1, o);
printf("next %d %d\n", i+1, list_end);
list = quicksort(p, i+1, list_end, o);
//printTable(p, o);
return list;
}
here are the helpers I use:
Code:
struct label *getNth(struct label *node, int n)
{
int i=1;
for(i=1;i<n;i++)
{
node = node->next;
}
return node;
}
struct label *findBefore(struct label *list, struct label *current) {
//printf("finding before %s\n", list->labelsymbol);
//printf("current %s\n", current->labelsymbol);
for(;list && list->next; list = list->next) {
if(strcmp(current->labelsymbol, list->next->labelsymbol) == 0) {
break;
}
}
if (list->next != current) {
return current;
}
return list;
}
struct label *swapEntries(struct label *list, struct label *node1, struct label *node2) {
struct label *node1prev;
struct label *node2prev;
struct label *tmp;
node1prev = findBefore(list, node1); //find the node before current
node2prev = findBefore(list, node2);
tmp = node2->next;
if (node1 != list) {
node1prev->next = node2;
}
else {
list = node2;
}
if (node1->next == node2) {
node2->next = node1;
node1->next = tmp;
}
else {
node2->next = node1->next;
node1->next = tmp;
node2prev->next = node1;
}
return list;
}
I don't understand why it's not working now, when it worked before. The table I'm putting in looks like this:
main y 0000
counter y 001C lhi 0002 llo 0006
loop y 000A jmp 0014
done y 0016 jmp 0016
dummy y 001E
foo n FFFF jmp 0020
(I'm only sorting the first labels, so "main", "counter", etc...)
the structs for my table
Code:
struct label {
char * labelsymbol;
char defined;
int value;
struct lineNode *occur;
struct label *next;
};
struct table {
int labelcount;
struct label *first;
};
this is my printout when I call it
quicksort starting
right is dummy
left main
pivot foo
!!!came here
2left main
2right dummy
i 0 j 5
swapped
!!!came here
2left loop
2right done
i 2 j 4
swapped
!!!came here
2left loop
2right done
i 3 j 3
came here
main y 0000
loop y 000A jmp 0014
next 0 2
main y 0000
loop y 000A jmp 0014
quicksort starting
Any help would be much appreciated! Thanks!