Double-linked list shaker sort

[lekfanda]

Hi everybody.
I'm havin problems with an assignment where I have to sort a randomly generated double linked list. I must only edit the swap and sort functions where '//Edit here' is written. For starters I don't understand how the pointer *A, on the argument of the swap function, is connected with the list_element struct. Tbh I don't even know where to start so I'd appreciate even the stupidest of ideas.

#include "stdafx.h"
#include<iostream>
#include<cstdlib>
using namespace std;

struct list_element {
	int i;
	list_element *prev, *next;
};

struct list {
	list_element *head, *tail;
};

list construct(int len) {
	srand(len);
	list l;
	l.head = new list_element;
	l.head->i = rand() % len;
	l.head->prev = 0;
	l.head->next = 0;
	l.tail = l.head;
	for (int i = 1;i<len;i++) {
		l.tail->next = new list_element;
		l.tail->next->prev = l.tail;
		l.tail = l.tail->next;
		l.tail->i = rand() % len;
		l.tail->next = 0;
	}
	return l;
}

void print_forward(list l) {
	list_element* current = l.head;
	do {
		cout << current->i << endl;
		current = current->next;
	} while (current);
}

void print_backward(list l) {
	list_element* current = l.tail;
	do {
		cout << current->i << endl;
		current = current->prev;
	} while (current);
}

void free(list l) {
	do {
		list_element* current = l.head;
		l.head = l.head->next;
		//cout << "deleting " << current->i << endl;
		delete current;
	} while (l.head);
}

void swap(list* l, list_element* A) {
	//Edit here
}

void sort(list* l) {
	//Edit here
}

int main() {

	list l;
	cout << "Eingabe der Listengroesse: \n";
	int len; cin >> len;
	cout << endl;
	if (len == 0) return 0;
	// Konstruktion
	l = construct(len);
	// Ausgabe
	print_forward(l);
	sort(&l);
	print_forward(l);
	// Destruktion
	free(l);

	return 0;
}

[JLBorges]

This is nonsense: void swap( list* l, list_element* A )
Ask your teacher to clarify.

[lekfanda]

This is nonsense: void swap( list* l, list_element* A )

That's where I'm having the most trouble. The assignment also has some written extra explanations which could maybe make that function a little bit clearer. Ok so this is what it says: "The routine gets a pointer to a list, as well as a pointer to a list element.
When swapping, it is only allowed to change the pointers in list_element.". I know it doesn't make much sense but maybe someone can figure it out from this godforsaken code.

[lekfanda]

Ok, so I figured some things out. For starters A at the argument is just a pointer to the current node of the list. I managed to figure out the sort code:

void sort(list* l) {
	list_element* bubble_tail = 0;
	int n = 0;
	do {
		list_element* current = l->head;
		list_element* last_swp = l->head;
		do
		{
			n++;
			if (current ->i > current->next->i)
			{
				last_swp = current->next;
				if (current->next == bubble_tail)
				{
					bubble_tail = current;
				}
				swap(l, current);
			}
			else {
				current = current->next;
			}
		} while (current != bubble_tail && current ->next);
		if (last_swp != bubble_tail)
		{
			bubble_tail = last_swp;
		}
	} while (bubble_tail->prev);
	cout << "Number of comparison steps: " << n << endl;
}

So now I just need help with the swap function.

[jonnin]

you can either swap the data or swap the pointers.
data is easier for your list, if you have a pointer to both items to swap.
if your data were very expensive to copy/move, pointers would be better in the long run but more complex logic.

swapping data is typically just
temp = a
a = b
b = temp

[lekfanda]

you can either swap the data or swap the pointers.
data is easier for your list, if you have a pointer to both items to swap.
if your data were very expensive to copy/move, pointers would be better in the long run but more complex logic.

I was going for pointers because I thought this is how the assignment required it but now that I double checked it wasn't necessary to use pointers so I used data swapping and it worked like magic:

void swap(list* l, list_element* A) {
	
	int temp = A->i;
	A->i = A->next->i;
	A->next->i = temp;
	
	/*list_element* temp;
	while (A->next != NULL)
	{
		temp = A;
		A = A->next;
		temp->next = A->next;
		A->next = temp;
	}*/
	/*temp->next = A;
	prev = A;
	A = A->next;*/
}

But since I tried for days with pointers it would be nice to figure that way out too for a change. At the commented section are 2 of the failed tries I made. The program would either stop (not exit) when the swap function was called, or it would strangely output only the first element and equal pairs. So I would appreciate it if somone would help me with the pointers method.

[jonnin]

ok.

you need 4 branches, I think. head and anything swap, tail and anything swap, and 2 middle swaps, and head & tail swap.

for each of those, I advise you to draw a picture of each pointer. You may need 2 temps for it, to hold a.next and b.next while you do surgery. Remember that pointers change everywhere: if you have a-b-c-d in a list, and pointer p points to b, and you mess with p-> next, you change the original list. This is critical to understand.

I can't write out the steps right now, so give this approach a try and if you can't get it I will write something for you tonight.

[lekfanda]

ok.

you need 4 branches, I think. head and anything swap, tail and anything swap, and 2 middle swaps, and head & tail swap.

for each of those, I advise you to draw a picture of each pointer. You may need 2 temps for it, to hold a.next and b.next while you do surgery. Remember that pointers change everywhere: if you have a-b-c-d in a list, and pointer p points to b, and you mess with p-> next, you change the original list. This is critical to understand.

I can't write out the steps right now, so give this approach a try and if you can't get it I will write something for you tonight.

Ok this is the best I could come up with and its starting to give me a serious headache. I don't know what logical element I'm missing here. Because the 'sort' function takes care of the flow control this swap should be enough. Anyway, I'm keeping the thread opened 'till tomorrow night for curiosity's sake then I'm marking it as solved since the original problem was solved.

void swap(list* l, list_element* A) {
	
		list_element* temp1 = new list_element;
		list_element* temp2 = new list_element;
		list_element* h1;
		list_element* t1;

			h1 = l->head;
			t1 = l->tail;

			temp1->i = A->i;
			temp1->prev = A->next;
			temp1->next = A->next->next;
			temp2->i = A->next->i;
			temp2->next = A->next;
			temp2->prev = A->prev;
			

			A = temp2;
			A->next = temp1;
			
			l->head = h1;
			l->tail = t1;


		delete temp1;
		delete temp2;
	//}
	/*int temp = A->i;
	A->i = A->next->i;
	A->next->i = temp;*/
}

[jonnin]

Lists are a royal pain. The best thing to take from an exercise like this is "avoid home-rolling pointer heavy constructs as much as possible".

That said, here is logic for the 2 nodes in the middle of the list swapped.

ap = a.p //ap is a temp. a.p is a's previous. that is the shorthand I use here.
an = a.n
bp = b.p
bn = b.n //ok we saved 4 pointers, the prev and next of a and b

ap.n =b //now put everything in place
b.p = ap
b.n = an
bp.n = a
a.p = bp
a.n = bn

see if that logic works. Hopefully I did not goof it up.

[lekfanda]

Still didn't work; the program crashes at the ap.n = b line. Anyway I don't think beating myself up with this is worth it so I'll just hope I won't have to do with pointers too much. Thanks for the help :)