insertion sort linked list c++

Question

I'm trying to write a code to sort a linked list containing integers but its not working how I thought it would based on my reasoning I worked out for it with pencil and paper. Instead of traversing through the list, it compares the first pair of values, deletes the second value in the list and returns the remainder of the list. My method code is:

//typedef Node * ListType;

void insertionSort(ListType &list) {
    ListType p = list;
    Node * curr;
    if(p == NULL || p->next == NULL){
        return;
    }
    while(p != NULL){
        curr = p->next;
        if(curr == NULL){
            break;
        }
        if(p->data > curr->data){
            p->next = curr->next;
            curr->next = p;
        }
        p = p->next;
    }
}

Say, for instance I start with a list: 5 2 3 4 The output I get after calling this method on this list is: 5 3 4

I'm not comfortable with pointers. Any help is appreciated!

Sam Varshavchik · Accepted Answer · 2016-05-01 04:14:26Z

2

This kind of a task works much better if instead of a pointer, you use a pointer to a pointer. It also works better if the new element is passed separately, instead of being "pre-inserted" at the beginning of the list.

But, let's go with what you have, and the new node is pre-inserted at the beginning of the list, and you want to move it to the right position.

Then, it's going to be something like this:

#include <iostream>

class Node {

public:

    Node *next;

    int data;
};

typedef Node * ListType;

void insertionSort(ListType &list) {
    ListType *p = &list;

    while ( (*p)->next && (*p)->next->data < (*p)->data)
    {
        ListType node= *p;

        *p=node->next;

        node->next=node->next->next;

        (*p)->next=node;

        p= &(*p)->next;
    }
}

int main()
{
    Node *head=0;

    int n;

    while (std::cout << ">>> ", std::cin >> n)
    {
        Node *p=new Node;

        p->data=n;

        p->next=head;
        head=p;

        insertionSort(head);

        for (p=head; p; p=p->next)
            std::cout << p->data << " ";
        std::cout << std::endl;
    }
}

Sample results:

$ ./t
>>> 5
5 
>>> 7
5 7 
>>> 1
1 5 7 
>>> 3
1 3 5 7 
>>> 9
1 3 5 7 9 
>>> 6
1 3 5 6 7 9 
>>> 0
0 1 3 5 6 7 9

The trick here that instead of p being a pointer to the node you're inserting, p is the pointer to the pointer to the node that's being inserted. So, if you need to "push" the new node further down the list, the "previous" pointer is *p, which you can easily update now.

Even though this looks confusing at first, this is far less messy that keeping track of the "previous" node, whose next pointer you need to update. All the if statement hairballs go away completely. That's where all the confusion comes from.

Also, if, as I mentioned initially, the new node is not preinserted at the beginning of the list, and gets passed as a separate pointer then this becomes much easier to understand. But, that was your starting point, so...

edited May 1, 2016 at 4:14

answered May 1, 2016 at 4:06

Sam Varshavchik

119k6 gold badges109 silver badges164 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

SamS Over a year ago

Hi Sam, I tried applying what you suggested but it's still not working completely. I'm trying to apply all of the logic into one method definition since it is part of a bigger class that will apply other functions on a linkedlist repeatedly. It only sorts for one element of the list and then doesn't take care of the rest of the elements. For instance, I started with a list 6 2 5 2 3 4 and the output it gives me every single time I call the method on it is 2 5 2 3 4 6

Sam Varshavchik Over a year ago

Before "6" is added to the head of the list, the list contains "2 5 2 3 4". This is not a validly sorted list, of course. It should be "2 2 3 4 5". With insertion sort, every time a new node is inserted, the list gets sorted correctly. See the example output in my answer.

SamS Over a year ago

Oh. I'm trying to make it so it can sort a list in one go even if its like 2 4 2 5 3 6 2 or something like that. But no luck so far

Sam Varshavchik Over a year ago

That wouldn't be an "insertion sort", then.

Collectives™ on Stack Overflow

insertion sort linked list c++

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related