Lab 9 40 Points The program is for C++ using visual studio You may do this alone or in groups of two. If two people do this lab together, then send only one submission with both names in the program. In this lab, you will write a function that will use the Insertion Sort technique to sort values in a linked list. The basic idea is that you will make a temporary link list. You will start with the first node in your unsorted linked list and insert it into the temporary link list (after the head node with the value 0). Next, you will focus on the second node in your unsorted linked list and insert it into the correct position in the temporary link list. Next, you focus on the third node in your unsorted linked list and insert it into the correct position in the temporary link list. Repeat this process until you have gone through all the nodes in your unsorted linked list. Conceptually, your unsorted linked list is becoming one node smaller in each iteration and your temporary link list gains one node. The key thing to keep in mind is that you are not creating new nodes in the InsertionSort function, you are just rewiring pointers. Therefore, if you start with the head node of the temporary link list and traverse through by following the next pointer, the values will print out in sorted order. That is why at the end, we assign the temporary lists head pointer to the head pointer of the original list. Use the comments in Lab 9.cpp to implement the function. Please take the time to draw out what your code is doing. Sample Output In original order: 0 5 2 4 7 3 1 6 In sorted order: 0 1 2 3 4 5 6 7 Press any key to continue . . .

CPP file provided:

/* Insert Name(s) here */

/* Answer the following quesions in the comments Before starting to progam:

What is the purpose of the following pointers: (look at the code from the book)

head

add

add->next

insert

*/

#include

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)

{

/* Just copy and paste the code for this function from the book.

* Don't add anything new

*/

}

void NumberList::displayList() const

{

/* Just copy and paste the code for this function from the book.

* Don't add anything new

*/

}

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: "<

example.displayList();

cout <<" In sorted order: "<

example.InsertionSort();

example.displayList();

system ("pause");

return 0;

}