wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> median in  link list 
        
(Message started by: chuncl on Sep 29th, 2008, 2:58pm)
Title: median in  link list
Post by chuncl on Sep 29th, 2008, 2:58pm
How to find median in a unsorted single link list efficiently?

I tried to do some search, but found nothing. If it was posted before, I am apologize.

Thanks
Title: Re: median in  link list
Post by Hippo on Sep 29th, 2008, 4:15pm
The single linked list does not cause additional problems.

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1219397742;start=3#3

http://en.wikipedia.org/wiki/Selection_algorithm
Title: Re: median in  link list
Post by chuncl on Sep 29th, 2008, 6:06pm

on 09/29/08 at 16:15:34, Hippo wrote:
The single linked list does not cause additional problems.

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1219397742;start=3#3

http://en.wikipedia.org/wiki/Selection_algorithm


thanks, Hippo, yeah, you are right.  but then we some time we say that quick sort is not suitable for link-list while merge sort is better?  Comments? thanks
Title: Re: median in  link list
Post by towr on Sep 30th, 2008, 1:15am

on 09/29/08 at 18:06:25, chuncl wrote:
thanks, Hippo, yeah, you are right.  but then we some time we say that quick sort is not suitable for link-list while merge sort is better?  Comments? thanks
Selecting appropriate pivots for quicksort in a list is probably more work.
Title: Re: median in  link list
Post by Hippo on Sep 30th, 2008, 3:48am

on 09/30/08 at 01:15:55, towr wrote:
Selecting appropriate pivots for quicksort in a list is probably more work.


No, but the reordering in single linked list causes problems (if you are restricted to use single linked lists during entire algorithm).
Title: Re: median in  link list
Post by towr on Sep 30th, 2008, 5:37am

on 09/30/08 at 03:48:16, Hippo wrote:
No, but the reordering in single linked list causes problems (if you are restricted to use single linked lists during entire algorithm).
I don't see any reason why you should ever be limited to using just one list. It makes no difference in memory usage to split the list in two during the process (and, if need be, join them at the end).
Finding a random pivot on the other hand can be done in O(1) with a direct access memory structure, but only O(n) in a linked list. (Not that it necessarily needs to be completely random).
Title: Re: median in  link list
Post by chuncl on Sep 30th, 2008, 7:10am

on 09/30/08 at 05:37:58, towr wrote:
I don't see any reason why you should ever be limited to using just one list. It makes no difference in memory usage to split the list in two during the process (and, if need be, join them at the end).
Finding a random pivot on the other hand can be done in O(1) with a direct access memory structure, but only O(n) in a linked list. (Not that it necessarily needs to be completely random).


So for quicksort in single link list,there is no problem in the  partition part, the only thing matter here is random selection of pivot? if we don't do  random selection of pivot, then quicksort is as applicable to single link list as the merge sort? Is my understanding right? Thanks
Title: Re: median in  link list
Post by towr on Sep 30th, 2008, 7:35am

on 09/30/08 at 07:10:30, chuncl wrote:
So for quicksort in single link list,there is no problem in the  partition part, the only thing matter here is random selection of pivot? if we don't do  random selection of pivot, then quicksort is as applicable to single link list as the merge sort? Is my understanding right?
It is rather critical for quicksort to make a decent selection of the pivot. Otherwise you get quicksort ;)
And to do that I don't see how you can avoid increasing the cost of pivot selection compared to the case where you have an array.
Title: Re: median in  link list
Post by Hippo on Sep 30th, 2008, 1:42pm
The recurence t(n) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif2t(n/2)+O(n) gives t(n) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gifO(n log n).
Even the recurrence t(n) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gift(n1)+t(n2)+O(n) where n1+n2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lt.gifn and n1http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lt.gifcn http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/gt.gifn2 for a constant c gives t(n) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gifO(n log n).
So I cannot see a problem here.
Title: Re: median in  link list
Post by towr on Sep 30th, 2008, 2:06pm

on 09/30/08 at 13:42:44, Hippo wrote:
The recurence t(n) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif2t(n/2)+O(n) gives t(n) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gifO(n log n).
Even the recurrence t(n) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gift(n1)+t(n2)+O(n) where n1+n2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lt.gifn and n1http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lt.gifcn http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/gt.gifn2 for a constant c gives t(n) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gifO(n log n).
So I cannot see a problem here.
You can't see the problem with having a larger constant factor?
The difference in the constant factor is the whole reason quicksort and heapsort are usually preferred over mergesort in the first place. They're faster, not in an order of magnitude way, but simply in practice.
Title: Re: median in  link list
Post by Hippo on Sep 30th, 2008, 11:24pm
Yes, the constant factor grows. I actually do not understand what we are solving now.

If there is single linked list on input and we are allowed to convert the list into an array, we can spend c.n to prepare for standard *sort, and after sorting to convert the array into the single linked list ...

If we are restricted to use single linked list during the entire algorithm, there is no effective implementation of quicksort swap of two elements. OK let we change the quicksort in a way we just split the list into 2(or 3) lists based on comparision with pivot. Even if you do not choose median as a pivot but prefere some sampling, the sampling time is majorized by the list splitting time and it forces much less than doubling the constant factor. The factor grow caused by pointer manipulation would be higher.

On the other side, single linked lists are natural data structures for mergesort.

BTW: Heapsort and Quicksort can sort an array without additional memory ...
Title: Re: median in  link list
Post by towr on Oct 1st, 2008, 12:15am

on 09/30/08 at 23:24:39, Hippo wrote:
Yes, the constant factor grows. I actually do not understand what we are solving now.
We somehow went from finding the medium to sorting a linked list, I think.


Quote:
OK let we change the quicksort in a way we just split the list into 2(or 3) lists based on comparision with pivot. Even if you do not choose median as a pivot but prefere some sampling, the sampling time is majorized by the list splitting time and it forces much less than doubling the constant factor. The factor grow caused by pointer manipulation would be higher.
What do you mean by "the sampling time is majorized by the list splitting time" ?
It seems to me to find a pivot you'd need to go through half the list on average. So that's a factor of 1.5 (1/2x for finding pivot, 1x for splitting. If pointer manipulation is the largest part of time cost, then that's fairly bad in comparison to mergesort.
Unless we can do them simultaneously (find the next pivots while splitting the list on the current one).
Title: Re: median in  link list
Post by Hippo on Oct 1st, 2008, 6:06am
Yes, you translated well what I mean ;)


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board