0

Am i right in thinking that it is not possible to perform insertion sort on a singly linked list?

My reasoning: assuming that insertion sort by definition means that, as we move to the right in the outer loop, we move to the left in the inner loop and shift values up (to the right) as required and insert our current value when done with the inner loop. As a result an SLL cannot accomodate such an algorithm. Correct?

4
  • where SLL means singly linked list, ok... Mar 28, 2011 at 18:06
  • Would I be correct in saying that by "insertion sort" you just mean inserting an element?
    – Maxpm
    Mar 28, 2011 at 18:10
  • Insertion sort is an algorithm that sequentially inserts the values in a list into the head of the list where you assume all elements are sorted by some order (mostly increasing). Mar 28, 2011 at 18:11
  • @Maxpm, you are confusing insertion with insertion sort: en.wikipedia.org/wiki/Insertion_sort
    – user425727
    Mar 28, 2011 at 18:13

3 Answers 3

1

Well, I'd sound like the Captain Obvious, but the answer mostly depends on whether you're ok with keeping all iterations directed the same way as elements are linked and still implementing the proper sorting algorithm as per your definition. I don't really want to mess around your definition of insertion sorting, so I'm afraid you'd really have to think yourself. At least for a while. It's an homework anyway... ;)

Ok, here's what I got just before closing the page. You may iterate over an SLL in reversed direction, but this would take n*n/2 traversals to visit all the n elements. So you're theoretically okay with any traversal directions for your sorting loops. Guess it pretty much solves your question.

3
  • can't iterate in reversed direction as suggested because there's no predecessor link in an SLL
    – user425727
    Mar 28, 2011 at 18:40
  • @both, just for clarification: i tagged this as homework as this is as close at it gets to saying that i'm doing this in the context of studying. my question is not an assignment per se, it is simply a question aimed at exploring what can be done and what can't. it seems that an SLL is just not suited for insertion sort and i was looking for thoughts on that statement. (almost) everything is possible so i'm sure there is a way but will it be worth the effort?
    – user425727
    Mar 28, 2011 at 19:04
  • it's possible to iterate in reverse direction, you only need a counter and an extra loop to do that. initially you find the tail element, iterating from head, and count up to compute its index, then you iterate to (index - 1)th element from the head, then to (index-2)th and so on. Mar 28, 2011 at 19:10
1

It is doable and is an interesting problem to explore.

The core of insertion sort algorithm is creating a sorted sequence with the first one element and extending it by adding new element and keeping the sequence is still sorted until it contains all the input data.

Singly linked list can not be traversed back, but you can always start from it's head to search the position for the new element.

The tricky part is when inserting node i before node j, you must handle their neighbor relationship well(I mean both node i and j's neighbor needs to be taken care of).

1

Here is my code. I hope it useful for you.

int insertSort(Node **pHead)
{
Node *current1 = (*pHead)->next;
Node *pre1 =*pHead;
Node *current2= *pHead;
Node *pre2=*pHead;
while(NULL!=current1)
    {
    pre2=*pHead;
    current2=*pHead;

    while((current2->data < current1->data))
    {
        pre2 = current2;
        current2 = current2->next;
    }
    if(current2 != current1)
    {
        pre1->next=current1->next;
        if(current2==*pHead)
        {
            current1->next=*pHead;
            *pHead = current1;
        }
        else
        {
            pre2->next = current1;
            current1->next = current2;
        }
        current1 = pre1->next;
    }
    else
    {
        pre1 = pre1->next;
        current1 = current1->next;
    }
}
return 0;

}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.