sorting of linked list

[MrPlus7]

I am trying to sort a linked list by being sneaky and only swap the data. I though this might be easier to implement, but I cannot manage to get it right.

Anyone, please, what is that I'm doing wrong?

 void LinkedList::sort() {
			ListItem *preA=root;
			ListItem *A = preA->next;

			int i, j, j1,j2;

			for (i = 1; i < getSize(); i++) {
			
				j = i;
				
				preA->set_item(getItem(j-1));
				j1 = preA->get_item();

				A->set_item(getItem(j));
				j2 = A->get_item();


				while (j > 0 && j2 < j1) {
				
					// swap the data only

					preA->set_item(j2);
					A->set_item(j1);
						

					j = j - 1;

					preA->set_item(getItem(j-1));
					j1 = preA->get_item();

					A->set_item(getItem(j));
					j2 = A->get_item();
				

					}

				}

		}

[jonnin]

you have it backwards. you want to only swap a pointer, not all the data under it. Moving the data costs a lot more, if its bigger than a pointer, and it usually will be.

I don't see your issue, but swapping the pointers is absolutely what should happen, so you may need a re-do.

a serious ll sort is probably going to do some sort of recursive splitting of the list and merge sorting back. you split until you have 1 item in each list, then grab 2 of them and make that a sorted list of 2. Then you do that again for all the pairs, then merge sort all the pairs into lists of 4, all of those into 8, etc until its rebuilt, all by pointer manipulation.

[MrPlus7]

Thanks! I was trying to swap the pointers initially but could´t get that to work either. Hence, as a preliminary fix i´d like to swap the data until I get a bit more cpp-savvy. If this were an array this would be easy. Now, there is probably something related to pointer and memory addressing I do not get.

[jonnin]

it works like anything else. Pointers are often poorly taught, causing an aura of mystery that keeps students in a state of confusion. But they are just variables. Really, they are just integers that store an offset into your ram.

type * tmp;
tmp = a;
a = b;
b = tmp; //same way you swap anything.

but you don't generally swap things to sort lists.
its more of surgical removal and reinsertion.
eg
tmp = node->next;
node->next = node->next->next; //cut tmp out of the list
and reinsert tmp where it belongs, setting up its next to go somewhere else.

along those lines..
unfortunately you have special cases for empty lists, lists with 1 guy, or fooling with the first or last node. Do you see why?

[MrPlus7]

I found a workaround by creating an array from the list, sort the array and then recreate the list. Not very elegant or efficient, but at least I made this work.
I should now try again to do it the proper way, i.e. moving the pointer...

Thanks for your input!

[jonnin]

its very efficient, if the array is an array of pointers, and you write a custom sort comparison to dereference the data, its probably faster than sorting the list itself, or at worst identical.