Insertion Sort

#include<iostream>
using namespace std;

/* Using some code from the book - see Chapter 19 Programs Number List */
class NumberList
{
private:

	struct ListNode
	{
		double value;
		struct ListNode *next;
	};

	ListNode *head;

public:
	/* Notice that this constructor is different than the one in the book.
	* When a new linked list is made, a head node (which is given the value 0)
	* is created and the head pointer will point to it.  This head node should not be
	* considered part of the data, it is just there to make the sorting easier.
	*/

	NumberList()
	{
		head = new ListNode;
		head->value = 0;
		head->next = NULL;
	}


	void appendNode(double);
	void InsertionSort();
	void displayList() const;
};

void NumberList::appendNode(double num)
{
	ListNode *newNode, *nodePtr;

	// Allocate a new node & store num
	newNode = new ListNode;
	newNode->value = num;
	newNode->next = NULL;

	// If there are no nodes in the list
	// make newNode the first node
	if (!head)
		head = newNode;
	else  // Otherwise, insert newNode at end
	{
		// Initialize nodePtr to head of list
		nodePtr = head;

		// Find the last node in the list
		while (nodePtr->next)
			nodePtr = nodePtr->next;

		// Insert newNode as the last node
		nodePtr->next = newNode;
	}
}


void NumberList::displayList() const
{
	ListNode *nodePtr;

	nodePtr = head;
	while (nodePtr)
	{
		cout << nodePtr->value << endl;
		nodePtr = nodePtr->next;
	}
}

void NumberList::InsertionSort()
{

	/* You can only use the 4 variables listed below.  Dont' create any other variables*/
	/* Don't add any more code than specified by the comments */

	NumberList temp;
	ListNode *add;

	ListNode *addNext;
	ListNode *insert;

	add = head->next; //The first node to be sorted is the one after the head node (which has the value 0)

	while (/*stop when there is nothing left to sort in the original list*/)
	{
		/* Replace this comment with one line of code to assign a value to addNext */

		/* Replace this comment with one line of code to assign a value to insert */

		while ( /*stop when you are at the end of the temp list*/)
		{
			if (/* use the  > operator to determine when to break out of this inner while loop*/)
			{
				break;
			}
			/* Replace this comment with one line of code to assign a value to insert */
		}
		/* Replace this comment with one line of code to assign a value to add->next */

		/* Replace this comment with one line of code to assign a value to insert->next */

		/* Replace this comment with one line of code to assign a value to add */

	}

	delete head;

	/* Replace this comment with one line of code to assign a value to head */

	temp.head = NULL;

}


int main()
{
	NumberList example;
	example.appendNode(5);
	example.appendNode(2);
	example.appendNode(4);
	example.appendNode(7);
	example.appendNode(3);
	example.appendNode(1);
	example.appendNode(6);

	cout << "In original order: " << endl;
	example.displayList();
	cout << "\n\nIn sorted order: " << endl;
	example.InsertionSort();
	example.displayList();

	system("pause");
	return 0;

}