using insertion sort with a linked list

[Julia]

I am trying to sort a linked list using insertion sort. I have seen a
lot of ways to get around this problem but no time-efficient and
space-efficient solution. This is what I have so far:

struct node
{
int x;
struct node *next;
};

void sort(struct node *root, struct node *conductor)
{
while(0 != conductor->next)
{
while(conductor->x < conductor->next->x)
{
conductor = conductor->next;
}
node *temp, *temp2;
temp = new node;
temp2 = new node;
temp = root;
temp2 = root;
while(conductor->next->x temp->x)
{
temp2 = temp;
temp = temp->next;
}
temp2->next = temp->next;
temp->next = temp2->next->next;
temp2->next->next = temp;
}
return;
}

[Kai-Uwe Bux]

Re: using insertion sort with a linked list

Julia wrote:

I am trying to sort a linked list using insertion sort.

Consider using std::list. It has a sort method. Also consider using other
standard containers. There is no need to roll your own list code.

I have seen a
lot of ways to get around this problem but no time-efficient and
space-efficient solution.

If I recall correctly, insertion sort has quadratic complexity anyway. So
what do you mean by efficient?

This is what I have so far:
>
struct node
{
int x;
struct node *next;
};
>
void sort(struct node *root, struct node *conductor)
{
while(0 != conductor->next)
{
while(conductor->x < conductor->next->x)
{
conductor = conductor->next;
}

It appears this loop might run past the end of your list.

node *temp, *temp2;
temp = new node;
temp2 = new node;
temp = root;
temp2 = root;
while(conductor->next->x temp->x)
{
temp2 = temp;
temp = temp->next;
}

Same here. In order to asses correctness, however, one would need to know
the preconditions of the contract for sort.

temp2->next = temp->next;
temp->next = temp2->next->next;
temp2->next->next = temp;
}
return;
}

I am with you so far. Now, what is your question?


Best

Kai-Uwe Bux

[Julia]

Re: using insertion sort with a linked list


Kai-Uwe Bux wrote:

Julia wrote:
>

I am trying to sort a linked list using insertion sort.

>
Consider using std::list. It has a sort method. Also consider using other
standard containers. There is no need to roll your own list code.
>

I know there is no need to write my own code. I am doing it to
challenge for myself as opposed to actually using it for something.

I have seen a
lot of ways to get around this problem but no time-efficient and
space-efficient solution.

>
If I recall correctly, insertion sort has quadratic complexity anyway. So
what do you mean by efficient?
>

Obviously using an insertion sort on a linked list is a waste of time,
energy and space. However, some of the other solutions I have seen to
this puzzel have consisted of transferring the data from the linked
list to an array, sorting the array and transferring the data back to a
linked list. I would like to do this without using that many extra
memory locations.

This is what I have so far:

struct node
{
int x;
struct node *next;
};

void sort(struct node *root, struct node *conductor)
{
while(0 != conductor->next)
{
while(conductor->x < conductor->next->x)
{
conductor = conductor->next;
}

>
It appears this loop might run past the end of your list.

Hmmm... should the while statement be
(conductor->x < conductor->next->x) && (0 != conductor->next)

>

node *temp, *temp2;
temp = new node;
temp2 = new node;
temp = root;
temp2 = root;
while(conductor->next->x temp->x)
{
temp2 = temp;
temp = temp->next;
}

>
Same here. In order to asses correctness, however, one would need to know
the preconditions of the contract for sort.

Should I add the same thing here? The preconditions are that there is a
root that points to the first item in a linked list. The last item in
the list points to a null value. each item in the list contains an
integer value and a pointer to the next item in the list.

>

temp2->next = temp->next;
temp->next = temp2->next->next;
temp2->next->next = temp;
}
return;
}

>
I am with you so far. Now, what is your question?

Right now the program has an infinite loop (i think) for some sets of
data. It works perfectly for other sets of data though.

>
>
Best
>
Kai-Uwe Bux

[Kai-Uwe Bux]

Re: using insertion sort with a linked list

Julia wrote:

>
Kai-Uwe Bux wrote:

>Julia wrote:
>>

I am trying to sort a linked list using insertion sort.

>>
>Consider using std::list. It has a sort method. Also consider using other
>standard containers. There is no need to roll your own list code.
>>

>
I know there is no need to write my own code. I am doing it to
challenge for myself as opposed to actually using it for something.
>

I have seen a
lot of ways to get around this problem but no time-efficient and
space-efficient solution.

>>
>If I recall correctly, insertion sort has quadratic complexity anyway. So
>what do you mean by efficient?
>>

>
Obviously using an insertion sort on a linked list is a waste of time,
energy and space. However, some of the other solutions I have seen to
this puzzel have consisted of transferring the data from the linked
list to an array, sorting the array and transferring the data back to a
linked list. I would like to do this without using that many extra
memory locations.
>

This is what I have so far:
>
struct node
{
int x;
struct node *next;
};
>
void sort(struct node *root, struct node *conductor)
{
while(0 != conductor->next)
{
while(conductor->x < conductor->next->x)
{
conductor = conductor->next;
}

>>
>It appears this loop might run past the end of your list.

Hmmm... should the while statement be
(conductor->x < conductor->next->x) && (0 != conductor->next)

Other way:

( conductor->next != 0 ) && ( conductor->x < conductor->next->x )

This makes sure that conductor->next->x is only evaluated if it is
meaningful.

>>

node *temp, *temp2;
temp = new node;
temp2 = new node;
temp = root;
temp2 = root;
while(conductor->next->x temp->x)
{
temp2 = temp;
temp = temp->next;
}

>>
>Same here. In order to asses correctness, however, one would need to know
>the preconditions of the contract for sort.

Should I add the same thing here? The preconditions are that there is a
root that points to the first item in a linked list. The last item in
the list points to a null value. each item in the list contains an
integer value and a pointer to the next item in the list.

Yeah, you should have a test

conductor->next != 0

before the loop and you should have a test

temp != 0

within the loop.

>>

temp2->next = temp->next;
temp->next = temp2->next->next;
temp2->next->next = temp;
}
return;
}

