1. ## 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!

2. You're approach is wrong unfortunately. You've obviously written an array sorting algorithm at some point and you're applying the same methods of sorting to a list. Don't do that! A list is fundamentally different and needs different actions to sort it.

E.g. an array has constant-time lookup but linear time insertion. A list has linear-time lookup, but constant-time insertion.
You can still perform essentially the same algorithm with a list, but you need to do things a little differently.
There are some techniques that don't work well for singly-linked-lists:
• Swapping
• Reverse iterating
You've already seen first-hand how annoyingly difficult those are and have attempted to write helper functions for them because of how tricky they actually are. But it doesn't have to be that way. The answer is to not fight with the data structure, just work with its different strengths.
When it comes to singly-linked-list sorting, you abandon any use of the above operations completely.
Instead you adopt some different techniques that are perfectly suited to lists:
• Insertion
• Removal
• Prepending
• Appending
• Splitting lists
• Concatenating lists
Being able to easily do all of these new operations quickly and easily certainly makes up for what you lose with not being an array any more.

Now lets see how this applies to the partitioning step of quicksort (to start with).
In the array version we take a single portion and split it into two portions, one of items less-than the splitter, and one of items not less than the splitter. We can still logically do exactly that for singly-linked lists. However instead of swapping items, you iterate forwards over the input list, removing each item as you go, and prepending (or appending if you prefer) each item onto one of two new lists. One new list for the less-than items, and one new list for the not-less-than items.
Try to take a moment to understand what this all means (ponder it for a bit until it all 'clicks') and start over from scratch.
The good news is that the actual solution is far simpler than what you have already! You'll find it really easy if you do it the right way.

You need to get rid of your helper functions entirely anyway. If you were to use those then your sort function would end up more like O(n^4) which is awful, and not really quicksort anymore. Not to mention that actually performing a swap on linked lists is even harder than you realise. Your code almost certainly didn't take into account every case, such as when one item comes after the one you want to swap it with. That's possibly where your infinite loop comes from. Trust me, I've tried it and it's really a pain to get right!

3. 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.

4. Insertion into a linked-list is only two short lines of code! You don't even need to write a function for it. All six of the things I mentioned are either one or two short lines of code each!
Those six list operations are the basic things you should be using.
Not having much time is precisely why you should immediately stop going down the dead-end path that you're going down.

As long as you are aware that you're doing it completely the wrong way, and are likely to get a low mark if this is what you turn in (IMHO), here's a big hint for your current code:
What does findBefore return when right==list, i.e. you've reached the start of the list?
Bonus question: What prevents the first for-loop form looping until it goes past the end of the list? (It is prevented, but I'm just seeing if you know why, and I'll help you out furthur if you can answer that correctly)

Also, get rid of that malloc. You don't allocate heap memory while quicksorting, especially not when all you do is leak it.