Thread: problems with quicksort!

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!

thanks for your response! unfortunately, I don't have a lot of time, so I don't think I can write out all those inserting removal functions. Also, I'm avoiding creating new lists, because each of my nodes has a lot more stuff attached to it, and I'm worried about creating wrong pointers.

The run-time doesn't really matter to me, I just want to be able to sort correctly. What I still don't understand is how it can break when I change the structure of my lists, but I'm still comparing the same keys.