Member Avatar for Twins_effect

How do you make an insertion sorting algoritm using a liked list, first of all, i really dont have the slightest idea about link list, can anyone pleeeeeeeeeaaaaaaase help me.... :?: :?: :?: :?: :?: :cry: :cry:

  • 4 Contributors
  • 4 Replies
  • 272 Views
  • 2 Weeks Discussion Span
  • Latest Post Latest Post by SpS

Dani AI

Generated

— insertion sort on a singly linked list is easiest done by building a sorted list and moving nodes from the original list into it one at a time. Detach the current node, scan the sorted list to find where it belongs, then relink it there. This is an in-place, stable algorithm (no new node copies required), with O(n^2) worst-case time but O(n) best-case for nearly-sorted input. Use a dummy head to avoid special-casing insertion at the front.

Here is a compact C++ example for a singly linked list of ints. Note the important save of next before relinking and the use of <= to keep the sort stable (existing equal elements stay before newly-inserted equals).

struct Node {
    int val;
    Node* next;
    Node(int v): val(v), next(nullptr) {}
};

Node* insertionSortList(Node* head) {
    Node dummy(0);           // dummy head for the sorted list
    Node* curr = head;
    while (curr) {
        Node* next = curr->next;           // save next node before relink
        Node* prev = &dummy;               // find insertion point
        while (prev->next && prev->next->val <= curr->val)
            prev = prev->next;
        // insert curr between prev and prev->next
        curr->next = prev->next;
        prev->next = curr;
        curr = next;                       // continue with saved next
    }
    return dummy.next;
}

Quick troubleshooting/tips:

  • Always save curr->next before changing pointers — forgetting this loses the remaining list.
  • Use a dummy node to simplify head insertions.
  • For large, randomly ordered lists prefer merge sort on lists (O(n log n)); insertion sort is good for small or nearly-sorted lists.
  • Test edge cases: empty list, single node, many duplicates, and already-sorted input.
  • If you need a custom comparison, make the loop use your comparator instead of <=.

pointed to a general insertion-sort resource earlier in the thread; the snippet above shows the linked-list-specific relinking approach and common pitfalls to watch for.

Recommended Answers

All 4 Replies

Member Avatar for the_coolcat_11 
#include <iostream>
using namespace std;


void instruction ();
float do_next_op ( float, float , char );


int main()
{
instruction();                      // displays instruction


float total;
float newentry;
char op;


total = 0;                           // initialisation


cin >> op;
while  (op != 'Q' && op != 'q' && op != '=')
{
cin >> newentry;
do_next_op (total, newentry, op);
cin >> op;
}
cout << "the final result is " << total << endl;


system ("pause");
return 0;
}



void instruction()
{
cout << endl;
cout << "*******************************************************" << endl;
cout << "                    CALCULATOR                    " << endl;
cout << "        the initial value is set to 0             " << endl;
cout << "   please enter an operator and a number to begin " << endl;
cout << "    the accepted operators are : + - * / ^ only   " << endl;
cout << "       enter a q, Q or = to exit the program      " << endl;
cout << "*******************************************************" << endl;
cout << endl;
}


float do_next_op ( float total, float newentry, char op)
{
switch (op)
{
case '+': total = total + newentry;
break;
case '-': total = total - newentry;
break;
case '*': total = total * newentry;
break;
case '/': total = total / newentry;
if (newentry == 0)
{
cout << "divide by zero is unexecutable" << endl;
}
break;
case '^': total =  pow (total,newentry);
break;
default : cout << "  Unacceptable Operator(" << op << ")" << endl;
}
cout << "result so far is " << total << endl;
cout << endl;


return (total);
}
Edited by happygeek because: fixed formatting
Member Avatar for the_coolcat_11

help me to answer the product of first 10 even numbers in c++ program

Member Avatar for SpS

help me to answer the product of first 10 even numbers in c++ program

Two posters posting the same code :eek: . now what is happening.

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.