2

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

2
Contributors
2
Replies
7
Views
7 Years
Discussion Span
Last Post by power_computer
0

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;

	}
}
0

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 by power_computer: n/a

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.