Public Group

# Insertion sort for linked list

This topic is 3588 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I am trying to develop an insertion sort for a linked list program. I am allowing myself to get confused on something simple and I am not catching what I need to do. I have everything I need in order to sort the linked list I am just having trouble figuring out the correct way to iterate through the list and get back the information I am seeking.
#include <iostream>
using namespace std;

struct Node
{
int data;
};

typedef Node* NodePtr;

* Postcondition: A new node containing the_number has been added at the head of the linked list
*/

void insert(NodePtr after_me, int the_number);

int main()
{
int numbers;

for(int i = 0; i < 5; i++)
{
cin >> numbers;
{
}
else
{
{
//cout << "Need to sort.\n";
for(currNode; currNode != NULL; currNode = currNode->link)
{
if(numbers > currNode->data)
{
insert(currNode, numbers);
}
//printList(currNode);
}
}
else
}
}
}

{
NodePtr temp_ptr;
temp_ptr = new Node;

temp_ptr->data = the_number;

}

{
NodePtr here;

cout << "List contains:\n";
cout << (here->data) << ' ';
cout << endl;
}

void insert(NodePtr after_me, int the_number)
{
NodePtr temp_ptr;
temp_ptr = new Node;

temp_ptr->data = the_number;

}


I know my iteration goes through the list and finds the correct spot but how do I retain that information to be used by the head list. I would like the insertion to be insert(head, number) where insert(currNode, number) is, I am just unsure how to get head to be currNode without losing the information already in head. Thanks for any help.

##### Share on other sites
1) Why are you doing this? The std::list is what you should be using. There's no need to reinvent the wheel.

2) This is almost anti-C++. You should write a container class that has all those methods (insert, etc), and then write iterators to traverse your nodes.

3) You have about a million memory leaks. You must call delete for everything you new.

4) Insertion sort requires a sorted list as a prerequisite. It shouldn't sort the list as it inserts.

##### Share on other sites
I am actually doing this for educational purposes so that I completely understand pointers and linked lists. I agree I haven't cleaned up the memory leaks because I usually do that after the program is doing what I want it to do. Anyway I was trying to see if there was anyway that I could insert the elements in order as I go that way it would be easier to implement a merge sort for two already sorted linked list. I thought by using the head_insert and the insert functions that have been created (I actually got these directly out of Problem Solving with C++ 5th edition) I could accomplish inserting the elements as I go but if I am flawed in my thinking please let me know. Is there no way to do this type of operation with these functions because the text book clearly states in it, that the insert function in the program above is designed for alphabetical and numerical ordering. Thanks for any help.

1. 1
Rutin
46
2. 2
3. 3
4. 4
5. 5
JoeJ
19

• 11
• 15
• 9
• 10
• 13
• ### Forum Statistics

• Total Topics
633004
• Total Posts
3009837
• ### Who's Online (See full list)

There are no registered users currently online

×