>>
>I am with you so far. Now, what is your question?

Right now the program has an infinite loop (i think) for some sets of
data. It works perfectly for other sets of data though.

The first of the two loops runs off the end for conductor pointing to a list
that is sorted in increasing order. Is that among the kind of data for
which the program fails?



Best

Kai-Uwe Bux

[Markus Moll]

Re: using insertion sort with a linked list

Hi

Julia wrote:

Obviously using an insertion sort on a linked list is a waste of time,
energy and space. However, some of the other solutions I have seen to
this puzzel have consisted of transferring the data from the linked
list to an array, sorting the array and transferring the data back to a
linked list. I would like to do this without using that many extra
memory locations.

Why don't you use in-place merge-sort or quick-sort?
In-place merge-sort should be easy to implement.

Hmmm... should the while statement be
(conductor->x < conductor->next->x) && (0 != conductor->next)

Actually it would be better to test for conductor->next != 0 _first_, before
trying to dereference conductor->next:

(0 != conductor->next) && (conductor->x < conductor->next->x)

Also, you would have to return after the loop in case 0 == conductor->next,
because then your list is completely sorted.

node *temp, *temp2;
temp = new node;
temp2 = new node;
temp = root;
temp2 = root;
while(conductor->next->x temp->x)
{
temp2 = temp;
temp = temp->next;
}

Some more remarks:

1. You have a memory leak here. You allocate two nodes and immediately
discard all pointer pointing to them.

2. Looks like you're trying to find the two nodes temp2 and temp between
which conductor should be inserted. You should use the
invariant "temp2->next == temp", so you had better initialize temp with
root->next (more intelligible). At the same time, you might think about
renaming these variables ("temp" is rarely a good name).

Should I add the same thing here?

In fact you needn't, as you know that eventually temp->x >=
conductor->next->x (hint: temp == conductor)

You should also consider using a wrapper class (mylist?) around your nodes
so that you cannot pass around internal nodes but only complete lists.
Secondly, I don't see the point in passing conductor as an argument instead
of declaring it as a local variable...

Markus

[Dmitri Sologoubenko]

Re: using insertion sort with a linked list

Kai-Uwe Bux wrote:

Julia wrote:
>

>I am trying to sort a linked list using insertion sort.

>
Consider using std::list. It has a sort method. Also consider using other
standard containers. There is no need to roll your own list code.
>

>I have seen a
>lot of ways to get around this problem but no time-efficient and
>space-efficient solution.

>
If I recall correctly, insertion sort has quadratic complexity anyway. So
what do you mean by efficient?
>

>This is what I have so far:
>>
>struct node
>{
> int x;
> struct node *next;
>};
>>
>void sort(struct node *root, struct node *conductor)
>{
> while(0 != conductor->next)
> {
> while(conductor->x < conductor->next->x)
> {
> conductor = conductor->next;
> }

>
It appears this loop might run past the end of your list.
>

> node *temp, *temp2;
> temp = new node;
> temp2 = new node;
> temp = root;
> temp2 = root;
> while(conductor->next->x temp->x)
> {
> temp2 = temp;
> temp = temp->next;
> }

>
Same here. In order to asses correctness, however, one would need to know
the preconditions of the contract for sort.
>

> temp2->next = temp->next;
> temp->next = temp2->next->next;
> temp2->next->next = temp;
> }
> return;
>}

>
I am with you so far. Now, what is your question?
>
>
Best
>
Kai-Uwe Bux

[Dmitri Sologoubenko]

Re: using insertion sort with a linked list

Markus Moll wrote:

Hi
>
Julia wrote:
>

>Obviously using an insertion sort on a linked list is a waste of time,
>energy and space. However, some of the other solutions I have seen to
>this puzzel have consisted of transferring the data from the linked
>list to an array, sorting the array and transferring the data back to a
>linked list. I would like to do this without using that many extra
>memory locations.

>
Why don't you use in-place merge-sort or quick-sort?
In-place merge-sort should be easy to implement.
>

>Hmmm... should the while statement be
>(conductor->x < conductor->next->x) && (0 != conductor->next)

>
Actually it would be better to test for conductor->next != 0 _first_,
before trying to dereference conductor->next:
>
(0 != conductor->next) && (conductor->x < conductor->next->x)
>
Also, you would have to return after the loop in case 0 ==
conductor->next, because then your list is completely sorted.
>

> node *temp, *temp2;
> temp = new node;
> temp2 = new node;
> temp = root;
> temp2 = root;
> while(conductor->next->x temp->x)
> {
> temp2 = temp;
> temp = temp->next;
> }

>
Some more remarks:
>
1. You have a memory leak here. You allocate two nodes and immediately
discard all pointer pointing to them.
>
2. Looks like you're trying to find the two nodes temp2 and temp between
which conductor should be inserted. You should use the
invariant "temp2->next == temp", so you had better initialize temp with
root->next (more intelligible). At the same time, you might think about
renaming these variables ("temp" is rarely a good name).
>

>Should I add the same thing here?

>
In fact you needn't, as you know that eventually temp->x >=
conductor->next->x (hint: temp == conductor)
>
You should also consider using a wrapper class (mylist?) around your nodes
so that you cannot pass around internal nodes but only complete lists.
Secondly, I don't see the point in passing conductor as an argument
instead of declaring it as a local variable...
>
Markus

PROVA