Making an efficient algorithm for sorting with a pointer

Question

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:

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.
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.

Please, specify, how do you want to sort the list. You can simply use some conventional method of sorting if you map the list to some kind of vector. — V-X
– V-X, Commented Feb 27, 2013 at 6:45
Have you tried mergesort, quicksort or any other standard sorting method? — n. m. could be an AI
– n. m. could be an AI, Commented Feb 27, 2013 at 6:52
Given the constraints in your last edit, this sounds like a homework question. Is it? — Roger Rowland
– Roger Rowland, Commented Feb 27, 2013 at 7:26
Mergesort the list, and there are only about a thousand samples implementations that do it, one linked with this comment. It is O(NlogN) and plenty-efficient for space needs. It requires no additional pointers (except the temp pointers in the recursive algorithm) and in fact, you don't need the freeNode pointer for it either (though using it for a prev pointer would make the final algorithm significantly more straight-forward to implement). — WhozCraig
– WhozCraig, Commented Feb 27, 2013 at 8:14

c.fogelklou · Accepted Answer · 2013-02-27 16:54:03Z

2

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

edited Feb 27, 2013 at 16:54

answered Feb 27, 2013 at 7:10

c.fogelklou

1,8012 gold badges14 silver badges26 bronze badges

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

1 Comment

c.fogelklou Over a year ago

@DeadCoder, Read the Wikipedia on it. en.m.wikipedia.org/wiki/Tree_sort#section_1

Collectives™ on Stack Overflow

Making an efficient algorithm for sorting with a pointer

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related