Member Avatar for Traicey

I have struct which is like this

struct Node
{
     int Num;
     Node *Point
}

so the program has to insert the numbers in the list during the execution, so the user can insert as many number as s/he wants so I want to sort those numbers when printing, I have a function call printList(Node *Current) so I need help on how to sort this I have tried selection sort but that didnt work out, I cant understant how am I gona relate the pointer variable which is Current with the sorting of the numbers in memory location

  • 3 Contributors
  • 2 Replies
  • 111 Views
  • 10 Hours Discussion Span
  • Latest Post Latest Post by Prabakar

Dani AI

Generated

Two practical ways to get a sorted output from the dynamic list described by were already suggested by and . Both are valid; the choice depends on what is easiest and safest for the program.

Keeping the list sorted during insertion (idea from ) makes printing trivial and avoids a separate O(n^2) sort pass. A typical routine finds the proper spot and links the new node in place:

void sortedInsert(Node*& head, Node* newNode)
{
    if (!head || newNode->Num <= head->Num) {
        newNode->Point = head;
        head = newNode;
        return;
    }
    Node* cur = head;
    while (cur->Point && cur->Point->Num < newNode->Num)
        cur = cur->Point;
    newNode->Point = cur->Point;
    cur->Point = newNode;
}

If the list already exists and a sort pass is preferred (as outlined), the simplest implementation swaps node data rather than rewiring pointers. That avoids many pointer bugs:

void selectionSort(Node* head)
{
    for (Node* i = head; i; i = i->Point) {
        Node* min = i;
        for (Node* j = i->Point; j; j = j->Point)
            if (j->Num < min->Num) min = j;
        if (min != i) std::swap(i->Num, min->Num);
    }
}

A minimal print routine that works with either approach:

void printList(Node* current)
{
    for (; current; current = current->Point)
        std::cout << current->Num << ' ';
    std::cout << '\n';
}

Notes and cautions: both sorted-insert and selection-style sorts are O(n^2) worst-case; for large lists prefer containers with built-in sort (for example, std::list::sort uses a merge sort and is O(n log n)). When manipulating raw pointers, always initialize newNode->Point and check for nulls before dereferencing to prevent crashes.

Recommended Answers

All 2 Replies

Member Avatar for ff4930

You should have a separate function to sort the linked list.

Selection sort should be fine, what didnt work out?
Have a node call LowestNode and have equal to the head of the list and iterate comparing if its smaller then that node becomes the lowest and if it reaches the end, append it to the new linked list and start the whole procedure again till you reach the end of your current linked list and your new linked list should be sorted.

so your printList is easier to implement
your printList(Node* Current), current will be the head of the list, so you just iterate from head to the end printing the num.

Member Avatar for Prabakar

Why not sort the list as you insert the node. It will prove to be very easy

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.