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

## All 2 Replies

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

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.