sorting linked list using link manipulation

Hi,

I am stuck at a peculiar problem where in there is a linked list and it has to be sorted out using the link part. Can anyone tell the tips to understand it (if it is desired i can post the entire code here) but how do i understand it because i seem to get lost at one or the other part. (Have spend a couple of hours trying to figure out the logic behind its steps). Please give some suggestions.

I mean if you were to encounter a complex problem how would you proceed to understand it?

Well the simplest way is to sort the list the same way you would sort an array.

Iterate through the list starting from the beginning, and find the node that has the lowest value. Once you have found that node, place it at the beginning of the list. Now iterate through starting at the second node (the one after the one you just moved to the beginning of the list). Do the same thing: find the node with the lowest value, and place it after the first node you moved to the beginning. Keep going until the list is sorted. This is just a bubble sort for linked lists.

I'm not sure where you were going with "has to be sorted out using the link part". Surely you can't mean that you are sorting by the values of the links, because that makes no sense. Do you mean sorting only by switching links, or sorting without switching links, or what?

yes i mean sorting by switching links

[insert]

Code:

#include <stdio.h>
#include <stdlib.h>

struct node{

	int data;
	struct node *link;
};

void getdata();
void display(struct node *);
void selection_sort();
struct node *start;

int main(void){

	start = NULL;
	getdata();
	display(start);
	
	selection_sort();
	display(start);

	return 0;
}

void selection_sort()
{
	struct node *p, *q, *r, *s;
	p = start;
	r = start;
	q = p ->link;
	s = q;

	// nodes being compared are adjacent and p is first node
	while(p ->link != NULL)
	{
		s = q = p->link;

		while(q != NULL)
		{
			if( p == start && p ->link == q)
			{
				if(p ->data > q ->data)
				{
					struct node *temp;
					temp = p ->link;
					p->link = q->link;
					q ->link = temp;
					q = p->link;
					s = p;
					p = r = q;
				}
			}
			else if( p == start && p ->link != q)
			{
				if(p ->data > q ->data)
				{
					struct node *temp;
					temp = p->link;
					p ->link = q ->link;
					q ->link = s;
					s ->link = p;
					q = r->link;
					s = p;
					p = r = q;
					start = p;
				}
			}
			else if(p != start && p->link == q)
			{
				if(p ->data > q ->data)
				{
					struct node *temp1, *temp2;
					temp1 = q->link;
					temp2 = p->link;
					p->link = q->link;
					q ->link = temp2;
					r->link = q;
					q = temp1;
					p = r->link;
					s = p ->link;
				}
			}
			else if(p != start && p->link != q)
			{
				if(p ->data > q->data)
				{
					struct node *temp1, *temp2;
					temp1 = p->link;
					temp2 = q->link;
					p ->link = q->link;
					q ->link = s;
					s ->link = p;
					r ->link = q;
					p = q;
					s = q;
					q = temp2;
				}
			}
			s = q;
			q = q->link;
		}

		r = p;
		p = p->link;
	}
}

void getdata(){
	
	struct node *p, *q;
	char ch;
	int val;
	do{
		
		printf("\nEnter data for the list");
		scanf("%d", &val);;

		// adding the node for the first time
		if( start == NULL)
		{
			p = malloc(sizeof(struct node));
			p ->data = val;
			p ->link = NULL;
			start = p;
		}
		else
		{
			p = start;
			while(p ->link !=  NULL)
				p = p ->link;
			q = malloc(sizeof(struct node));
			q ->data = val;
			q ->link = NULL;
			p ->link = q;
		}
	
		printf("\nAny more data");
		ch = getche();
	}while (ch == 'y' || ch == 'Y');
}

void display(struct node *p){
	
	struct node *temp;
	temp = p;
	while(temp != NULL){
		printf("\n%d", temp->data);
		temp = temp->link;
	}
}

I am getting errors but now i am totally lost in this :-(

Well then there's two parts to the problem, I guess: (1) figuring out how to switch links and (2) deciding which elements of the list to switch. To figure out 1 you should draw some pictures. For number 2 you just need to decide what sort of sorting algorithm you want to use -- bubble sort isn't bad, unless your list is very long; and having two consecutive elements of the list makes doing part #1 slightly easier, I think.

Originally Posted by bithub

Well the simplest way is to sort the list the same way you would sort an array.

Iterate through the list starting from the beginning, and find the node that has the lowest value. Once you have found that node, place it at the beginning of the list. Now iterate through starting at the second node (the one after the one you just moved to the beginning of the list). Do the same thing: find the node with the lowest value, and place it after the first node you moved to the beginning. Keep going until the list is sorted. This is just a bubble sort for linked lists.

Nope you're describing "Selection Sort". Bubble Sort only ever swaps adjacent items.

Trying to "sort the list the same way you would sort an array" is not good. You get neither random access nor the ability to insert/remove in constant time. All good algorithms are therefore out, and anything that is left tends to suck.

By far the easiest and simplest way to sort a list is using Insertion Sort. But if you're comfortable with recursion then MergeSort isn't all that hard and gives much better performance.

@Malc

I like the eternally confuzzled funda that is presented on one of the webpages. I think its a perfect word describing the state i am currently in.

Originally Posted by roaan

Hi,

I mean if you were to encounter a complex problem how would you proceed to understand it?

rooan, as tabstop suggested, draw pictures and code from that. Attached is my attempt to sort in ascending order. Neatness does not count.

Once you get the general case, as I have in the picture, then work on the special cases like:
What if pLargest is the first element pointed at by root?
What if root points to a list with only 1 element or no elements?

A picture that you animate with pencil and eraser will help to bring out the special cases.

I don't know about the code you posted. If you're lost, in it, then its time to scrap it and start over.

I hope that helps you.

Originally Posted by roaan

Hi,

I mean if you were to encounter a complex problem how would you proceed to understand it?

First, for tough problems, back away from the keyboard! How would you swap a tiny linked list by hand (pencil and paper)?

Write that out, step by step, and I recommend selection sort, not bubble sort or any others, for now. Selection sort combines simplicity and efficiency rather well.

In this process, you want to break down the big problem, into small "chunks" that you can first solve, by hand.

Write down each small "chunk" that you need. Clearly, you'll need a "chunk" to swap two nodes in your linked list.

Those "chunks" will become either blocks of code, or functions in your program, later on.

Once you get a very small linked list of 3 nodes to work right by hand, then you can make that the basis for your program.

I would describe this process as breaking down the problem into it's smaller constituent parts, until each part can be understood. Then build these parts back up, using paper and pencil if needed, while you learn "the game" (what the problem is all about).

Don't expect to know the game well, until you know the basic rules and techniques, used. Here, that would be 1) How to swap nodes in a linked list and 2) How to code a selection sort for that list.

Avoid like hell itself, the naturally tendency to start banging away "something" on the keyboard, getting all these lines of code, and having no real understanding why it doesn't work. That's only human perhaps, but it's *definitely* something to be avoided.

@all

Thanks a lot !!!!!!!!!