CODEWITHSUNDEEP
c++sortinglinked-list
DeadCoder
DeadCoder

Reputation: 87

Making an efficient algorithm for sorting with a pointer

Consider a simple struct:

struct Node{
 int val;
 Node *next;
 Node *freeNode;
};

Now I have to sort a given linked list only using freeNode and the method has to be efficient. I can't make another list and use some kind of sorted-insert there. Nor can use genome or bubble sort. The pointer freeNode of any elem in the list can be pointing to any elem in the list.

Now I have come up with two ideas:

  1. Use freeNode to make a doubly Linked List.

    And do pair comparing, i.e. compare the ith elem with the (i+1)th elem. When I find that two elements need to be swapped, I swap them and then again start from the head of the List.

    This algorithm would be more than O(n) (not sure just guessing). It will take much time.

  2. Another method is that my freeNode points to elem that is smaller than it.

    E.g. if I have 30->6->14->56>Tail, then

    56->freeNode->14
30->freeNode->14
14->freeNode->6
6->freeNode->NULL.

    But again, this doesn't help much, because when I insert 45 or 20 I would have to re-arrange my freeNode pointer. And, again, it would not be a very efficient method.

Any suggestions on this? How to use freeNode to implement a better and efficient method for sorting. Pseudo-code would work, and I'd actually prefer that over real code.

EDIT: You can't use arrays, vectors or anything else. Just the freeNode pointer. Use it in any way you want. Keep it NULL or have it point to elements of your choice.

Upvotes: 0

Views: 296

Answers (1)

c.fogelklou
c.fogelklou

Reputation: 1801

You could make a binary tree. Use next as your right child pointer and freeNode as your left child pointer. Make the first of the nodes you should sort your root. Then, take the rest of your nodes and "insert" them in your new binary tree.

Edit: Like this:

Your typedef:

typedef struct Node{
 int val;
 struct Node *next;
 struct Node *freeNode;
} NodeT;

Some defines to make this code easier to read:

// Conversions to make this code easier to read.
#define pRight freeNode
#define pLeft  next

Recursive binary tree insertion:

static void BinTreeInsert( NodeT *pRootNode, NodeT *pChildNode );

Edit 2: solution removed when made apparent that this was homework. Figure out out dude!

This solution would be O(n log n) best / average case but O(n2) worst case... If the incoming list is already sorted.

http://en.m.wikipedia.org/wiki/Tree_sort#section_1

Upvotes: 2

Related Questions