Sorting Circular Linked List

[shadabrana]

cur does not change after first if condition

void sort()
{
if(!isEmpty())
{
int check = 0;
Process *cur = head;
do
{
cur = cur->Next;
check++;
}while(cur != head);
for (int k = 0; k < check; k++)
{
cur = head;
for(int n=0; n < check; n++)
{
if( (cur->arrTime) > (cur->Next->arrTime) )
{
string name = cur->name;
int arr=cur->arrTime,burst=cur->burstTime;
cur->name = cur->Next->name;
cur->arrTime = cur->Next->arrTime;
cur->burstTime = cur->Next->burstTime;
cur->Next->burstTime = burst;
cur->Next->arrTime = arr;
cur->Next->name = name;
cur = cur->Next; // issue here
}
else
{
cur = cur->Next;
}
}
}
}

[Handy Andy]

Hello shadabrana,

PLEASE ALWAYS USE CODE TAGS (the <> formatting button) when posting code.
It makes it easier to read your code and also easier to respond to your post.
http://www.cplusplus.com/articles/jEywvCM9/
http://www.cplusplus.com/articles/z13hAqkS/
Hint: You can edit your post, highlight your code and press the <> formatting button.
You can use the preview button at the bottom to see how it looks.

Looking around I found that you have not received any response yet.

If you would have looked at the code after using code tags you would have seen that your copy and paste may have left out the closing brace '}' of the function or maybe it was not there to begin with,

void sort()
{
	if (!isEmpty())
	{
		int check = 0;
		Process *cur = head;

		do
		{
			cur = cur->Next;
			check++;
		} while (cur != head);

		for (int k = 0; k < check; k++)
		{
			cur = head;
			for (int n = 0; n < check; n++)
			{
				if ((cur->arrTime) > (cur->Next->arrTime))
				{
					string name = cur->name;
					int arr = cur->arrTime, burst = cur->burstTime;
					cur->name = cur->Next->name;
					cur->arrTime = cur->Next->arrTime;
					cur->burstTime = cur->Next->burstTime;
					cur->Next->burstTime = burst;
					cur->Next->arrTime = arr;
					cur->Next->name = name;
					cur = cur->Next; // issue here
				}
				else
				{
					cur = cur->Next;
				}
			}
		}
	}
}

With proper indenting it is easier to see that.

There is a good chance that you have used the line using namespace std; somewhere in your program file(s) and this could be a potential problem with your function "sort" as there is a function"std::sort" in the <algorithm> header file anm maybe somewhere else.

When it comes to "class", "structs" and function names I like to start the names with a capital letter to help keep it separate from a variable name or something that might be in the standard name space. Another option is to name the function something like "SortLL" or a name that is more descriptive of what the function does. For now it may be easier to start the name with a capital letter.

You say that you have an issue with line 29, but you say nothing about line 34. My question is on line 29 what does "cur->Next" actually contain?

Now that I notice it variable names are best when they start with a lower case letter. Being in a class or struct do not give regular variables any special privilege.

Right now I do not see anything with line 29 other than what "cur->Next" is. If this is not a good address then you will have a problem.

Without the rest of the program I have no way to test the function. And there might even be a better way to sort the linked list.

Hope that helps,

Andy

Edit:

I noticed line 3 which says if(!isEmpty()). If what is not empty. You could either have an endless loop or an if condition that is never true.

[lastchance]

Can't you just swap pointers instead of having to create a whole load of temporary variables to swap things? That is one big advantage of linked lists.

(Also, aren't there conceptual difficulties with sorting a circular linked list? Who is at the head of a round table?)

[icy1]

@shadabrana -- Maybe try sorting on a regular linked list first -- I suspect there are many problems with this selection sort logic. Review the pseudo-code from the wiki, for example.

Also, instead of awkwardly computing the size at the time of sort, you could be keeping track of a size counter that increments/decrements at each add or remove.

[dhayden]

Also, aren't there conceptual difficulties with sorting a circular linked list?

Since there's a head pointer, I think it's safe to assume that head points to the beginning of the list.

cur does not change after first if condition

Okay, it's a silly question, but is there only 1 item in the list? That would result in cur not changing.

If there are more items in the list then it's likely that the list itself is corrupted. Try printing it out before you sort it to ensure that the list is valid.

Replace lines 29-34 with

}
cur = cur->Next;

If you adjust the pointers rather than copying the data around (and you should). Then be sure to handle the case of swapping head with head->next. You'll have to adjust head too.

[jonnin]

I might seriously consider breaking the list at head, making it a normal list, sorting it, and then reconnecting it. While you can avoid wraparound mistakes if you code it carefully, this would let you use a tried and true algorithm / approach without the additional complexity, and putting the circle link back in is cheap, just an assignment statement...

what do you guys think??