I have a linked list containing the following data

struct node
{
string name;
int hours;
node* next;
}

I have all function I've made so far working, adding indiviual node, deleting node, printing data in nodes, Ive made the program to read from a file upon execution to create the data in the nodes I use the method of building a list backward to load the new nodes into the list

Now I have to sort the nodes in descending order based on the hours contained in each object, any suggestions, thanks

Here's an implementation of quicksort for your linked list... (it sorts your list ascending, for descending: change each 'less' to 'greater', and 'greater' to 'less', or simply change '<' to '>')

To sort list : list = quicksort(list); For details on the quicksort algorithm, see wikipedia :)

node * quicksort(node * linked_list){

    if (linked_list == NULL) return linked_list;

	node * less = NULL;
	node * greater = NULL;

	node * pivot = linked_list;

	node * x = pivot->next;

	while(x != NULL){
	    node * next = x->next;
		if (x->hours < pivot->hours){
            x->next = less;
            less = x;
		} else {
            x->next = greater;
            greater = x;
		}
		x = next;
	}

	less = quicksort(less);
	greater = quicksort(greater);

	if (less != NULL){

	    node * less_end = less;
	    while(less_end->next != NULL) less_end = less_end->next;

        less_end->next = pivot;
        pivot->next = greater;

        return less;

	} else {

	    pivot->next = greater;
	    return pivot;

	}
}

Ohhhh thank you very very much!
That is excellent, I am working on a project and Ive got everything completed and I picked up a last detail about the node list being in descending order based upon the hours "object" in the node I wonder if implementing a insertion sorting algo when reading into the link list will causes problems? It seems like it would. I'll read over this and just transfer over as I have a dynamic array and each element in the arrays a pointer to the linked list so in essence each array object has a linked list attached to it and the point in that object is just holding the address of the linked list for the element

Edited 7 Years Ago by power_computer: n/a

This question has already been answered. Start a new discussion instead.