wu :: forums - Print Page


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

        riddles >> cs >> Sorting Geometrically-distributed values
        
(Message started by: KWillets on Oct 28^th, 2014, 11:02am)

Title: Sorting Geometrically-distributed values
Post by KWillets on Oct 28^th, 2014, 11:02am

Hello, it's been a while since I've posted here, but this question seems like it belongs here.

I need to sort integers with a geometric distribution (eg P(1)=.5, P(2)=.25, .125...), but I'm having trouble finding references on the problem.

It seems like o(n). I tried something like Quicksort where it splits between == min and > min, and recurses on the >min part. I'm experimenting with doing one pass and resetting the min as lower values are encountered.

The recurrence is something like C(n)=P*n + C((1-P)n), i.e. fairly easy to get o(n).

It seems like a simple algo, but I can't find any mention of it. The only examples I've found are Groupsort and some kind of counting sort where the highest bin is all the remaining values; these seem needlessly complicated and data-dependent.

Has anybody seen this problem?

Title: Re: Sorting Geometrically-distributed values
Post by towr on Oct 28^th, 2014, 2:11pm

I haven't seen the problem before. But I agree that it seems solvable in O(n); for P=1/2 a very skewed binary tree comes to mind. For smaller P there's probably smarter choices, but it doesn't seem to get worse than O(n/P).

Title: Re: Sorting Geometrically-distributed values
Post by KWillets on Oct 28^th, 2014, 3:32pm

It's funny, because I've since found benchmarks of quicksort on various distributions (I searched for "exponential distribution" instead of geometric) and found linear times, but no discussion of it.

Quicksort works for this if it happens to pick the median equal to the minimum; that's how I found this before trying an explicit min. However 2-way quicksort can run into problems in one direction, eg splitting < and >=, since it will fail to split out the min in that case. Ternary will work with pivot = either min or max.