435,011 Members | 2,968 Online
Need help? Post your question and get tips & solutions from a community of 435,011 IT Pros & Developers. It's quick & easy.

# using insertion sort with a linked list

 P: n/a 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; } Aug 6 '06 #1
6 Replies

 P: n/a 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 Aug 6 '06 #2

 P: n/a 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 Aug 6 '06 #3

 P: n/a 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 otherstandard 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. Sowhat 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 knowthe 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 Aug 6 '06 #4

 P: n/a 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 Aug 6 '06 #5

 P: n/a 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 alot of ways to get around this problem but no time-efficient andspace-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 Aug 11 '06 #6

 P: n/a 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 tothis puzzel have consisted of transferring the data from the linkedlist to an array, sorting the array and transferring the data back to alinked list. I would like to do this without using that many extramemory 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 Aug 11 '06 #7

### This discussion thread is closed

Replies have been disabled for this discussion.