Jump to content
  • Advertisement
Sign in to follow this  
toogreat4u

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.

If you intended to correct an error in the post then please contact us.

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;
	Node* link;
};

typedef Node* NodePtr;

void head_insert(NodePtr& head, int the_number);
/* Precondition: The pointer variable head points to the head of a linked list.
 * 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);

void printList(NodePtr head);

int main()
{
	int numbers;
	NodePtr head = NULL;

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

void head_insert(NodePtr& head, int the_number)
{
	NodePtr temp_ptr;
	temp_ptr = new Node;

	temp_ptr->data = the_number;

	temp_ptr->link = head;
	
	head = temp_ptr;
}

void printList(NodePtr head)
{
	NodePtr here;

	cout << "List contains:\n";
	for(here = head; here != NULL; here = here->link)
		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;

	temp_ptr->link = after_me->link;
	after_me->link = temp_ptr;
}

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!