Help with sorting link lists

[clockworkinferno]

Our teacher never actually teaches us the code making it hard for me to understand how to do the assignment. He only teaches pseudocode and this the first time I actually seen code for link list in c++. So any help would be greatly appreciated.
This is the assignment I have to do.
1. Using the linked list program given in class , alter the
program to input twenty five FLOATS , sorting them
as they are inserted into the list. Print out
the sorted list.



2. Create a linked lists with two info fields, a last name
and a G.P.A. (Ex. Smith, 3.98) Sort the list as it is
created, by G.P.A. (use 1.) Print out list.

Then, delete all entries whose G.P.A. is
less than 2.5. Print out the new list

Finally, create a new list out of this modified
list , this time sorting alphabetically

This is the code we are given by our teacher.

//		This program introduces simple linked lists using pointers					//
// It creates a list of nodes having an id and a grade field and computes the		//
// average of the grades. It also prints out the nodes in the order in which they	//
// are added to the list..It does NOT sort the list..that is YOUR job!!!			//
// D. Pinto FALL 2015 CS 501_112
#include <iostream>
using namespace std;

void getdata(int& ident, int& grade_value);
const int nil = 0;
class node_type		    // declaration of class//
{
public:
	int id;
	int grade;
	node_type *next;
};

void main()
{
	node_type *first, *p, *q, *newnode;
	int i, ident, grade_value;
	float sum, average;
	sum = 0;
	first = new node_type;
	p = first;
	getdata(ident, grade_value);
	(*first).id = ident;
	(*first).grade = grade_value;
	(*first).next = nil;
	for (i = 2; i <= 10; ++i)
	{
		getdata(ident, grade_value);
		newnode = new node_type;
		(*newnode).id = ident;
		(*newnode).grade = grade_value;
		(*newnode).next = nil;
		//**********Links previous node to newnode******//
		(*p).next = newnode;
		p = newnode;
	}
	//**********Traverses list and prints out nodes in chronological order ******//
	q = first;
	cout << "The list contains \n";
	while (q != nil)
	{
		cout << "ID is :" << (*q).id << "\n";
		cout << "GRADE is :" << (*q).grade << "\n";
		sum = sum + (*q).grade;
		q = (*q).next;
	}
	average = sum / 10;
	cout << "\nThe average of the grades is " << average << "\n";

}
void getdata(int& ident, int& grade_value)
{
	cout << "Enter id and grade \n";
	cin >> ident;
	cout << ident << "\n";
	cin >> grade_value;
	cout << grade_value << "\n";
}

[JLBorges]

> This is the code we are given by our teacher.

Are you certain that this is the code given by your teacher?

//    	This program introduces simple linked lists using pointers					//
// It creates a list of nodes having an id and a grade field and computes the		//
// average of the grades. It also prints out the nodes in the order in which they	//
// are added to the list..It does NOT sort the list..that is YOUR job!!!			//
// D. Pinto FALL 2015 CS 501_112
#include <iostream>
using namespace std;

void getdata(int& ident, int& grade_value);
const int nil = 0;
class node_type		    // declaration of class//
{
public:
	int id;
	int grade;
	node_type *next;
};

void main() // *** error: 'main' must return 'int'
{
	node_type *first, *p, *q, *newnode;
	int i, ident, grade_value;
	float sum, average;
	sum = 0;
	first = new node_type;
	p = first;
	getdata(ident, grade_value);
	(*first).id = ident;
	(*first).grade = grade_value;
	(*first).next = nil; // *** error: assigning to 'node_type *' from incompatible type 'const int'
	for (i = 2; i <= 10; ++i)
	{
		getdata(ident, grade_value);
		newnode = new node_type;
		(*newnode).id = ident;
		(*newnode).grade = grade_value;
		(*newnode).next = nil; // *** error: assigning to 'node_type *' from incompatible type 'const int'
		//**********Links previous node to newnode******//
		(*p).next = newnode;
		p = newnode;
	}
	//**********Traverses list and prints out nodes in chronological order ******//
	q = first;
	cout << "The list contains \n";
	while (q != nil) // *** error: comparison between pointer and integer ('node_type *' and 'int')
	{
		cout << "ID is :" << (*q).id << "\n";
		cout << "GRADE is :" << (*q).grade << "\n";
		sum = sum + (*q).grade;
		q = (*q).next;
	}
	average = sum / 10;
	cout << "\nThe average of the grades is " << average << "\n";

}
void getdata(int& ident, int& grade_value)
{
	cout << "Enter id and grade \n";
	cin >> ident;
	cout << ident << "\n";
	cin >> grade_value;
	cout << grade_value << "\n";
}

http://coliru.stacked-crooked.com/a/acda2ebb3a9209ea

[clockworkinferno]

Yep, this was the example he gave us on linked list and unlike most examples he gives us this one didn't have any errors in it. It is kinda scary because he is the head of the computer science department at our school.

[JLBorges]

Here is the same code, with the errors removed, written in a somewhat more sane manner, with a few comments added to explain what is going on. It may be easier for you to understand this version:

#include <iostream>
// using namespace std;

void getdata(int& ident, int& grade_value);
// const int nil = 0;

class node_type		    // declaration of class//
{
    public:
        int id;
        int grade;
        node_type *next ;
};

int main()
{
    const int NUM_NODES = 10 ; // number of nodes to be added
    int ident, grade_value;

    getdata(ident, grade_value);

    // create a new node with id == ident, grade == grade_vale, next == nullptr
    node_type* first = new node_type { ident, grade_value, nullptr } ;

    node_type* last = first; // last keeps track of the last ode in the list.
                             // right now, there is only one node and last == first

    for( int i = 1 ; i < NUM_NODES ; ++i ) // add (NUM_NODES-1) more nodes
    {
        getdata(ident, grade_value);
        // create a new node with id == ident, grade == grade_vale, next == nullptr
        node_type* newnode = new node_type { ident, grade_value, nullptr } ;

        //**********Links previous node to newnode******//
        last->next = newnode; // append newnode to the end of the list:
                              // it becomes the next to the current last node

        last = newnode; // and the node just added at the end becomes the last node
    }

    //**********Traverses list and prints out nodes in chronological order ******
    double sum = 0 ;
    std::cout << "The list contains \n";

    // iterate through the nodes in the list
    // node_type* current = first ; to start with, the current node is the first node
    // current != nullptr ; when current becomes null, we are past the last node in the list; we should stop
    // current = current->next ; each time through the loop, we move from the current node to the next node
    for( node_type* current = first ; current != nullptr ; current = current->next )
    {
        // print out the id and grade in the current node
        std::cout << "ID is : " << current->id << "  GRADE is : " << current->grade << '\n' ;

        sum += current->grade ; // add the grade in the current node
    }

    const double average = sum / NUM_NODES ;
    std::cout << "\nThe average of the grades is " << average << '\n' ;
}

void getdata( int& ident, int& grade_value )
{
    std::cout << "Enter id and grade \n";
    std::cin >> ident;
    // std::cout << ident << '\n' ;
    std::cin >> grade_value;
    // std::cout << grade_value << '\n' ;
}

[clockworkinferno]

Ok, this does make more sense but I am still unsure how to code the assignment.

[JLBorges]

To insert an element, maintaining sorted order:

a. start by inserting the element as the first node (head) of the list.

b. iterate through the list, comparing the value of the current element with that of the next element 
    b1. if the value of the current element is greater than that of the next element, swap the values, 
          and continue with the iteration
    b2. if not, we are done.

Spoiler: http://coliru.stacked-crooked.com/a/4e1360aeaaea7efe

[clockworkinferno]

Thank you so much, this makes a lot of sense.