Printable View
i thought of breaking it into two lists merge them and sorting them
in this way
but i dont have this breaking into two stuff here??Code:node* merge(node* l1,node* l2)
{
if ((!l1)&&(!l2))
{
return NULL;
}
if (!l1)
{
v1=99999999999;
v2=l2->val;
}
if (!l2)
{
v2=99999999999;
v1=l1->val;
}
if (v1>v2)
{
l2->next=merge(l1,l2->next);
return l2;
}
else
{
l1->next=merge(l1->next,l2);
return l1;
}
}
because i need to sort a single linked list
??
Use selection sort instead, you'll be 100% happier, guaranteed. Merge sort is fine, but stinks on a linked list.
i'll do both.Quote:
Originally Posted by Adak
first my original question:
i got an idea to use a spliting function
i split it in half and send it to merge.
its not a real mergesort because i split it only onesCode:node* split(node* l)
{
node* l1,*l2,*t,*r;
l=t=r;
if (!l) return NULL;
if(!l->next) return l;
while(r)//turtle rabbit algorithm
{
r=r->next;
prev=t;
t=t->next;
if (t->next)
{
r=r->next;
}
prev->next=NULL;
return merge(l,t);
}
??(is it ok??)
regarding sorting by selection sort :
i only can sort it by value.(fliiping the values)
there is no way i could think of so many relinking to do
in a recursive way.(like i did before)
Is it OK to split a mergesort just once? No. :) Mergesort relies on each sub-string being sorted before the two are merged together. It could happen with just a single split, but it's *extremely* unlikely.
You don't have to re-link all the nodes as you sort, just swap the values which the nodes contain. That's fine! You can swap a whole struct very easily, with all it's members, if you need to. You don't have to swap each member of the struct, individually.
An alternative would be to use mergesort on the larger substrings, and use selection sort, on only the smaller substrings, after you've made a split or two (or four or whatever), and then merge the substrings back together again.
Do you *have* to use a mergesort as one of your linked list sorting algorithms?
but look at my merge function
it doesnt need a sorted lists
its merging two unsorted lists
into a sorted one
ahh you are correct
Code:node* split(node* l)
{
node* l1,*l2,*t,*r;
l=t=r;
if (!l) return NULL;
if(!l->next) return l;
while(r)//turtle rabbit algorithm
{
r=r->next;
prev=t;
t=t->next;
if (t->next)
{
r=r->next;
}
prev->next=NULL;
return merge(split(l),split(t));
}
I've heard of the turtle & rabbit algorithm, but have not used it or studied it. I don't have any opinion of it, pro or con, nor do I know if you have implemented it properly.Quote:
Originally Posted by kakaroto
There are more ways to sort data than you might imagine. If you want a recommendation for sorting a linked list, I recommend selection sort. If you have another algorithm that works, and you like it's performance, then sure, use it.
ok thanks :)
Ok. I have a question, which is related to sorting a linked list, and that's why I didn't create any thread for it. I just want to sort a singly linked list, should I also go for selection sort(I'm assuming heap sort), as Adak posted in his earlier post in this thread. I want the code to be most efficient.
Insertion, bubble, and selection sort are all very fast if the number of items to be sorted is less than 25 or so. Even in arrays, they're quicker than standard Quicksort (and frequently used as an enhancement to Quicksort, on the smaller sub arrays it generates).
After 25, I would look at Cocktail and Comb 11 algorithms, because they're basically bi-directional versions of one (sometimes two), of the above sorting algorithms. I've only tested the Comb 11 version on arrays, but it is *very* good on large quantities of data - within a hair of equaling Quicksort. I'm not a big fan of Heapsort, but it can also be quite fast.
You will need to do some testing on linked list sorting, to see what works best with your specific data.
How? I mean by calculating the Big O thing or something else.Quote:
Originally Posted by Adak
This is completely false. I've done comparative performance testing with sorts on a linked list (bubble, insertion, selection, merge and quick), and merge sort has all the advantages over selection sort, etc that it does on an array. Which is to say, on a very large linked list, it and quicksort perform exponentially better than anything else, including selection sort. That is, they will do in seconds what takes minutes for selection sort.Quote:
Originally Posted by Adak
Agreed, plus merge sort on a linked list does not need the extra space consumption as does merge sort on an array.Quote:
Originally Posted by MK27
Yep, because you just swap pointers. I just tried this again to demonstrate:Quote:
Originally Posted by laserlight
Command (h for help, Q to quit): N
How many records? 25000
New list is 3515.62 kb
Command (h for help, Q to quit): s
Selectionsorting....
624950002 Iterations Comparison calls: 312487500
Elapsed time: 2 min 10 sec
Command (h for help, Q to quit): S
Shuffled.
Command (h for help, Q to quit): m
Mergesorting..............24999 function calls
503757 Iterations Comparison calls: 334111
Elapsed time: 0 min 0 sec
The bigger the list, the more severe the difference. Merge sort will still do 100's of thousands in several seconds, while selection sort is simply not worth waiting for at that point.
If anyone wants to look at the implementation I used for that:
linklist_comparative-sorts.c
Big O notation is a good overall guide, but it's not based on actual run-time. If you want good results for your program, with your target computer, and your typical data, then that's what you should test with, and use actual run-time as your guide.Quote:
Originally Posted by BEN10
I will add mergesort to my list of good sorters for large sized linked lists. Thanks for that correction.
Ditto that. Here's some thoughts I had about the significance of the big O notation after doing this:Quote:
Originally Posted by Adak
http://cboard.cprogramming.com/c-pro...tml#post829926
It mostly has to do with the distinction between an iteration and comparison, which normative presentations of big O notation do not take into account. Gosh what a funny kid I was 6 months ago :p
does the code of split and merge are correct?
Does it successfully sort the array?Quote:
Originally Posted by kakaroto