Need help with insertion sort for a C++ linked list. Should be a simple fix

Basically, I have to sort the linked list using insertion sort. I'm not very good at understanding the syntax behind the sort methods and feel completely lost with this list. I would really appreciate any help. I've done a ton of Googling but haven't had much luck finding out how to solve this. My instructor posted exactly what needs to be put on what line, but I'm still having trouble as I don't know what to do.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#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)
{
    //Just copy and paste the code for this function from the book.
    //Don't add anything new
 
    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
{
    //Just copy and paste the code for this function from the book.
    //Don't add anything new
    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();
       
        return 0;
}
Last edited on
Topic archived. No new replies allowed.