Member Avatar for power_computer

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
  • 1K Views
  • 7 Hours Discussion Span
  • Latest Post Latest Post by power_computer

Dani AI

Generated

Good summary of the problem and a useful quicksort from . Two practical choices are easiest in practice: (A) keep inserting nodes in sorted order as the file is read (simple, no extra memory), or (B) build the list then sort it with an O(n log n) algorithm. Choice depends on list size and expected input order.

Insertion-while-reading (best for small lists or mostly-sorted input)

  • Easy to implement and keeps the list always sorted, but worst-case cost is O(n^2) if every insert scans most of the list.
  • Keep this if N is small or file is nearly sorted. Example insertion for descending hours:
node *insert_sorted(node *head, node *newNode) {
    if (!head || newNode->hours > head->hours) {
        newNode->next = head;
        return newNode;
    }
    node *cur = head;
    while (cur->next && cur->next->hours >= newNode->hours)
        cur = cur->next;
    newNode->next = cur->next;
    cur->next = newNode;
    return head;
}

Sort-after-build (recommended for large lists)

  • Merge sort on singly linked lists is the usual recommendation: stable, O(n log n), and works by pointer manipulation. An iterative bottom-up merge avoids recursion depth issues.
  • A simple alternative is collecting node* into std::vector, std::stable_sort (or std::sort) by hours (descending), then relinking the vector elements — O(n log n) and very straightforward:
std::vector<node*> v;
for (node* p = head; p; p = p->next) { v.push_back(p); }
std::stable_sort(v.begin(), v.end(), [](node*a,node*b){ return a->hours > b->hours; });
for (size_t i=0;i+1<v.size();++i) v[i]->next = v[i+1];
if (!v.empty()) v.back()->next = nullptr; head = v.empty() ? nullptr : v.front();

Notes and tips

  • If duplicates must preserve input order, use stable_sort (or merge sort).
  • If building lists into an array of heads (as described), sort each list independently or sort the head pointers in the array if ordering across buckets is needed.
  • Always set the last node->next = nullptr, and watch ownership/cleanup to avoid leaks.

Recommended Answers

All 2 Replies

Member Avatar for BosByte

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;

	}
}
Member Avatar for power_computer

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 because: n/a
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.